Maths Olympiad Prep

Library / /78 of 86

Combinatorics Difficulty 7.0 National olympiad Prove it Estonia

Little Juku writes all integers from 11 to nn on a blackboard, but as he does not know the digit 44 yet, he skips all numbers that contain 44. Juku's sister Mari erases two numbers on the blackboard and writes the absolute value of the difference of these numbers on the blackboard. Then Mari again erases two numbers on the blackboard and writes the absolute value of their difference on the blackboard, etc. Can it happen after a finite number of such steps that there are all integers from 11 to nn that contain the digit 44 and only these on the blackboard, each one exactly once, if

a. n=2021n = 2021;

b. n=10000n = 10000?

Solution

*Answer:* (a) No; (b) No.

a. The difference and the sum of two integers have equal parity, likewise are an integer and its absolute value of equal parity. Thus Mari's every step keeps the parity of the sum of all numbers on the blackboard unchanged. Among 1,2,,20211, 2, \ldots, 2021, there are 10111011 odd numbers. As 10111011 is odd itself, the sum of all numbers 1,2,,20211, 2, \ldots, 2021 is odd. This implies that the sum of all integers from 11 to 20212021 that contain 44 and the sum of integers from 11 to 20212021 that do not contain 44 have different parities. Hence the set of all natural numbers from 11 to 20212021 that contain 44 can never appear on the blackboard.

b. Let there be aa positive integers from 11 to 1000010000 that do not contain 44. Then there are 10000a10000 - a positive integers from 11 to 1000010000 that contain 44. As each Mari's step decreases the number of numbers on the blackboard by 11, she should make a(10000a)a - (10000 - a) or, equivalently, 2a100002a - 10000 steps to reach the desired state. As only one new number can appear at each step, introducing 10000a10000 - a new numbers assumes 2a1000010000a2a - 10000 \ge 10000 - a which is equivalent to a200003a \ge \frac{20000}{3}. But there are only 949^4 numbers among the first 1000010000 positive integers that do not contain 44; since 94=6561<2000039^4 = 6561 < \frac{20000}{3}, achieving the desired state is impossible.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.