Problem 1010
Alice writes the integer numbers from 1 to 19 on a board (once each). She chooses two of the same parity, and replaces them with their average. She starts again (18 times in all) until she gets only one number.- 1A, 1B, 1C,1D, 1E, 1F. What are the numbers (between 1 and 19) that she won't be able to obtain at the end?
(we will write them by ascending order; all boxes are not necessarily to be filled).
- 2A, 2B, 2C,2D, 2E, 2F. What are all the numbers (between 1 and 19) that he will be able to obtain at the end?
(we will write them by ascending order; all boxes are not necessarily to be filled)
For Question 1, the following program allows to exhaustively search on the original size of the problem (the search takes about 5 minutes). The program uses (among others) a tree to cache the already explored intermediate configurations (numbers displayed on the board in ascending order).
For Question 2, the following program is a program analog to the one of the first question, but a lot faster to make the exhaustive search (a few seconds) given the smaller combinatory (4 numbers each time)
For Question 2, the following program is a program analog to the one of the first question, but a lot faster to make the exhaustive search (a few seconds) given the smaller combinatory (4 numbers each time)
- 1A, 1B. The only numbers that we cannot obtain by replacing two integers by their average are 1 and 19.
- 2A, 2B, 2C, 2D, 2E : The only numbers that can be obtained by replacing four integers by their mean are 4, 7, 10, 13 et 16.