Very dirty ... But actually the solution only use induction and case division. Do you know any simple solution?

I used the following lemma: For a tournament $G(V,E)$, there exists a partition of $V= V_1 \cup \dots \cup V_k$ such that for each $i$ there exists a cycle passing all points of $V_i$, and for all $x\in V_i , y \in V_j, i<j \Longrightarrow (x,y)\in E(G)$. I've heard a lot of messy solutions, but I personally think this was the best problem of FKMO 2020.

deleted;;

proof sketch Let directed graph $G(V, A)$ such that $V$ is a group which consists a boy and a girl. For group $x, y \in V$, if boy of $x$ shakes hand with girl of $y$, we add arrow $x ->y $ in A. Then. we have to prove this statement. $\left| V \right|=2020$, and for every $x, y \in V$, there is at least one arrow. Then. we can find cycle with length $2019$, or there exist two point $x, y$ such that there are two path $P, Q$ which starts at $x$ and ends at $y$, and $P \cap Q=\left\{ x, y \right\}, P \cup Q=V$ We can do this with induction. However, if $n=3$, it doesn't satisfy. So we have to start with $n=4$.

I solved it with messy casework and using induction with the base case n=4

Nice solution @MNJ2357!

Messy caseworks aren't required if we use the following fact. Every tournament (directed graph based on a complete graph) has at least one Hamiltonian path. Construct a directed graph $G=(V,E)$ as follows: $V$ is a set of all groups (a boy + a girl) and $x\to y \in E$ if girl of $x$ shakes hand with boy of $y$. Fourth condition implies that $G$ is a tournament. Suppose $v_1 \cdots v_{2020}$ is a Hamiltonian path of $G$. ($v_i$ is a group consisted of a boy $b_i$ and a girl $g_i$.) If $v_1\to v_{2020}$, then $g_1 b_2 g_2 \cdots b_{2019} g_{2019} b_{2020}$ is a cycle of length $4038$ in the original shaking hands setting. If the Hamiltonian path was actually the Hamiltonian cycle, little bit of casework will end up the problem.

If we have a vertex $v, $ we can build its partition set by looking at all the vertex $w $ for which there is a cycle starting in $v , $ passing through $w.$ An equivalence relation. Then you have your set, and its clear that those sets satisfies are linearly ordered by the second hypothesis. Either all the members of set $A$ wins again all the members of $B,$ or vice versa. Else you can create a cycle originating in $A$ which goes to $B. $ Lemma Let $\mathcal{G}(V,E)$ be a tournament graph. There exists a partition of $V= V_1 \cap \dots \cap V_k$ such that for each $i$ there exists a cycle passing all points of $V_i$, and for all $x\in V_i , y \in V_j, i<j \Longrightarrow (x,y)\in E(\mathcal{G})$. This is the structure theorem for the tournament graphs. They all look like pre-orders that become linear orders when you quotient all the strongly connected components. Each component is itself hamiltonian, and the ordering on the components follows by a counting argument on the neighbourhoods of two vertices in $2$ different components. Any induced subgraph of a tournament is a tournament. Any strongly connected tournament is hamiltonian (giving cycle) The condensation of any tournament is a linear order is (giving the order)

deleted;;

WolfusA wrote:

If there's an edge $G_{2020}\rightarrow G_1$ , we can arrange students as length 4040. However, this problem wants to arrange students not 'at least 4038 students', but 'exactly 4038 students'. That's why this problem is hard.

Label the $2020$ groups $G_1, \ldots , G_{2020}$, each group $G_i$ with a boy and girl $b_i, g_i$. Draw a directed arrow from $G_a \to G_b$ if the boy from $G_a$ shook hands with the girl from $G_b$. The last condition tells us that there is a directed edge between any two groups, hence the graph on $G_1, G_2, \ldots , G_{2020}$ is a directed tournament. It is a fact that every directed tournament has a Hamiltonian path; WLOG this path is $G_1 \to G_2 \to \ldots \to G_{2020}$. We have a few cases: If any $G_i$ is directed to $G_{i+2}$, then we have a Hamiltonian cycle on $2019$ vertices, which finishes. Else, for any groups $G_i, G_{i+2}$, we have that the edge between them is directed from $G_{i+2} \to G_i$. Split cases again: If $G_{1}$ is directed to $G_{2020}$, then we need simply take $b_1G_2G_3\ldots G_{2019}g_{2020}$ which finishes. If $G_{2020}$ is directed to $G_1$, then this is a little more complicated. Recall that in this case, $G_{i+2} \to G_i$ for all $i$, hence $G_2 \to G_{2020}$ and $G_1 \to G_{2019}$. Thus, we may take\[b_2G_3G_4\ldots G_{2018}g_{2019}G_1G_{2020}\]which finishes. After exhausing all cases, we have found such needed $4038$ students in every case, so we are done. $\blacksquare$ Remark: I think a couple of people have mentioned methods similar to this above, but I don't think anybody has actually explicitly written it out.

Spacesam wrote: guys watch im a psychic and can predict the future: the great even-chan (venhance) will make a post on this completely random thread.

Solution: Define the tournament the same way jj_ca does, where $A_i$ contains $b_i$ the boy and $g_i$ the girl. Take a hamilton path, call $A_1\rightarrow A_2\rightarrow \cdots \rightarrow A_{2020}$. We have two cases. If $A_1\rightarrow A_{2020}$, then $b_1\rightarrow g_2\rightarrow b_2\rightarrow g_3\rightarrow \cdots \rightarrow g_{2020} \rightarrow b_1$ works. Notice how $b_{2020}$ and $g_1$ are not in the cycle. Otherwise, since a 2020-cycle exists, an 2019 cycle exists by the USA TST 09/6 lemma. Take $A_1\rightarrow A_2\rightarrow \cdots \rightarrow A_{2019} \rightarrow A_1$ and we have $g_1\rightarrow b_1\rightarrow g_2\rightarrow \cdots \rightarrow g_{2019} \rightarrow b_1\rightarrow g_1$ works.

Construct the directed graph the same way as jj_ca888. It is sufficient to show that there is either a (i) $2019$ cycle, or (ii) $2020$ cycle with exactly one edge traversed in the opposite direction (technically we just need the edges traversed in the opposite direction to be consecutive but we don't care). A classical result due to Rédei is that every tournament has a Hamiltonian path; let's say it is $G_1 \to G_2 \to \dots \to G_n$. If $G_1 \to G_n$, we are done since we have constructed (ii). Otherwise, $G_n \to G_1$, so, taking indices mod $2020$, if $G_i \to G_{i+2}$ for any $i$, we can simply take \[ G_1 \to G_2 \to \dots \to G_i \to G_{i+2} \to \dots \to G_{2020} \to G_1,\]which is a $2019$ cycle, i.e. we have constructed (i). Otherwise, $G_i \leftarrow G_{i+2}$ for all $i$. Now we again have two cases: if $G_1 \to G_{2018}$, then \[ G_{2019} \to G_{2017} \to \dots \to G_1 \to G_{2018} \to G_{2016} \to \dots \to G_2 \to G_{2020} \leftarrow G_{2019}.\]This is an instance of (ii), so we are done. Otherwise $G_1 \leftarrow G_{2018}$. Similarly we can find that if $G_2 \to G_{2019}$, then we can find an instance of (ii). Hence assume $G_2 \leftarrow G_{2019}$. But then \[ G_2 \to G_3 \to G_4 \to \dots \to G_{2018} \to G_1 \to G_{2019} \to G_2,\]is a $2019$ cycle. Therefore we have exhausted all cases, and are done. $\blacksquare$ Remark: I think jj_ca888's method is similar to this above, but I don't think it is actually explicitly the same.

A inductive proof which does not creates a directed graph: We more generally show that if there are $n$ groups, then there is a cycle of length $2n-2$. Base case $n=3$ is easy to handle. Now assume there are $k$ groups $\{a_1,b_1\},\{a_2,b_2\},\ldots,\{a_k,b_k\}$ which has a $2k-2$ length cycle $\mathcal C$ and we add another pair $\{a,b\}$ to get a graph $G$. Assume on the contrary that $G$ has no $2k$ length cycle. For any vertex $v \in G$, let $v_0$ denote the other vertex in the group of $v$ (for example $b = a_0$). Lemma: If $uv \in \mathcal C$ with $v \ne u_0$ and $ua \in G$, then we must have $vv_0 \in \mathcal C$ and $av_0 \in G$. Proof: We know at least one of $v_0a,vb \in G$. If $vb \in G$, then we can replace $uv \in \mathcal C$ by $u \to a \to b \to v$ which increases the length of $\mathcal C$ by exactly $2$, contradiction. Thus $v_0a \in G$. Now if $vv_0 \notin \mathcal C$, then we can replace $uv \in \mathcal C$ by $u \to a \to v_0 \to v$, which again increases the length of $\mathcal C$ by exactly $2$, contradiction. Thus $vv_0 \in \mathcal C$, which proves our Lemma. $\square$ As $\mathcal C$ has more than $\frac{k}{2}$ vertices, so we can choose some $u \in \mathcal C$ which is connected to either $a$ or $b$, say it is connected to $a$. Now since there are two edges passing through $u$ in $\mathcal C$, so there is $v \in \mathcal C$ with $v \ne u_0$ such that $uv \in \mathcal C$. Then our lemma gives $vv_0 \in \mathcal C$ and $av_0 \in G$. Continuing this way, we obtain that $\mathcal C$ must look something like $b_2a_2b_3a_3 \cdots b_ka_k$ and $ab_i \in G$ for all $i = 2,3,\ldots,k$. We similarly get that either $a_1b_i \in G$ for all $i = 2,3,\ldots,k$ OR $b_1a_i \in G$ for all $i = 2,3,\ldots,\mathcal C$. $a_1b_i \in \mathcal C$ for all $i = 2,3,\ldots,k$. We know at least one of $ab_1,ba_1 \in G$. Wlog, $ab_1 \in G$. Then we consider the $2k$ length cycle $$ab_1a_1 \cup (\mathcal C \setminus \{a_k\})$$ $b_1 a_i \in \mathcal C$ for all $i = 2,3,\ldots,k$. Again, one of $ab_1,ba_1 \in G$. If $ab_1 \in G$, then consider $$b_1a \cup \mathcal C$$If $ba_1 \in G$, then consider $$aba_1b_1 \cup (a_3b_3a_4b_4 \cdots a_kb_k)$$ This completes the proof of the problem. $\blacksquare$

Let $n = 2020$. Let $A_{1}, A_{2}, \dots, A_{n}$ be our groups, and let $b_{i}, g_{i}$ be boy and girl from group $A_{i}$. Let $G$ be directed graph with vertices $v_{1}, v_{2}, \dots, v_{n}$. Draw edge $v_{i} \to v_{j} \iff$ boy from $A_{i}$ shook hand to girl from $A_{j}$. Then $G$ becomes tournament. Thus we have a Hamiltonian path. WLOG, let $v_{1}\to v_{2}\to \dots \to v_{n}$ be a Hamiltonian path. Now divide 2 two case. Case 1: There is edge $v_{n} \to v_{1}$. Then $(v_{1}, v_{2}, \dots, v_{n})$ becomes Hamiltonian cycle. It's well known that we have directed cycle of length $n - 1$. Assume $(v_{1}, v_{2}, \dots, v_{n - 1})$ be a directed cycle of length $n-1$. Then $(g_{1}, b_{1}, g_{2}, b_{2}, \dots, g_{n - 1}, b_{n - 1})$ forms a cycle of length $2(n - 1) = 4038$. Case 2: There is edge $v_{1} \to v_{n}$ Then $(b_{1}, g_{2}, b_{2}, \dots, g_{n - 1}, b_{n - 1}, g_{n})$ becomes cycle of length $2(n - 1) = 4038$. Thus we're done. $\blacksquare$

wtf twitch lemma Construct a directed graph $G$ where vertices represent groups, drawing an edge $v \to w$ if the boy in $v$ shakes hands with the girl in $w$. The condition implies that any pair of vertices has at least one edge, and by deleting edges (i.e. removing extra handshakes) we can suppose in fact that every pair of vertices has exactly one edge, i.e. $G$ is a tournament. It is clear that we are done if we can find a cycle of length $2019$, or two paths that start and end at the same vertices, cover every vertex, go in the same direction, and are disjoint (phew). Take the maximal path of $G$ and let it be $v_1\ldots v_k$; I claim it is Hamiltonian, i.e. $k=2020$. Indeed, if it doesn't contain a vertex $w$, then we must have $v_1 \to w$ and $w \to v_k$, hence there exists some $i$ such that $v_i \to w \to v_{i+1}$. But then $v_1\ldots v_iwv_{i+1}\ldots v_k$ is a longer path: contradiction. Now if $v_1 \to v_{2020}$ then we have found two paths as before. Otherwise, we have a Hamiltonian cycle, and by the so-called "twitch lemma" it follows that we have a $2019$-cycle as well. $\blacksquare$

If I had to shake hands with $\frac{1009}{2}$ people I'd probably do some rather crazy things. Note that this is equivalent to having a bipartite graph $G'$ from boys $b_1, b_2, \dots, b_{2020}$ to girls $g_1, g_2, \dots, g_{2020}$ with a perfect matching $b_i$ and $g_i$ such that either $b_i$ and $g_j$ or $b_j$ and $g_i$ are connected for each $i, j$. Now, consider the directed graph $G$ where $v_i \to v_j$ if $b_i$ shook hands with $g_j$. It remains to show that $G$ has a cycle of length $2019$. Note that $G$ contains a directed copy of $K_{2020}$, giving a directed path of length $2020$ $v_{i_1} \to \dots \to v_{i_{2020}}$, which expands to a graph of $g_{i_1} \to b_{i_1} \to g_{i_2} \to \dots \to g_{i_{2020}} \to b_{i_{2020}}$. Since either $g_{i_1}$ is connected to $b_{i_{2020}}$ or $b_{i_1}$ is connected to $g_{i_{2020}}$, we are done.

Twitch Lemma wrote: Prove that if a tournament has no directed cycles of length $n \ge 3$, it does not have any directed cycles of length $n+1$ either. This is more or less the same as the proof of the statement that a tournament contains a Hamiltonian cycle iff its strongly connected, which in turn is the same as the proof of the key lemma that a tournament contains a Hamiltonian path, id est, take the largest H path and assume one vertex $u$ is left out, we say that a vertex in the path is painted red or blue depending on if $u$ is entering or leaving the vertex, thus the path can't be all blue or red otherwise you can jus extend it, but if it is not monochromatic, we can find two consecutive vertices with different colors (deep), so you can just extend it anyway. To solve the problem, consider the following interpretation, for groups $v$ and $w$ we say that $vw$ is an edge if the boy of $v$ shook hands with the girl of $w$, by the lemma we can find a Hamiltonian path and connect the terminal points according to what we need.

this should work as well