KöMaL problem A, 2025

Combinatorics Difficulty 6.0 National Olympiad Prove it Hungary

We write the ordered pair $(1,0)$ on the board. In one step, if the ordered pair $(a,b)$ is on the board, we erase it and replace it with either $(a+b,b)$ or $(2a+b,a+b)$ . (For example, after two steps, the pair on the board may be one of $(1,0)$ , $(2,1)$ , $(3,1)$ , or $(5,3)$ .) Prove that after $n$ steps, the ordered pair on the board can take exactly $2^n$ different values.

We don't reproduce this publisher's solutions. Their own solution is here — work the problem first.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: KöMaL, licensed Rights held by KöMaL and the MATFUND Foundation. Statement reproduced verbatim; metadata (topic, difficulty) added by this project. Solutions are the publisher's, linked not copied.