There are two airlines A and B and finitely many airports. For each pair of airports, there is exactly one airline among A and B whose flights operates in both directions. Each airline plans to develop world travel packages which pass each airport exactly once using only its flights. Let $a$ and $b$ be the number of possible packages which belongs to A and B respectively. Prove that $a-b$ is a multiple of $4$. The official statement of the problem has been changed. The above is the form which appeared during the contest. Now the condition 'the number of airports is no less than 4'is attached. Cite the following link. https://artofproblemsolving.com/community/c6h2923697p26140823
Problem
Source: Korean junior mathematical olympiad 2019 December
Tags: combinatorics, graph theory, Hamiltonian path, KJMO
seoneo
17.11.2019 11:40
There's some issue for this problem. Let $n$ be the number of airports. We may need the restriction $n \ge 4$.
Letteer
20.11.2019 02:37
This result appears to be false. Example 1. Let R,S,T,U be airports with Airline A operating in both directions between R&S, S&U and U&T, and Airline B operating in both directions between the other three pairs of airports. In addition, let Airline A operate flights from U to R and S to T. Then Airline B has $0$ possible world travel packages. (Assuming it requires a closed path visiting each airport precisely once.) Airline A has $1$ possible world travel package U-R-S-T-U. (If you count this as 4 packages then see Example 2.) Example 2. Let R,S,T,U,V be airports with Airline A operating in both directions between R&S and V&R and Airline B operating in both directions between all the other pairs of airports. In addition, let Airline A operate flights from s to T,T to U and U to V. Then Airline B has $0$ possible world travel packages. (Assuming it requires a closed path visiting each airport precisely once.) Airline A has $1$ possible world travel package R-S-T-U-V-R. You may wish to count this as 5 packages. (If $a$ and $b$ count Hamiltonian paths not cycles then see Example 3.) Example 3. Let R,S,T,U be airports with Airline A operating in both directions between all pairs of airports and Airline B only operating flights from R to S and S to T and T to U. Then $a=4!$ and $b=1$.
MNJ2357
21.11.2019 11:15
Letteer wrote: ... $a,b$ is the number of Hamiltonian paths, not cycles.
Letteer
21.11.2019 18:15
MNJ2357 wrote: Letteer wrote: ... $a,b$ is the number of Hamiltonian paths, not cycles. I have added a counterexample for the case of Hamiltonian paths.
MNJ2357
21.11.2019 18:28
Oh now I see that the problem is a little confusing. The problem is about a complete graph with each edge colored with either red or blue.
Letteer
23.11.2019 03:08
The rules of the problem are this. For some $n$, the edges of the undirected complete graph, $K_n$, are each colored red (for airport $A$) or blue (for airport $B$). Letting a be the number of Hamiltonian paths of the red graph, and b be the number of Hamiltonian paths of the blue graph, prove $a-b\equiv 0\pmod 4$. In your example $3$, you have unidirectional edges (not allowed), and the edge {$R,S$} is shared by both airports (exactly one airport owns each edge).
We shall also adopt the convention of considering paths $v_1 v_2 ... v_i$ and $v_i ... v_2 v_1$ to be distinct.
Preliminary result: Let $E$ be any set of edges in $K_n$. If $|E|<n-1$ then the number of Hamiltonian paths using all the edges of $E$ is a multiple of $4$.
We can assume the edges of $E$ are part of at least one Hamiltonian path otherwise we are finished. Let the graph on $E$ have $c$ components and $n-v$ vertices. For each arrangement of the components and the extra $v\ge 2$ vertices in a line we can permute the components and the vertices in $(c+v)!$ ways and this will be divisible by 4 unless $c=1, v=2$.
In the latter case, the component has more than one vertex and so has two orientations. For each of these there are six placings for the extra vertices giving 12 Hamiltonian paths in total.
Proof that $a\equiv b \mod 4$.
Let the edges of $K_n, n\ge 4$ be partitioned as $X\cup R \cup B$ where $R$ and $B$ are edges coloured red and blue, respectively.
Given that the edges of $X$ are coloured blue, define $N_B(X,R,B)$ to be the number of Hamiltonian paths in the blue graph which must use the edges of $X$. Given that the edges of $X$ are coloured red, define $N_R(X,R,B)$ to be the number of Hamiltonian paths in the red graph which must use the edges of $X$.
The result we need to prove is therefore $N_R(\phi,R,B)-N_B(\phi,R,B)\equiv 0 \mod 4$
General result $N_R(X,R,B)-N_B(X,R,B)\equiv 0 \mod 4$
We shall proceed by induction on $|B|$.
Let $e$ be any edge of $B$. Then, by considering paths using and not using $e$ we see that $$N_B(X,R,B)=N_B(X\cup \{e\},R,B/\{e\})+N_B(X,R\cup \{e\},B/\{e\})$$Similarly $$N_R(X,R\cup \{e\},B/\{e\})=N_R(X\cup \{e\},R,B/\{e\})+N_R(X,R,B)$$
The quantity $N_R(X,R,B)-N_B(X,R,B)$ is therefore given by the difference of two quantities of the same form but with smaller $|B|$. It is therefore sufficient to prove the result when $|B|=0$.
If $|X|\ne n-1$ then $N_B(X,R,\phi)=0$ and the result follows from the Preliminary result. So suppose $|X|= n-1$. Then $N_R(X,R,\phi)=N_B(X,R,\phi)$ is $2$ or $0$ depending upon whether the edges of $X$ form or do not form a Hamiltonian cycle.
CBMaster
15.11.2024 08:53
Like senior's problem #8 in 2019 Korean math olympiad, this is well known result about hamiltonian cycle, originally proved by T. Szele. See《Combinatorial Problems and Exercises》, Chapter 5, Problem 19 for the Szele's solution.