Maths Olympiad Prep

Library / /72 of 87

Algebra Difficulty 7.0 National Olympiad, round 2 Prove it Russia

A pair of polynomials F(x,y)F(x, y), G(x,y)G(x, y) with integer coefficients is called important, if the following condition holds: if for some integers a,b,c,da, b, c, d both F(a,b)F(c,d)F(a, b) - F(c, d) and G(a,b)G(c,d)G(a, b) - G(c, d) are divisible by 100, then both aca - c and bdb - d are divisible by 100. Determine if there exist an important pair of polynomials P(x,y)P(x, y), Q(x,y)Q(x, y) such that the pair P(x,y)xyP(x, y) - xy, Q(x,y)+xyQ(x, y) + xy is also important.

Solution

Ответ. Does not exist.

Решение. Let FF and GG be an important pair of polynomials. Consider pairs of residues modulo 100 of numbers F(a,b)F(a,b) and G(a,b)G(a,b), where a,ba,b range over all integer pairs from 0 to 99. According to the problem's condition, all such residue pairs are distinct. Since there are 1002100^2 possible number pairs, each residue pair modulo 100 occurs exactly once. Therefore, all 4 possible parity combinations of F(a,b)F(a,b) and G(a,b)G(a,b) are achieved.
Since the parity of a polynomial's value with integer coefficients at point (a,b)(a,b) depends only on the parity of aa and bb, we conclude that the value pairs (F(0,0);G(0,0))(F(0,0); G(0,0)), (F(1,0);G(1,0))(F(1,0); G(1,0)), (F(0,1);G(0,1))(F(0,1); G(0,1)), and (F(1,1);G(1,1))(F(1,1); G(1,1)) must give all four possible parity combinations.
However, observe that for both polynomial pairs F=P,G=QF = P, G = Q and F(x,y)=P(x,y)xy,G(x,y)=Q(x,y)+xyF(x,y) = P(x,y) - xy, G(x,y) = Q(x,y) + xy, the first three parity pairs are identical, while the fourth pair differs. Consequently, both such polynomial pairs cannot be important.

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.