Track / Stage 5 / 11 of 400 #611 of 1964

Problem 611

AIME late

Combinatorics Difficulty 5.0 Prove it Taiwan IMO Selection Camp · Taiwan

Given a positive integer $n$ , consider all integer points in $n$ -dimensional space (that is, points all of whose coordinates are integers). When two integer points have Euclidean distance $1$ , we say they are adjacent to each other. Is it possible to mark some of these integer points so that, for every integer point, among the $(2n + 1)$ points consisting of the point itself and all points adjacent to it, exactly one is marked?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Yes, it is possible!
令 $x_1, \dots, x_n$ 為整數點的座標, 將所有滿足
$(2n + 1) \mid (x_1 + 2x_2 + \dots + nx_n)$
的點標記, 即達成條件; 對於每個點, $x_1 + 2x_2 + \dots + nx_n$ 可以唯一的表示為 $(2n+1)l \pm k$ , 其中 $l$ 為整數, $k = 0, 1, \dots, n$ . 當 $k=0$ 時即該點被標記, 否則即是沿著第 $k$ 個座標方向的兩個相鄰點之一被標記。

[Rendered in English:] Let $x_1, \dots, x_n$ be the coordinates of an integer point. Mark all points satisfying
$(2n + 1) \mid (x_1 + 2x_2 + \dots + nx_n)$
and this achieves the condition; for every point, $x_1 + 2x_2 + \dots + nx_n$ can be uniquely written as $(2n+1)l \pm k$ , where $l$ is an integer, $k = 0, 1, \dots, n$ . When $k=0$ , the point itself is marked; otherwise, it is one of the two adjacent points along the $k$ -th coordinate direction that is marked.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.