There are coins worth $1, 2, \ldots , b$ rubles, blue bills with worth $a{}$ rubles and red bills worth $a + b$ rubles. Ilya wants to exchange a certain amount into coins and blue bills, and use no more than $a-1$ coins. Pasha wants to exchange the same amount in coins and red bills, but use no more than $a{}$ coins. Prove that they have equally many ways of doing so.
Problem
Source: Russian TST 2020, Day 6 P1
Tags: combinatorics, number theory
31.03.2023 09:57
interesting result, there should definitely be a beautiful combinatorial bijection but here is a (mostly) algebraic solution to the problem:
07.06.2024 19:04
I found this surprisingly difficult for P1. Took me like 2 hours. Anyway, here's a combinatorial bijection. I'll present 2 algorithms and the reader can deduce that they're inverses of each other. Let's start with the $a$-bills case. If there's a $b$-coin and an $a$-bill we swap them for an $a+b$-bill. If there's only an $a$-bill, we increase every coin by $1$ (even the initially nonexistent $a$-th coin). If there's no $a$-bill, then we finish. Now let's start with the $a+b$-bills. If there's no zero-coin, we reduce every coin by $1$ and add an $a$-bill. If there's a zero-coin and an $a+b$-bill, we increase that coin by $b$, discard the $a+b$-bill, and add an $a$-bill. If there's a zero-coin and no $a+b$-bill, we finish.
07.06.2024 19:34
Let $\mathcal{C}$ be the multiset with infinite copies of all numbers $1$ through $b$. Then $\sum_{A\subset \mathcal{C}, |A|\le n}x^{S(A)}$ is the generating function representing the sums the coins $1,\dots, n$ make (where $n\le a$). It suffices to show\begin{align*}(1+x^a+x^{2a}+\dots)\sum_{A\subset \mathcal{C}, |A|<a}x^{S(A)}=(1+x^{a+b}+x^{2(a+b)}+\dots)\sum_{B\subset \mathcal{C}, |B|\le a}x^{S(B)}\\ \Longleftrightarrow\sum_{A\subset \mathcal{C}, |A|<a}x^{S(A)+a+b}+\sum_{|B|=a}x^{S(B)}=\sum_{B\subset \mathcal{C}, |B|\le a}x^{S(B)+a}.\end{align*}This is clear as: The first sum matches with the summands in the third sum whose sets contain $b$, and for each set in the second sum we decrease all elements by one and obtain the rest of the third sum.
09.06.2024 07:06
@oVlad , can you share the official solution ?