We have a pile of $2016$ cards and a hat. We take out one card, put it in the hat and then divide the remaining cards into two arbitrary non empty piles. In the next step, we choose one of the two piles, we move one card from this pile to the hat and then divide this pile into two arbitrary non empty piles. This procedure is repeated several times : in the $k$-th step $(k>1)$ we move one card from one of the piles existing after the step $(k-1)$ to the hat and then divide this pile into two non empty piles. Is it possible that after some number of steps we get all piles containing three cards each?
Problem
Source: PAMO 2016
Tags: combinatorics
29.04.2016 23:37
Among $\{1, 2, 3, 4\}$ only $3$ works. Call an integer good if it satisfies the desired property and also it is $\not\equiv 3\ (\textrm{mod}\ 4)$. Let $k \ge 5$ be the smallest good integer. Then $k = a + b + 1$, with $a, b \equiv 3\ (\textrm{mod}\ 4)$, but then $k \equiv 3\ (\textrm{mod}\ 4)$, contradiction. So there are no good integers. $2016$ is divisible by $4$ and hence doesn't work.
09.06.2017 23:59
Suppose we can meet the condition. Then the number of cards left is divisible by $3$, and since we put one card into the hat in each move and $3\mid 2016$, the number of moves made is divisible by $3$. Let $3k$ be the number of moves. Then the number of piles left is $3k+1$, and the number of cards left is $9k+3$ (!). Since we made $3k$ moves, the number of cards in the hat is $3k$, and the number of cards left is $2016-3k$ (*). Combining (!) and (*) we get $9k+3=2016-3k\Longleftrightarrow12k=2013$, which is not true for $k\in \mathbb{N}$, therefore we cannot meet the condition.
31.03.2019 14:55
Let the number of piles be $x$ and the total number of cards not in the hat be $y$ . On each turn the number of piles increases by 1 and the number of cards not in the hat decreases by 1. Therefore $x + y$ doesn't change and will always remain at $2017$. Also, we are trying to find solutions for $y/x= 3$ . This means that $y=3x$ and therefore $x + y = x + 3x = 4x = 2017$. We see that this is not possible so far as $x$ is an integer, so it is not possible.