Each two of $n$ students, who attended an activity, have different ages. It is given that each student shook hands with at least one student, who did not shake hands with anyone younger than the other. Find all possible values of $n$.
Problem
Source: Turkey TST 2017 Problem 4
Tags: combinatorics, graph theory
08.04.2017 01:12
Consider each person as a vertex on a graph. Draw the directed graph where each person sends (exactly one) arrow to the youngest person whose hands they have shaken. By the condition (surjectivity) and the fact that the function is defined, we see that this must be a permutation digraph, and furthermore there are no fixed points (consequent of the fact that no one shakes their own hand). It is well-known that the graph admits a partition into directed cycles. It suffices to prove the theorem for cyclic graphs, as disjoint cycles cannot "talk" to each other. By considering the extremally young vertex, and the absence of self-directed vertices, it follows that the only cyclic digraph that can satisfy the condition is that with two vertices. We conclude that the answer is $\boxed{n\text{ even}}$. (Construction is obvious).
08.04.2017 18:21
can anyone explain in non graph theoretic language?
10.04.2021 23:00
Solution without Graph Theory by Mehmet Burak Gönül (same idea though) I will number students as $1, 2, \dots n$ and let their ages be $1, 2, \dots n$ respectively. Besides I will use "friendship" instead of "shaking hands" For even $n$, take student pairs $1-2, 3-4, \dots (n-1)-n$ and let them be friends. Clearly this works. Now I will define a function and a set to prove that $n$ cannot be odd. With function $f$, for student $a$, let the youngest friend of $a$ be $f(a)=x$. With set $S_a$, I will show the people who are friends of $a$ and are not friends of anyone else younger and for every $a$ we know $|S_a| \ge 1$. Because of the condition, $f(a)=x \Leftrightarrow a \in S_x$. If for $i \neq j$, there exists a $b$ such that $b \in S_i \cap S_j$, then $f(b)=i=j$. Contradiction. Thus, every $b$ is in exactly one $S$ and since every $S$ contains at least one element, we have that each one of $1, 2, \dots n$ appears exactly in one $S$ and this gives us $f$ is bijective. Now take the student $1$ and realize that it cannot have more than one friend because if it had, we would have $f(x)=f(y)=1$ for some $x \neq y$, contradiction. Let this friend be $x$. From the conclusions we had, $x$ is not an element of sets except $S_1$ and $1$ is not an element of sets except $S_x$. Hence, we can take these students out from the group and with similar moves we result in one student who doesn't satisfy the conditions.
04.09.2023 23:30
Suppose each student $s$ shook hands with $f(s)$. Note that $f(s)$ is injective by the age condition and thus bijective. Now consider the graph with the vertices being the students and directed edges $s \to f(s)$. Let $g(s)$ be the age of $s$. Notice that $g(s) \leq g(f(f(s))$, which implies that the only possible cycle lengths in this graph are of length $2$. Thus, $n$ must necessarily be even, and we can easily construct $\frac n2$ pairs of disjoint friendships in that case.
16.02.2024 09:35
Let the age of the students be $1,2,\ldots,n$. Number the students according to their ages. We claim that all even $n$ work. A construction for the same is as follows: $1\leftrightarrow2,3\leftrightarrow4,\cdots,(n-1)\leftrightarrow n$. We now show that $n$ cannot be odd. For each student $s$, let $g(s)$ denote the student $t$ where $g:\text{student set}\rightarrow\text{student set}$ is a function. Claim: $g(s)$ is injective, and hence bijective. Proof. Suppose there are students $r$ and $s$ having the same image in $g$. Note that $r$ is a friend of $g(s)$, so $r$ is older than $s$. Similarly, $s$ is older than $r$ as it is a frienf of $g(r)$. This is absurd. So, $g(r)=g(s)\Rightarrow r=s$. Consider the directed graph $G$ on $n$ vertices, such that directed edge $s\rightarrow t$ exists if and only if $t=g(s)$. Claim: $G$ is composed entirely of $2-$cycles. Proof. Clearly, $G$ cannot have a loop. Suppose $G$ has a directed cycle of length $m>2$ consisting of students $s_1,s_2,\ldots,s_m$. Then, $s_{i+1}$ is the friend of $g(s_{i-1})$, so $s_{i+1}>s_{i-1}$ for each $i$, if indices are taken $\pmod{m}$. It follows that $s_{i+2}>s_i$. However, taking this $m$ times, we get $s_i=s_{i+2m}>s_i$ which is again absurd. This however does not work for $m=2$ as $s_{i+1}$ and $s_{i-1}$ are the same students. From our claim, it follows that $g(g(s))=s$ for all $s$, which means there are a total of $\frac n2$ cycles in $G$. So, $n$ must be even.