Problem

Source: 2019-20 International Dürer Competition ,Category E, P2

Tags: combinatorics, Tables



Initially we have a $2 \times 2$ table with at least one grain of wheat on each cell. In each step we may perform one of the following two kinds of moves: $i.$ If there is at least one grain on every cell of a row, we can take away one grain from each cell in that row. $ii.$ We can double the number of grains on each cell of an arbitrary column. a) Show that it is possible to reach the empty table using the above moves, starting from the position down below. b) Show that it is possible to reach the empty table from any starting position. c) Prove that the same is true for the $8 \times 8$ tables as well.


Attachments: