Browse · MathNet
PrintNational Olympiad Final Round
Estonia counting and probability
Problem
a) The general form of a three-digit number is initially written on a blackboard. Ann and Enn replace by turns letters with digits, exactly one at a time, with Ann starting. Can Ann write digits in such a way that, irrespectively of Enn's move, the resulting three-digit number would be divisible by 11? (Different letters may be replaced with equal digits but the letter must not be replaced with zero.)
b) Ann and Enn got bored with writing the general form of the number again at the beginning of each game, and decided to change the rules as follows. First, Ann writes one digit to the blackboard, then Enn writes the second digit either to the right or to the left of it, and finally Ann completes the number with writing the third digit either to the left or to the right of the two digits already on the blackboard (writing between the digits is not allowed). Can Ann write digits in such a way that, irrespectively of Enn's move, the result would be a three-digit number (i.e., not starting with 0) that is divisible by 11?
b) Ann and Enn got bored with writing the general form of the number again at the beginning of each game, and decided to change the rules as follows. First, Ann writes one digit to the blackboard, then Enn writes the second digit either to the right or to the left of it, and finally Ann completes the number with writing the third digit either to the left or to the right of the two digits already on the blackboard (writing between the digits is not allowed). Can Ann write digits in such a way that, irrespectively of Enn's move, the result would be a three-digit number (i.e., not starting with 0) that is divisible by 11?
Solution
a) Let Ann replace on her first move one of letters or with a digit . If Enn now replaces the other one of and with digit , too, the resulting number is divisible by 11 if and only if is divisible by 11, which in turn is the case if is divisible by 11. The only such digit is 0 but cannot be replaced with 0. If Ann replaces on her first move the letter with a non-zero digit then Enn can replace with the digit . The number resulting from Ann's second move differs from the number by less than 11, whence it cannot be divisible by 11.
b) Let Ann write 9 on her first move. If Enn now writes before or after it a digit and Ann writes after or before of it, respectively, the digit , then the resulting number is divisible by 11. Ann cannot make her last move in such a way only if Enn on his move has written either 9 to the end of the number or 0 to the beginning of the number. If Enn has written 9 to the end of the number, the blackboard contains digits 99 and Ann can construct a multiple of 11 by writing 0 to the end. If Enn has written 0 to the beginning of the number, Ann can write 2 to the very beginning which results in 209, again a multiple of 11.
b) Let Ann write 9 on her first move. If Enn now writes before or after it a digit and Ann writes after or before of it, respectively, the digit , then the resulting number is divisible by 11. Ann cannot make her last move in such a way only if Enn on his move has written either 9 to the end of the number or 0 to the beginning of the number. If Enn has written 9 to the end of the number, the blackboard contains digits 99 and Ann can construct a multiple of 11 by writing 0 to the end. If Enn has written 0 to the beginning of the number, Ann can write 2 to the very beginning which results in 209, again a multiple of 11.
Final answer
a) No. b) Yes.
Techniques
Games / greedy algorithmsDivisibility / FactorizationModular Arithmetic