Competition problem — Combinatorics

Library / /23 of 520

Combinatorics Difficulty 5.0 AIME Find the answer

Let $S$ be the set of two-digit numbers that do not contain the digit 0. Two numbers in $S$ are called friends if their largest digits are equal, and if the difference between their smallest digits is equal to 1. For example, 68 and 85 are friends, 78 and 88 are friends, but 58 and 75 are not friends.
Determine the largest integer $m$ such that there exists a subset $T$ of $S$ with $m$ elements, such that any two elements of $T$ are not friends.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

Answer: 45. We can take for $T$ the set of numbers whose smallest digit is odd.
Conversely, if $x=\overline{a b}$ with $1 \leqslant b<a \leqslant 9$ then $x$ and $x+1$ are friends. If $x=\overline{a b}$ with $2 \leqslant a<b \leqslant 9$ and $a$ even, then $x$ and $x+10$ are friends. We have thus found 36 disjoint pairs of friends. Consequently, among the 72 numbers $\geqslant 21, T$ can contain at most 36 numbers, so $|T| \leqslant 9+36=45$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.