AoPS - Problem

Source: Ukrainian mathematical olympiad 2018 11.5

Tags: combinatorics

Mindstormer

22.07.2018 21:37

The squadron of $10$ powerful destroyers and $20$ small boats is about to attack the island. All ships are positioned on the straight line, and are equally spaced. Two torpedo boats with $10$ torpedoes each want to protect the island. However, the first torpedo boat can shoot only $10$ successive boats, whereas the second one can shoot $10$ targets which are next by one. Note that they have to shoot at the same moment, so that some targets may be hit by both torpedoes. What is the biggest number of destroyers that can avoid the torpedoes no matter which targets the torpedo boats choose? Proposed by Bohdan Rublyov

We will prove, that answer is $3$. Give numbers $1,2,3,...,30$ to ship positions. Divide it to groups $A_1=(1,2,...,10),A_2=(11,12,...,20),A_3=(21,...,30)$. If there are more than $2$ destroyers in $A$ or in $C$ then first torpedo boat shoot in this group, and second shoot to others, such that try to hit maximal number of destroyers. They both will hit not less than $x+\lceil \frac{10-x}{2} \rceil \geq 7$. If there are are less than $3$ destroyers in $A$ and $C$, then first boat shoot in $B$, and second in $A$ or $C$ in some destroyer. They will hit not less than $7$ destroyers. Set destroyers in $1,4,7,14,15,16,17,24,27,30$. Easy to show, that boats cannot hit more than 7.