Maths Olympiad Prep

Library / /10 of 86

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:
Let NN be the number of ordered pairs (x,y)(x, y) of integers such that
x2+xy+y22007 x^2 + x y + y^2 \leq 2007
Remember, integers may be positive, negative, or zero!

a. Prove that NN is odd.

b. Prove that NN is not divisible by 33.

Solution

Solution:

a.
If (x,y)(x, y) is a pair of integers that satisfies the inequality, then (x,y)(-x, -y) is also such a pair, since
(x)2+(x)(y)+(y)2=x2+xy+y2. (-x)^2 + (-x)(-y) + (-y)^2 = x^2 + x y + y^2.
So we can match up pairs of solutions to the inequality, (x,y)(x,y)(x, y) \leftrightarrow (-x, -y). Every solution will be paired with a different solution, except for the one remaining solution (0,0)(0, 0) which is paired with itself. This shows that the number of solutions is odd.

b.
This is similar to the previous part, except now that we have to arrange the nonzero solutions into triples instead of pairs. If (x,y)(x, y) is a solution to the inequality, then so is (xy,x)(-x-y, x), since
(xy)2+(xy)x+x2=x2+xy+y2 (-x-y)^2 + (-x-y)x + x^2 = x^2 + x y + y^2
Applying this transformation three times in succession gives the cycle
(x,y)(xy,x)(y,xy)(x,y) (x, y) \rightarrow (-x-y, x) \rightarrow (y, -x-y) \rightarrow (x, y)
so we can unambiguously arrange the solutions into cycles of three, of the form {(x,y),(xy,x),(y,xy)}\{(x, y), (-x-y, x), (y, -x-y)\}. Now, if any two solutions in the same cycle are equal, then the third is also equal to them, so every cycle contains either three distinct solutions or just one solution. If a cycle contains just one solution (x,y)(x, y), then x=yx = y and y=xyy = -x - y gives x=y=0x = y = 0. Therefore, the solution (0,0)(0, 0) forms a cycle by itself, and every other cycle consists of three different solutions, which means that the total number of solutions has remainder 11 when divided by 33.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.