New users cannot post latex it seems

sophie.germain wrote: Answer: 11 Good job: 0/7.

New users cannot post latex it seems, so here are wordy writings. First, let's show that 10 colors are not enough. Assume that we can use only 10 colors, from 0 to 9, and color in i the two-digit numbers with unit digit i. Observe that in this way the requested property does not hold. Therefore, the minimum value of k is at least 11. Assume for contradiction that 11 colors are not enough. Construct a table with 10 rows and 9 columns, consisting of all two-digit numbers, so that the (i,j)-th cell has the number with first digit j and second digit i-1. From PHP there is a row with two differently colored numbers in it. Without loss of generality those numbers are 21 and 31 (in the second row) and 21 is in color 1, while 31 is in color 2. Now from the assumption in the second and third columns, we must have numbers in only those two colors, otherwise, we are done. Consider the numbers in the second row except 21 and 31, i.e. the collection of numbers (11,41,51,61,71,81,91). After a bit of case bash, one can observe that for every number in this collection we can have at most one "new" color (different from colors 1 and 2) in the column generated by it. Thus there are at most 7 "new" colors in those columns (because there are 7 numbers in the collection), therefore we have used at most 7+2<11 colors in total - contradiction!

With $10$ (or less) colours if one colours the numbers in a way that all numbers with the same units digit have the same colour, then $a$ and $b$ with the desired property do not exist. We prove that $11$ colours always suffice. As there are $10$ possible unit digits, by the Pigeonhole principle there is a digit $i$ and two numbers with units digit $i$ which have a different colour. Now focus on the numbers with units digit $i$. They are $9$ in amount and since the colours are $11$, it must be the case that some colour, say red, does not appear among these numbers. Pick $c$ to be a red number (such exists, since the problem conditions require that each colour appears at least once). Pick $b$ to be a number with units digit $i$ and tens digit equal to that of $c$ (it is not red since it has $i$ units digit) and $a$ to be a number with $i$ units digit from a colour, different from that of $b$ (we argued above that such exists). The result follows.