Maths Olympiad Prep

Library / /577 of 860

Algebra Difficulty 5.3 AIME, harder Find the answer

Find the smallest integer n≥5n \geq 5 for which there exists a set of nn distinct pairs (x1,y1),…,(xn,yn)\left(x_{1}, y_{1}\right), \ldots,\left(x_{n}, y_{n}\right) of positive integers with 1≤xi,yi≤41 \leq x_{i}, y_{i} \leq 4 for i=1,2,…,ni=1,2, \ldots, n, such that for any indices r,s∈{1,2,…,n}r, s \in\{1,2, \ldots, n\} (not necessarily distinct), there exists an index t∈{1,2,…,n}t \in\{1,2, \ldots, n\} such that 4 divides xr+xs−xtx_{r}+x_{s}-x_{t} and yr+ys−yty_{r}+y_{s}-y_{t}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

In other words, we have a set SS of nn pairs in (Z/4Z)2(\mathbb{Z} / 4 \mathbb{Z})^{2} closed under addition. Since 1+1+1+1≡0( mod 4)1+1+1+1 \equiv 0(\bmod 4) and 1+1+1≡−1( mod 4),(0,0)∈S1+1+1 \equiv-1(\bmod 4),(0,0) \in S and SS is closed under (additive) inverses. Thus SS forms a group under addition (a subgroup of (Z/4Z)2(\mathbb{Z} / 4 \mathbb{Z})^{2} ). By Lagrange's theorem (from basic group theory), n∣42n \mid 4^{2}, so n≥8n \geq 8. To achieve this bound, one possible construction is {1,2,3,4}×{2,4}\{1,2,3,4\} \times\{2,4\}

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.