Maths Olympiad Prep

Library / /474 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Prove it

Example 4 Let a,bNa, b \in \mathbf{N}^{*}. Prove: In the interval [0,abab][0, a b-a-b], there are exactly 12(a1)(b1)\frac{1}{2}(a-1)(b-1) integers cc that cannot be expressed in the form ax+bya x+b y, where x,yx, y are non-negative integers.

Solution

Proof
Let
I={n0nabab,nZ},A=abab,I=\{n \mid 0 \leqslant n \leqslant a b-a-b, n \in \mathbf{Z}\}, A=a b-a-b,

and call a number representable if it can be written as ax+by(x,y0,x,yZ)a x+b y(x, y \geqslant 0, x, y \in \mathbf{Z}), otherwise it is called non-representable.

Clearly, II contains
abab+1=(a1)(b1)a b-a-b+1=(a-1)(b-1)

integers, so it suffices to prove that the number of representable numbers is equal to the number of non-representable numbers, i.e., to prove: for any nI,nn \in I, n and AnA-n are exactly one of which is representable.

First, nn and AnA-n cannot both be representable. Otherwise, A=n+(An)A=n+(A-n) would also be representable, contradicting the conclusion of Example 3.

Second, if nn is non-representable, then AnA-n is representable. Because if nn is non-representable, then the integers x,yx, y satisfying
n=ax+byn=a x+b y

must have exactly one of them negative. Without loss of generality, assume x<0x<0. In this case, we can choose an appropriate tZt \in \mathbf{Z} such that yat[0,a),x+bt<0y-a t \in[0, a), x+b t<0 (otherwise nn would be representable). This means there exist x<0,0y<ax<0, 0 \leqslant y<a, such that n=ax+byn=a x+b y. Therefore,
An=ababaxby=a(x1)+b(a1y)\begin{aligned} A-n & =a b-a-b-a x-b y \\ & =a(-x-1)+b(a-1-y) \end{aligned}

Clearly, x10,a1y0-x-1 \geqslant 0, a-1-y \geqslant 0, so AnA-n is representable.
In summary, the proposition is established.

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.