At an IMOTC party, all people have pairwise distinct ages. Some pairs of people are friends and friendship is mutual. Call a person junior if they are younger than all their friends, and senior if they are older than all their friends. A person with no friends is both junior and senior. A sequence of pairwise distinct people $A_1, \dots, A_m$ is called photogenic if: 1. $A_1$ is junior, 2. $A_m$ is senior, and 3. $A_i$ and $A_{i+1}$ are friends, and $A_{i+1}$ is older than $A_i$ for all $1 \leq i \leq m-1$. Let $k$ be a positive integer such that for every photogenic sequence $A_1, \dots, A_m$, $m$ is not divisible by $k$. Prove that the people at the party can be partitioned into $k$ groups so that no two people in the same group are friends. Proposed by Shantanu Nene
Problem
Source: India IMOTC 2024 Day 2 Problem 3
Tags: combinatorics, graph theory
31.05.2024 08:27
31.05.2024 16:27
Introduce a directed graph $G$ with vertices $V$ representing the set of people. Put a directed edges $\overrightarrow{uv}$ between $u,v\in V$ if $u,v$ are friends and $v$ is older than $u$. According to the statement, $G$ is an acyclic graph. We can arrange its vertices as $v_1,v_2,\dots,v_n$ such that if $\overrightarrow{v_iv_j}$ is an edge then $i<j$. Let $V_0$ be the set of vertices of $G$ which have only out-bounded edges. We assign to each vertex $v\in V$ a set $S(v)$ of residues modulo $k$ as follows. We take the family $\mathcal{F}(v)$ of all possible directed paths starting from $v_0\in V_0$ and ending in $v$ and set $$S(v):= \{\text{length of } P \text{ modulo } k : P\in \mathcal{F}(v)\}, \forall v\in V\setminus V_0$$and $S(v):=\{0\}$ for $v\in V_0$. We assign to all vertices in $v_0,v_1,\dots,v_r\in V_0$ color $0$. We will prove that starting from $i=r+1$ we can assign to $v_i$ a color (number) $\ell$ such that $\ell \in S(v_i)$ and for all direct edges $\overrightarrow{v_jv_i}, j<i$, $v_j$ is colored in color that differs from $\ell$. Assume the opposite. We'll prove that $S(v_i)$ consists of all residues modulo $k$. Indeed, take $\ell\in S(v_i)$. Then there exists $v_j, j<i$ such that $v_j$ is colored in $\ell$ and $\overrightarrow{v_jv_i}$ is edge. Then, by the mere definition $\ell+1\pmod k\in S(v_i)$. In the same way $\ell+2\pmod k\in S(v_i)$ and so on, thus $S(v_i)$ consists of all residues modulo $k$. But this is impossible since otherwise there would exist maximal paths of all possible lengths modulo $k$, contradiction. Therefore, starting from $i=r+1$ we'll color properly all the vertices of $G$ in no more than $k$ colors. Remark. I saw that it's the same as in #2, but it was already written, so I post it. As a motivation, for me it was not straightforward to get to this argument. It's very logical to enumerate the vertices like that and try to color them one after another. It's also logical to track the lengths of paths that start from $V_0$ and end into a vertex $v$, especially their residues modulo $k$ . First, I tried to map two lists of residues to each vertex - number of paths from $V_0$ to $v$ and from $v$ to a terminal vertex. After some play, the final idea was cleared.
02.06.2024 14:34
A few remarks: The statement is true, and the same proof follows through, even if vertex-lengths of photogenic paths miss any one residue modulo $k$ (not just $0$). This is a generalization of (one direction of) the Gallai-Hasse-Roy-Vitaver Theorem, with the residue missed being $1$ (for graphs without isolated vertices). There exist vertex-weighted graphs such that the chromatic number does not divide the vertex-length of any photogenic path. Indeed, take any weighted complete graph with $k$ vertices $H$, and attach an increasing path with $k-1$ vertices (each having sufficiently large weight) to the vertex with the largest weight in $H$. The length of any photogenic path will then be in the set $\{k+1,k+2, \dots, 2k-1\}$. I don't know for which (unweighted) graphs $G$ the following form of converse is true: There exists a vertex-weighting with distinct (real) weights such that the vertex-length of any photogenic path is not divisible by $\chi(G)$. It is true for some graphs as shown above, and false for others, like the complete graph. However, if we replace vertex-length by just length, it is always true, as can be seen by the other direction of the Gallai-Hasse-Roy-Vitaver Theorem. All colorings that we could come up with basically followed the ideas in the second post (coloring based on all paths that lead up to the vertex). It seems that any other idea fails. For instance, the greedy algorithm of ordering the vertices according to weight and coloring with the smallest color unavailable fails to the following graph (with $k=3$, and vertices labelled $3$ and $??$ having higher weight than all others):
Attachments:

04.06.2024 00:50
Reparameterize the problem in terms of rivers. Call juniors sources and call seniors sinks. Call the vertices rivers and call younger friends tributaries. As for my two cents on motivation, it was looking at the contrapositive and the fact that a path of length $k$ is forced by pigeonhole the same time a coloring fails by pigeonhole; ie see Brooks's theorem. A heuristic against any local argument is the fact that you can arbitrarily attach new vertices to the beginning / end of the path -- the forcing of an existence of a path of length $k$ must be invariant under that. Take the obvious graph theory interpretation on a DAG. Suppose that a $k$-coloring is impossible. We now show a path of length divisible by $k$ must exist. We now assign residues $\pmod k$ to rivers inductively as follows. First, assign a residue of $1 \pmod k$ to headwaters. Next, for a river whose tributaries have all been assigned residues $S$, we assign it a residue $r$ such that $r \not\in S$ and $r-1 \in S$. We repeat this process while $S \ne {\mathbb Z}/k{\mathbb Z}$. Claim: No river has the same residue as any of its tributaries. If a river has residue $n$, there is a path of length $n \pmod k$ to some source. Proof. The first claim follows by construction. For the second, attach to each river a path inductively by taking the path of a tributary with residue $r-1$ and appending the river to it. Then this works inductively as well. $\blacksquare$ Now, if $S$ is never ${\mathbb Z}/k{\mathbb Z}$, then this gives a coloring by residue, contradiction. As such, when $S$ is ${\mathbb Z}/k{\mathbb Z}$ at some river $r_1$, then suppose that $r_1$ has a path $r_1, r_2, \dots, r_l$ to the ocean. Then take the path with a tributary with residue $-l \pmod{k}$. This gives a path of length divisible by $k$ as desired.