Maths Olympiad Prep

Library / /8 of 14

Combinatorics Difficulty 5.6 AIME, harder Prove it Singapore

For each i=1,2,,Ni = 1, 2, \dots, N, let ai,bi,cia_i, b_i, c_i be integers such that at least one of them is odd. Show that one can find integers x,y,zx, y, z such that xai+ybi+zcixa_i + yb_i + zc_i is odd for at least 4N/74N/7 different values of ii.

Solution

Consider all the 7 triples (x,y,z)(x, y, z), where x,y,zx, y, z are either 00 or 11 but not all 00. For each ii, at least one of the numbers ai,bi,cia_i, b_i, c_i is odd. Thus among the 7 sums xai+ybi+zcixa_i + yb_i + zc_i, 3 are even and 4 are odd. Thus there are altogether 4N4N odd sums. Thus there is choice of (x,y,z)(x, y, z) for which at least 4N/74N/7 of the corresponding sums are odd. (You can think of a table where the rows are numbered 1,2,,N1, 2, \ldots, N and the columns correspond to the 7 choices of the triples (x,y,z)(x, y, z). The 7 entries in row ii are the 7 sums xai+ybi+zcixa_i + yb_i + zc_i. Thus there are 4 odd numbers in each row, making a total of 4N4N odd sums in the table. Since there are 7 columns, one of the columns must contain at least 4N/74N/7 odd sums.)

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 and solution reproduced as published; topic and difficulty added by this site.