Competition problem — Combinatorics

Library / /26 of 64

Combinatorics Difficulty 7.8 National olympiad, round 2 Find the answer

Let $\mathbb{Z}^n$ be the integer lattice in $\mathbb{R}^n$ . Two points in $\mathbb{Z}^n$ are called $\emph{neighbors}$ if they differ by exactly $1$ in one coordinate and are equal in all other coordinates. For which integers $n \geq 1$ does there exist a set of points $S \subset \mathbb{Z}^n$ satisfying the following two conditions? $\text{[(1)]}$ If $p$ is in $S$ , then none of the neighbors of $p$ is in $S$ . $\text{[(2)]}$ If $p \in \mathbb{Z}^n$ is not in $S$ , then exactly one of the neighbors of $p$ is in $S$ . $\text{}$

Your answer

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

Solution

Such a set exists for every $n$ . To construct an example, define the function $f: \mathbb{Z}^n \to \mathbb{Z}/(2n+1) \mathbb{Z}$ by $f(x_1,\dots,x_n) = x_1 + 2x_2 + \cdots + nx_n \pmod{2n+1},$ then let $S$ be the preimage of 0.

To check condition (1), note that if $p \in S$ and $q$ is a neighbor of $p$ differing only in coordinate $i$ , then $f(q) = f(p) \pm i \equiv \pm i \pmod{2n+1}$ and so $q \notin S$ .

To check condition (2), note that if $p \in \mathbb{Z}^n$ is not in $S$ , then there exists a unique choice of $i \in \{1,\dots,n\}$ such that $f(p)$ is congruent to one of $+i$ or $-i$ modulo $2n+1$ . The unique neighbor $q$ of $p$ in $S$ is then obtained by either subtracting $1$ from, or adding $1$ to, the $i$ -th coordinate of $p$ .

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.