Let $k$ and $N$ be integers such that $k > 1$ and $N > 2k + 1$. A number of $N$ persons sit around the Round Table, equally spaced. Each person is either a knight (always telling the truth) or a liar (who always lies). Each person sees the nearest k persons clockwise, and the nearest $k$ persons anticlockwise. Each person says: ''I see equally many knights to my left and to my right." Establish, in terms of $k$ and $N$, whether the persons around the Table are necessarily all knights. Sergey Berlov, Russia
Problem
Source: 2019 RMM Shortlist C1
Tags: combinatorics
SnowPanda
11.12.2020 05:00
The people must all be knights if and only if $\gcd(N, 2k + 1) = 1$. This is true even without the conditions $k > 1$ and $N > 2k + 1$, where the $k$ people wrap around if $k > N$.
First, if $\gcd(N, 2k + 1) = d > 1$, then we can take $\frac{N}{d}$ copies of one knight followed by $d - 1$ liars. It suffices to prove this works for $N = d$, and we can replace $k$ with $\frac{d - 1}{2} \equiv k \pmod{d}$. Clearly the one knight sees $0$ liars on both sides, while each liar sees $1$ knight on one side and no knights on the other side.
Now we show if $\gcd(N, 2k + 1) = 1$, everyone is a knight. The idea is to show that the sequence is always periodic with period $2k + 1$.
First, we can create a sequence $a_i$ of $1$'s for knights and $0$'s for liars, extending it infinitely in both directions, and let $\ell_i$ and $r_i$ be the number of knights the $i$th person sees on their left and right.
We always have $$\ell_{i + 1} - r_{i + 1} = \ell_i - r_i + a_i + a_{i + 1} - a_{i - k} - a_{i + k + 1}$$(because when we move from $i$ to $i + 1$, $\ell_i$ gains $a_i$ and loses $a_{i - k}$, and $r_i$ loses $a_{i + 1}$ and gains $a_{i + k + 1}$).
If $a_i = a_{i + 1} = 1$, then $\ell_i = r_i$ and $\ell_{i + 1} = r_{i + 1}$, which means $a_{i - k} = a_{i + k + 1} = 1$.
[asy][asy]
unitsize(1 cm);
label("$K$", (0, 0));
dot((-1, 0));
dot((-2, 0));
dot((-3, 0));
label("$K$", (1, 0));
dot((2, 0));
dot((3, 0));
dot((4, 0));
draw((-3.3, 0.2)--(-3.3, -0.3)--(-0.7, -0.3)--(-0.7, 0.2), blue+linewidth(1));
draw((0.7, 0.2)--(0.7, -0.3)--(3.3, -0.3)--(3.3, 0.2), blue+linewidth(1));
draw((-2.3, 0)--(-2.3, -0.5)--(0.3, -0.5)--(0.3, 0.0), red+linewidth(1));
draw((1.7, 0)--(1.7, -0.5)--(4.3, -0.5)--(4.3, 0), red+linewidth(1));
draw((-3, 0.2)..(0.5, 0.7)..(4, 0.2), blue, EndArrow(TeXHead));
[/asy][/asy]
If $a_i = 1$ and $a_{i + 1} = 0$, then $\ell_i = r_i$ and $\ell_{i + 1} \neq r_{i + 1}$, which means $a_{i - k} + a_{i + k + 1} \neq 1$. So then either both are $0$'s or both are $1$'s. The case where $a_i = 0$ and $a_{i + 1} = 1$ follows similarly.
So then the only remaining case is when we have two consecutive $0$'s.
Claim: We always have $|\ell_i - r_i| \leq 1$.
Proof: First, $\ell_i - r_i = 0$ at all $i$ which have knights, so then by the above formula, $\ell_i - r_i = \pm 1$ at all $i$ which have a liar, and one of the adjacent people is a knight. So then the only relevant cases are where we have a stretch of liars, with a knight on both ends.
However, if we have liars from $a_m$ to $a_n$, then $|\ell_m - r_m| = |\ell_n - r_n| = 1$. But $\ell_i - r_i$ can't increase between consecutive $i$, which means its value must always remain between $-1$ and $1$.
Now if we have $a_i = a_{i + 1} = 0$, then we must have $\ell_i - r_i = \pm 1$, and $a_{i - k} \neq a_{i + k + 1}$ would take the difference to either $0$ or $\pm 2$, neither of which is allowed. So in this case again we have $a_{i - k} = a_{i + k + 1}$.
This covers all cases, so the sequence has period dividing $2k + 1$ and we're done.
CANBANKAN
15.05.2022 01:42
The answer is $\gcd(N,2k+1)=1$ only.
Let $a_1,\cdots,a_N$ such that $a_j=1$ if the $j$th person in the circle is a knight and $a_j=0$ otherwise. Indices are taken mod $N$.
First, I prove if $\gcd(N,2k+1)>1$ then there is a counterexample. Let $d=\gcd(N,2k+1), a_j=1$ if and only if $d\mid j$. We check it works:
If $d\mid k$ then there are precisely $\frac{\frac{2k+1}{d}-1}{2}$ on both sides
Otherwise, suppose $R(k,d)<\frac d2$ (since $d$ is odd equality cannot occur). Then check left hand side has $\frac{\frac{2k+1}{d}+1}{2}$ 1's and right hand side has $\frac{\frac{2k+1}{d}+1}{2}$
It remains to show all $\gcd(N,2k+1)=1$ work. The key is to prove $a_j$ has period $N$ and $2k+1$ by analyzing a continuous gap of $0$'s.
Claim: If $a_j=1$ then $a_{j+k+1}=a_{j-k}$ and $a_{j+k}=a_{j-k-1}$
Proof: Casework on $a_{j+1}$ to prove $a_{j+k+1}=a_{j-k}$.
$a_j=a_{j+1}=1$. This implies $a_{j-k}+\cdots+a_{j-1}=a_{j+1}+\cdots+a_{j+k}$ and $a_{j-k+1}+\cdots+a_j = a_{j+2}+\cdots+a_{j+k+1}$. This means $a_{j+k+1}-a_{j+1}=a_j-a_{j-k}$ so $a_{j+k+1}=a_{j-k}=1$. If $a_j=1, a_{j+1}=0$, we similarly get $a_{j+k+1}-a_{j+1}\ne a_j-a_{j-k}$. Rearranging, $a_{j+k+1}+a_{j-k}\ne a_{j+1}+a_j=1$ so $a_{j+k+1}=a_{j-k}$ if $a_j=1$ or $a_{j+1}=1$
Let $f(j)=a_{j-k}+\cdots+a_{j-1} - a_{j+1} - \cdots - a_{j+k}$
Observe $f(j+1)-f(j)=a_j+a_{j+1}-a_{j-k}-a_{j+k+1}$
Suppose $j<l, a_j=a_l=1, a_{j+1}=\cdots=a_{l-1}=0$.
Then $0=f(l)-f(j)=\sum\limits_{k=j}^{l-1} (f(k+1)-f(k))=(a_j+a_{j+1})+(a_{j+1}+a_{j+2})+\cdots + (a_{l-1}+a_l)- (a_{j-k}+a_{j+k+1}) - \cdots - (a_{l-k-1} + a_{l+k})$
Observe $(a_j+a_{j+1})+(a_{j+1}+a_{j+2})+\cdots + (a_{l-1}+a_l)=2$ so it follows that $(a_{j-k}+a_{j+k+1}) + \cdots + (a_{l-k-1} + a_{l+k})=2$ as well.
We verify with casework that either $a_{j-k}=a_{j+k+1}=1$ or $a_{l-k-1}=a_{l+k}=1$; by our claim, $a_{j-k}=a_{j+k+1}$ and $a_{l-k-1}=a_{l+k}$. If both are zero, then notice $f(j+1)=-1$. We can see $a_{t+k+1}$ or $a_{t-k}=0$ for some $j<t<l$, so $f(t)=0$.
It follows that for all $j$, $a_{j+k+1}=a_{j-k}$, so $a$ is periodic with period $\gcd(N,2k+1)$, implying $a_j=1$ for all $j$, the end.