Let $k$ be a fixed integer. In the town of Ivanland, there are at least $k+1$ citizens standing on a plane such that the distances between any two citizens are distinct. An election is to be held such that every citizen votes the $k$-th closest citizen to be the president. What is the maximal number of votes a citizen can have? Proposed by Ivan Chan Kai Chin
Problem
Source: Own. Malaysian APMO CST 2023 P4
Tags: combinatorics
20.02.2023 08:58
The answer is $5k$. Lemma 1: Given $n$ points (not necessary distinct) $P_1, \dots, P_n$ on the complex plane, for any $\epsilon>0$, $\exists P_1', \dots, P_n'$ s.t. $\forall i,\ |P_i'-P_i|<\epsilon$ and the distances between any $2$ points are not $0$ and all different. Proof: Let's choose $P_1', P_2', \dots$ one by one s.t. when choosing $P_i'$, the distances between any $2$ points among $P_1', \dots, P_i'$ are different. This can be done since when choosing $P_i'$, the points that cannot be chosen is in the union of finitely many arcs, which can't cover the circle $\{z:|z-P_i|<\epsilon\}$. Construction: A citizen is at $0$, and for all roots of $x^5-1$, there are $k$ citizen at there. By the lemma 1, we can move each citizen to a new place that the distance to the original place $<\epsilon$, s.t. the citizens stand at distinct points and the distances between any two citizens are distinct. Take $\epsilon=10^{-9}$, and we can see that the $5k$ citizens that stand at some roots of $x^5-1$ vote to the citizen standing at $0$. Answer is at most $5k$: Suppose the opposition that at least $5k+1$ citizens $P_1, P_2, \dots, P_{5k+1}$ vote to a citizen $P_0$. WLOG suppose $|P_1-P_0|>|P_2-P_0|>\cdots>|P_{5k+1}-P_0|$. Let $S_i:=\{j:|P_i-P_j|<|P_i-P_0|\}$, and we know that $\forall i,\ |S_i|\leq k-1$. Lemma 2: If $i<j$ and $j\notin S_i$, then $i\notin S_j$. Proof: $j\notin S_i: |P_i-P_j|>|P_i-P_0|$ $i<j: |P_i-P_0|>|P_j-P_0|$ $\Rightarrow|P_j-P_i|>|P_i-P_0|>|P_j-P_0|$ $\Rightarrow i\notin S_j$ by definition. Let $a_1=1$, $a_{n+1}:=\min\{i:1\leq i\leq5k+1, i\notin S_1\cup\cdots\cup S_n\}$. We can see that $a_1, \dots, a_6$ are well-defined since $|S_1\cup\cdots\cup S_n|\leq nk<5k+1\ (\forall n\leq5)$. By Lemma 2, $\forall1\leq i<j\leq6,\ a_i\notin S_{a_j},\ a_j\notin S_{a_i}$. $\Rightarrow\forall1\leq i<j\leq6,\ |P_{a_i}-P_{a_j}|>|P_{a_i}-P_{a_j}|>|P_{a_j}-P_0|,\ \angle P_{a_i}P_0P_{a_j}>60^o$. Sort $P_{a_1}, \dots, P_{a_6}$ by their principal arguments, and get $Q_1, \dots, Q_6$. $360^o=\angle Q_1P_0Q_2+\angle Q_2P_0Q_3+\cdots+\angle Q_5P_0Q_6+\angle Q_6P_0Q_1>60^o\times6=360^o$, contradiction. $\therefore$ we've finished the proof.
10.09.2023 18:40
https://youtu.be/chj_q0_lz7g subscribe!
10.09.2023 20:10
Official solution (Credits to Anzo for the write up!) We first provide an example where a center point, $O$, has exactly $5k$ "votes''. Indeed, consider a regular pentagon $P_1\cdots P_5$ with center $O$ and radius 1, and consider a circle with radius $\epsilon > 0$ (but small) centered around (each) $P_i$ and $k$ points $Q_{i1}, \cdots, Q_{ik}$ on the circle, placed in arbitrary fashion. Note that $P_iOP_j\ge 72^{\circ}$ for all $i\neq j$, so $P_iO < P_iP_j$ whenever $i\neq j$. Then as long as $\epsilon$ is small enough, for each $i\neq j$ and $1\le \ell_1 \neq \ell_2\le k$ we have $Q_{i\ell_1}Q_{i\ell_2} < Q_{i\ell_1}O < Q_{i\ell_1}Q_{j\ell_2}$, so the system of $O$ and $Q_{i\ell}$ for $i=1, \cdots, 5$ and $\ell=1, \cdots, k$ has $O$ getting votes from all the $Q_{i\ell}$'s. Now to establish the bound, we use the following identity: if $ABC$ is such that $\angle B \le 60^{\circ}$, then $\max \{BA, BC\}\ge AC$. Indeed, $$AC^2 = BA^2 + BC^2 - 2BA\cdot BC\cdot \cos\angle B\le BA^2 + BC^2-BA\cdot BC\le \max \{BA, BC\}^2$$Let $O$ be any center point and $P_1, \cdots, P_n$ be points that voted for $O$. W.l.o.g. suppose $OP_1 > OP_i$ for all $i\neq 1$. From our claim above, if $OP_1 < P_1P_i$ for some $i$, then $\angle P_1OP_i > 60^{\circ}$. Consider the region $\mathcal{R} = \{P: \angle POP_1 \le 60^{\circ}\}$, then at most $k$ of the $P_i$'s (including $P_1$ itself) is in $\mathcal{R}$. Such region $\mathcal{R}$ subtends an angle of $120^{\circ}$ from $O$ (symmetric with respect to the ray $OP_1$). We now show that there cannot be more than $4k$ $P_i$'s in $\mathcal{R}^c$ (i.e. the complement). Suppose otherwise, we may w.l.o.g. relabel them as $Q_1, \cdots, Q_m$ in that order (order according to the angle bearing of the line $Q_iO$). If $m\ge 4k+1$, then $\angle Q_{ak+1}OQ_{(a+1)k+1}\le 60^{\circ}$ for some $a\in \{0, 1, 2, 3\}$. Consider $Q_{ak+1}, \cdots, Q_{(a+1)k+1}$, and let $Q_j$ be the one among these furthest from $O$. Since $Q_jOQ_{\ell} < 60^{\circ}$ for all $\ell=ak+1, \cdots, (a+1)k+1$, we have $Q_jO > Q_jQ_{\ell}$ for $\ell=ak+1, \cdots, (a+1)k+1$ with $\ell\neq j$, implying that $O$ is ranked at least $k+1$ in distance from $Q_j$ (hence contradiction). $\blacksquare$