In La-La-Land there are 5784 cities. Alpaca chooses for each pair of cities to either build a road or a river between them, and additionally she places a fish in each city to defend it. Subsequently Bear chooses a city to start his trip. At first, he chooses whether to take his trip in a car or in a boat. A boat can sail through rivers but not drive on roads, and a car can drive on roads but not sail through rivers. When Bear enters a city he takes the fish defending it, and consequently the city collapses and he can't return to it again. What is the maximum number of fish Bear can guarantee himself, regardless of the construction of the paths? Remarks: Bear takes a fish also from the city he begins his trip from (and the city collapses). All roads and rivers are two-way.
Problem
Source: 2024 Israel Olympic Revenge P3
Tags: olympic revenge, combinatorics
06.09.2024 04:51
Let $n=1928,$ $5784=3n.$ Graph theory version is as follows: Quote: Colour edges of $K_{3n}$ with two colors red or blue, what is the largest $\ell,$ such that we can find a monochromatic path with size $\ell$ in any case. The answer is $2n+1.$ Construction: take $|V_1|=2n,|V_2|=n.$ Define the colour of edge $vw$ as follows: $$c(uv):=\begin{cases}1& v,w\in V_1\\2 &\text{otherwise}\end{cases}.$$Observe that the maximum length of monochromatic path is $2n+1.$ ($v_1,v_3,\ldots ,v_{2n+1}\in V_1,$ $v_2,v_4,\ldots ,v_{2n}\in V_2.$) Proof: I first saw this on a lesson by teacher Xiaomin Chen(陈晓敏), the main idea is induct from $3n$ to $3n+3,$ and take the longest monochromatic path in $K_{3n},$ and try to give contradiction. Full solution can be found in attached file, by L.Gerencser and A.Gyarfas. in 1967.
Attachments:
On Ramsey-Type Problems.pdf (208kb)