Maths Olympiad Prep

Library / /468 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

In how many ways can the set of ordered pairs of integers be colored red and blue such that for all aa and bb, the points (a,b),(1b,a+1)(a, b),(-1-b, a+1), and (1b,a1)(1-b, a-1) are all the same color?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let φ1\varphi_{1} and φ2\varphi_{2} be 9090^{\circ} counterclockwise rotations about (1,0)(-1,0) and (1,0)(1,0), respectively. Then φ1(a,b)=(1b,a+1)\varphi_{1}(a, b)=(-1-b, a+1), and φ2(a,b)=(1b,a1)\varphi_{2}(a, b)=(1-b, a-1). Therefore, the possible colorings are precisely those preserved under these rotations. Since φ1(1,0)=(1,2)\varphi_{1}(1,0)=(-1,2), the colorings must also be preserved under 9090^{\circ} rotations about (1,2)(-1,2). Similarly, one can show that they must be preserved under rotations about any point (x,y)(x, y), where xx is odd and yy is even. Decompose the lattice points as follows: L1={(x,y)x+y0(mod2)}L2={(x,y)xy10(mod2)}L3={(x,y)x+y1yx+10(mod4)}L4={(x,y)x+y+1yx10(mod4)}\begin{aligned} & L_{1}=\{(x, y) \mid x+y \equiv 0 \quad(\bmod 2)\} \\ & L_{2}=\{(x, y) \mid x \equiv y-1 \equiv 0 \quad(\bmod 2)\} \\ & L_{3}=\{(x, y) \mid x+y-1 \equiv y-x+1 \equiv 0 \quad(\bmod 4)\} \\ & L_{4}=\{(x, y) \mid x+y+1 \equiv y-x-1 \equiv 0 \quad(\bmod 4)\} \end{aligned} Within any of these sublattices, any point can be brought to any other through appropriate rotations, but no point can be brought to any point in a different sublattice. It follows that every sublattice must be colored in one color, but that different sublattices can be colored differently. Since each of these sublattices can be colored in one of two colors, there are 24=162^{4}=16 possible colorings.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.