Let $T$ be the set of all 2-digit numbers whose digits are in $\{1,2,3,4,5,6\}$ and the tens digit is strictly smaller than the units digit. Suppose $S$ is a subset of $T$ such that it contains all six digits and no three numbers in $S$ use all six digits. If the cardinality of $S$ is $n$, find all possible values of $n$.
Problem
Source: 2012 Indonesia Round 2.5 TST 4 Problem 2
Tags: combinatorics proposed, combinatorics
02.06.2012 19:13
EDIT: New version: Obviously, $|T|=\binom{6}{2}=15$. It can be easily checked that there is no solution for $n<4$ and that $4\le n \le 9$ are possible (Take $S=\{12,13,14,15,16,23,24,25,26\}$ for example. By removing numbers from this set we can create possible sets of every lower cardinality). Consider a set $S$ with $n=10$. We have $\frac{\binom{6}{2,2,2}}{3!}=15$ "bad" sets of 3 numbers that contain all 6 digits. In order for $S$ to be allowed, there must not be one of these bad sets in it. As there are 5 numbers that are not in $S$ and every number is in exactly 3 different bad sets, we can eliminate $3*5=15$ bad sets at most, implying that we have to eliminate exactly one number of every bad set. The problem is perfectly symmetrical, so we can assume wlog that $12\in S$ (as one number with 1 as a digit must be in $S$). So exactly one out of each of $\{34,56\},\{35,46\},\{36,45\}$ cannot be in $S$. We have 2 cases: 1. We eliminate 3 numbers with a shared digit, wlog $34,35,36\notin S$. Now we have to eliminate the remaining bad sets $\{13,24,56\},\{13,25,46\},\{13,26,45\},\{14,23,56\},\{15,23,46\},\{16,23,45\}$ with 2 numbers that are not in $S$. But the only 2 numbers that appear 3 times in these bad sets are 13 and 23. And eliminating these would result in $S$ not containing the digit 3, contradiction. 2. We eliminate 3 numbers not sharing a digit, wlog $34,46,36\notin S$. Again, look at the remaining bad sets: $\{13,24,56\},\{13,26,45\},\{14,23,56\},\{14,26,35\},\{16,23,45\},\{16,24,35\}$. As there are no numbers appearing 3 times in these bad sets, it is not possible to eliminate all of them with 2 numbers, so that $n=10$. As every $S$ with $n>10$ has a subset with cardinality 10 that is not possible, there are no solutions for $n\ge10$ and we conclude that $4\le n \le 9$.
02.06.2012 19:20
Problem with that: If some two numbers you choose (to determine the forbidden number) share a digit, there's no forbidden number.
03.06.2012 15:31
New version of my proof, would you pls check quickly if its correct now?