[NOIP2017]XiaoKai's confusion

If a price $P$ can be paid using such coins, this is equivalent to saying there exist non-negative integers $m$ and $n$ such that $P = ma + nb$ . The last three options have such expressions:

• $ab + a - b = a + (a - 1)b$
• $ab - a + b = (b - 1)a + b$
• $ab + a + b = a + (a + 1)b = (b + 1)a + b$

By process of elimination, the solution is $ab - a - b$ .

---

A more direct (and perhaps more satisfying) proof, without taking advantage of multiple choice: Let $P$ be the largest such price. Then $P + a = sa + tb$ for some $s, t \ge 0$ . That means $P = (s - 1)a + tb$ . If $s > 0$ , then this gives $P$ as a sum of positive integer multiples of $a$ and $b$ , which contradicts our construction of $P$ . Therefore $s = 0$ and $P + a = tb$ . A symmetrical argument shows that $P + b = ka$ , some $k > 0$ . Then

$P = tb - a = ka - b$

$\implies ka + a = tb + b$

$\implies (k + 1)a = (t + 1)b$

$\implies a \mid (t + 1)b \text{ and } b \mid (k + 1)a$

Since $a$ and $b$ are relatively prime, we must have $a \mid (t + 1)$ and $b \mid (k + 1)$ , i.e. there are positive integers $u$ and $v$ such that $t + 1 = au$ and $k + 1 = bv$ . Then $(bv)a = (k + 1)a = (t + 1)b = (au)b$ , meaning $u = v$ . Thus $abu = ka + a = tb + b \implies abu - a - b = ka - b = tb - a = P$ .

Suppose $x$ and $y$ are non-negative integers such that $u = x + y$ . Then

$P = ab(x + y) - a - b$

$= abx + aby - a - b$

$= (bx - 1)a + (ay - 1)b$

If $bx - 1 > 0$ and $ay - 1 > 0$ , then we have an expression for $P$ as a sum of non-negative integer multiples of $a$ and $b$ , which is impossible. Therefore either $x = 0$ or $y = 0$ , meaning $u = 1$ and $P = ab - a - b$ . $\quad \square$

I solved this problem with respect to symmetry: Since we don't know whether a or b is the larger of the two integers, the solution must stay the same if we exchange them. So any solution with different signs before a and b is not possible. And since $a \times b + a + b$ is a price, which can be paid, the only solution left is $a \times b - a - b$ , which is the right one.

Obviously this only works if possibilities for solutions are given.

Take $a$ , its multiples cover numbers of form $a \times k$ , from $a$ to infinity ( $k \in \mathbb{N}$ ). If we introduce shifts of amount $s \in \{1,2,\dots,a-1\}$ , then we can cover numbers of form $a \times k +s$ , from $a+s$ to infinity. The shift is provided by $b$ , but it would not take effect from the beginning. in order to find the first number of form $a \times k +s$ we need to solve $bx \equiv s (mod \ a)$ for $x$ . Having $x$ , $bx$ would be the first number of the form $a \times k +s$ . There would be a solution, as $a$ and $b$ are coprimes. Also, for each $s \in \{1,2,\dots,a-1\}$ there is a unique solution $x \in \{1,2,\dots,a-1\}$ . Then we find the maximum of $bx$ , which is $b(a-1)$ . the number $b(a-1)$ is the starting point of covering that is given by a specific shift. so, the previous number of the similar form, is the largest that has not been covered. that would be $b(a-1)-a=ba-b-a$