9.2 Given 19 cards. Is it possible to write a nonzero digit on each card in such a way that you can compose from these cards an unique 19-digits number, which is divisible by 11? (R. Zhenodarov, I. Bogdanov)
Problem
Source: All-Russian MO Round 4, 2005
Tags: combinatorics proposed, combinatorics
03.04.2005 01:11
suppose there is an unique number build with the cards, color the cards alternately black and white, changing the possition of 2 monochromatic cards, also give a good numbers so we must have 10 cards have the same number and the other 9 the same number. Let $a$ be the number in the black cards, and $b$ the number in the white cards we must have $10a-9b=0$(mod11), or $a=2b$ (mod 11) so we have the possible pairs: $(2,1), (2,4), (3,6),(4,8), (6,1), (7,3),(8,5), (9,7)$ from here i suggest trial and error with this combinations of numbers to check if some of them works...
03.04.2005 08:26
Hmm... Too many unfinished solutions last time, Pascual!
03.04.2005 19:19
We have $n=n_1n_2...n_{19}$ with $11|n$ If we set $m_k$ the number $n$ with $n_k\leftrightarrow n_{k+2}$ and $1\leq k\leq 17$ we have $m_k$ divisible by 11 because $n-m_k=(n_k-n_{k+2})10^{19-k}+(n_{k+2}-n_k)10^{17-k}=(n_{k+2}-n_k)10^{17-k}\times (1-100)=11\times 9(n_k-n_{k+2})10^{17-k}$ Consequently $\forall k, m_k=n\Rightarrow \forall k, n_k = n_{k+2}$ We have $10$ cards with $n_1$ and $9$ cards with $n_2$ Now we have to prove that with these cards the only number divisible by 11 is $n_1n_2n_1...n_2n_1$ We use the fact that $x_1x_2x_3...x_{2n}x_{2n+1}\equiv x_1-x_2+x_3-...x_{2n}-x_{2n+1} (11)$ For our numbers we have $k$ times $+n_1$, $(10-k)$ times $-n_1$, $(10-k)$ $+n_2$ and $(k-1)$ times $-n_2$ so we have to prove that $k\times n_1+(10-k)n_2 - (10-k)n_1 - (k-1)n_2\equiv (2k+1)n_1-2k\times n_2\equiv 0(11)$ has only the $k=10$ solution (By supposition $k=10$ works since $11|n$ thus we have $n_1\equiv 2n_2 (11)$) $(2k+1)n_1-2k\times n_2\equiv 0(11)$ $\Leftrightarrow (4k+2)n_2 - 2k\times n_2\equiv 0(11)$ $\Leftrightarrow (2k+2)n_2\equiv 0(11)$ $\Leftrightarrow 2k+2\equiv 0(11)$ $k=10$ is the unique solution since $1\leq k\leq 10$ So with $10$ cards $n_1$ and $9$ cards $n_2$ and $(n_1,n_2)\in ((2,1), (4,2), (6,3), (8,4), (1,6), (3,7), (5,8), (7,9))$ there is an unique 19-digits number, which is divisible by 11, it's $n_1n_2...n_2n_1$