Problem

Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade

Tags: combinatorics



Let $m > n$ be positive integers. In the host country of the International Olympiad in Informatics this year, there are coins of $1$, $2$, $\ldots$, $n$ alexandrias, lira banknotes, each worth $m$ alexandrias, and pharaoh banknotes, each worth $m+n$ alexandrias. Let $A$ be a positive integer. Boris wants to exchange the amount $A$ using coins and lira, using no more than $m-1$ coins, while Vesko wants to exchange the amount $A$ using coins and pharaohs, using no more than $m$ coins. Prove that regardless of the value of $A$, the number of ways for each of them to fulfill their desire is the same.