Problem

Source: Tournament of Towns, Junior A-Level , Fall 2019 p6

Tags: combinatorics



Peter has several $100$ ruble notes and no other money. He starts buying books; each book costs a positive integer number of rubles, and he gets change in $1$ ruble coins. Whenever Peter is buying an expensive book for $100$ rubles or higher he uses only $100$ ruble notes in the minimum necessary number. Whenever he is buying a cheap one (for less than $100$ rubles) he uses his coins if he has enough, otherwise using a $100$ ruble note. When the $100$ ruble notes have come to the end, Peter has expended exactly a half of his money. Is it possible that he has expended $5000$ rubles or more? (Tatiana Kazitsina)