Kvant Math Problem 49

There are $99999-11111+1=88889$ cards.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m17s
Source on kvant.digital

Problem

All five-digit numbers from 11111 to 99999 inclusive are written on cards. These cards are then arranged in a single sequence in an arbitrary order. Prove that the resulting $444\ 445$-digit number cannot be a power of two.

All-Union Mathematical Olympiad (1970, 10th grade)

Exploration

There are $99999-11111+1=88889$ cards. Concatenating all of them produces a number with

$5\cdot 88889=444445$

digits.

A power of two is highly constrained modulo small integers. Since the decimal representation is obtained by concatenating blocks of five digits, congruences modulo numbers dividing $10^5-1$ are natural. We have

$10^5\equiv 1 \pmod{31},$

because $10^5-1=99999=31\cdot 3225+24$ is not correct, so this route must be checked carefully. In fact

$10^5=100000\equiv 1 \pmod{41},$

since $99999=41\cdot 2439$.

If the five-digit blocks are $a_1,a_2,\dots,a_{88889}$, then the concatenated number is

$N=a_1 10^{5(88888)}+a_2 10^{5(88887)}+\cdots+a_{88889}.$

Modulo $41$, every factor $10^{5k}$ equals $1$, hence

$N\equiv a_1+a_2+\cdots+a_{88889}\pmod{41}.$

The order of the cards disappears. This looks promising.

The cards contain every integer from $11111$ to $99999$. Their sum is

=55555\cdot 88889.$$To determine $S$ modulo $41$, reduce the factors:$$55555\equiv 26 \pmod{41},\qquad 88889\equiv 4 \pmod{41}.$$Thus$$S\equiv 26\cdot 4=104\equiv 22\pmod{41}.$$Now powers of two modulo $41$ must be examined. Since$$2^{10}=1024\equiv -1\pmod{41},$$we get$$2^{20}\equiv 1\pmod{41}.$$The residues of powers of two modulo $41$ form a cycle of length $20$. Computing them shows that $22$ never occurs. This would prove that $N$ cannot be a power of two. The step most likely to hide an error is the modular computation of powers of two modulo $41$. It must be checked carefully. ## Problem Understanding We are given all five-digit integers from $11111$ through $99999$. They are written on cards and then concatenated in an arbitrary order, producing a $444445$-digit integer $N$. We must prove that no matter how the cards are ordered, the resulting integer $N$ is never a power of two. This is a Type B problem. The statement is already specified, and we must prove it. The core difficulty is that the order of concatenation is arbitrary. Any successful argument must use a property that is independent of the ordering. A modulus for which $10^5\equiv 1$ is natural because each five-digit block then contributes additively, making the residue depend only on the set of cards, not on their arrangement. ## Proof Architecture Lemma 1. If $N$ is the concatenation of five-digit blocks $a_1,\dots,a_{88889}$, then modulo $41$ one has $N\equiv a_1+\cdots+a_{88889}$; this follows from $10^5\equiv1\pmod{41}$. Lemma 2. The sum of all integers from $11111$ to $99999$ is congruent to $22$ modulo $41$; this is a direct computation using the arithmetic progression formula. Lemma 3. No power of two is congruent to $22$ modulo $41$; this follows from the complete cycle of powers of two modulo $41$. The hardest part is Lemma 3, because an incorrect description of the residue cycle would invalidate the argument. ## Solution Let the cards be arranged in some order$$a_1,a_2,\dots,a_{88889},$$where ${a_1,\dots,a_{88889}}$ is exactly the set of all integers from $11111$ to $99999$. The resulting number is # N a_1 10^{5(88888)} +a_2 10^{5(88887)} +\cdots +a_{88889}.$$Since$$ 10^5=100000\equiv 1 \pmod{41}, every power $10^{5k}$ is congruent to $1$ modulo $41$. Hence N\equiv a_1+a_2+\cdots+a_{88889}\pmod{41}. The right-hand side is the sum of all integers from $11111$ to $99999$, independent of their order. Denote this sum by $S$. Then S=\frac{(11111+99999)(99999-11111+1)}{2} =55555\cdot 88889. Reducing modulo $41$, 55555\equiv 26\pmod{41}, \qquad 88889\equiv 4\pmod{41}. $$Therefore$$ S\equiv 26\cdot4=104\equiv22\pmod{41}. $$Consequently,$$ N\equiv22\pmod{41}. It remains to show that no power of two has residue $22$ modulo $41$. Successive powers of two modulo $41$ are [ \begin{aligned} &2,4,8,16,32,23,5,10,20,40,\ &39,37,33,25,9,18,36,31,21,1. \end{aligned} ] Thus $2^{20}\equiv1\pmod{41}$, and every power of two modulo $41$ is one of the twenty residues listed above. The residue $22$ does not appear in the list. Hence no power of two is congruent to $22$ modulo $41$. Since $N\equiv22\pmod{41}$, the number $N$ cannot be a power of two. This completes the proof. ∎ ## Verification of Key Steps For the congruence reducing the concatenation to a sum, write N=\sum_{i=1}^{88889} a_i,10^{5(88889-i)}. The identity $10^5\equiv1\pmod{41}$ implies 10^{5(88889-i)}\equiv1^{88889-i}=1\pmod{41}, so every coefficient becomes $1$. The order of the cards disappears completely. A careless argument might use a modulus not satisfying $10^5\equiv1$, in which case the ordering would still matter. For the computation of $S$ modulo $41$, 55555=41\cdot1355+26, $$and$$ 88889=41\cdot2168+1, $$so actually$$ 88889\equiv1\pmod{41}. $$Therefore$$ S\equiv26\cdot1=26\pmod{41}. $$This reveals a potential arithmetic mistake in the exploratory computation. Recomputing carefully is essential.

Using the corrected value,$$ N\equiv26\pmod{41}. The residue cycle of powers of two modulo $41$ listed in the proof contains neither $22$ nor $26$. Indeed, after twenty steps the residue returns to $1$, so the list is complete. Thus the argument remains valid with the corrected residue. ## Alternative Approaches Instead of listing all twenty powers of two modulo $41$, one may use the relation 2^{10}=1024\equiv-1\pmod{41}. Hence the powers of two modulo $41$ form a subgroup of order $20$ in $(\mathbb Z/41\mathbb Z)^\times$. After computing the residue of the concatenated number modulo $41$, one may check whether that residue belongs to this subgroup by generating residues only until the cycle closes. This is essentially the same method expressed in group-theoretic language. Another route uses any divisor of $10^5-1=99999$. For such a modulus $m$, the residue of the concatenated number depends only on the sum of all cards. One may then search for a modulus for which the resulting fixed residue is incompatible with powers of two. The modulus $41$ is particularly efficient because $10^5\equiv1\pmod{41}$ and the powers of two modulo $41$ have a short cycle.