MathDB

3

Part of 2016 Japan MO Finals

Problems(1)

2^n currencies and a greedy king

Source: Japan Mathematical Olympiad Finals 2016 Q3

4/1/2016
Let nn be a positive integer. In JMO kingdom there are 2n2^n citizens and a king. In terms of currency, the kingdom uses paper bills with value \$$2^n$ and coins with value \$$2^a(a=0,1\ldots ,n-1)$. Every citizen has infinitely many paper bills. Let the total number of coins in the kingdom be $S$. One fine day, the king decided to implement a policy which is to be carried out every night: [*] Each citizen must decide on a finite amount of money based on the coins that he currently has, and he must pass that amount to either another citizen or the king; [*]Each citizen must pass exactly \$1 more than the amount he received from other citizens.
Find the minimum value of $S$ such that the king will be able to collect money every night eternally.
combinatorics