XXIX Rioplatense Mathematical Olympiad

Question

There are some cards on the table. Each card has an integer number written on it. Beto performs the following operation many times: he picks two cards from the table, computes the difference between the numbers that are written on them, he writes this difference on his notebook and then removes those two cards from the table. He can do this operation as many times as he wants, as long as there are at least 2 cards on the table.

In the end, Beto computes the product of all the numbers written on his notebook. Beto's goal is that this product is divisible by

7^{100}

.

a. Prove that if there are initially 207 cards on the table then Beto can always achieve his goal, regardless of which numbers are written on the cards.

b. If there are initially 128 cards on the table, is it true that Beto can always achieve his goal?

Accepted Answer

a. To begin, let us note that, as long as there are more than 7 cards on the table, we can always find two cards with the same remainder upon division by 7 (because there are only 7 possible remainders). In that situation, Beto can pick those two cards and write in his notebook the difference, which will be divisible by 7. Since there are 207 cards and each of those operations requires picking just two cards, Beto can repeat that 100 times without a problem. Hence, after that, there will be 100 numbers divisible by 7 written on the notebook, and so their product will be divisible by

7^{100}

as we wanted.

b. Yes, Beto can always achieve his goal. For a proof, see the solution to Problem 1.3.