2^n currencies and a greedy king
Source: Japan Mathematical Olympiad Finals 2016 Q3
April 1, 2016
combinatorics
Problem Statement
Let be a positive integer. In JMO kingdom there are 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.