There are $85$ soldiers with different heigth and age. Every day commander chooses random soldier and send him and also all soldiers that are taller and older than this soldier, or all soldiers that are lower and younger than this soldier to color grass. Prove that after $10$ days we can find two soldiers, that color grass at same days.
Problem
Source: St Petersburg Olympiad 2013, Grade 10, P6
Tags: combinatorics
don2001
26.10.2017 12:49
Any full solution.
MessingWithMath
27.06.2019 05:01
Okay I will attempt to prove it using thedarklord's diagram, from which it appears that $82$ is optimal minimum bound of total soldiers: First, following his logic, we place each person on a cartesian plane, with their $(x,y)$ coordinate being their height and age. Each time a person is called, we can place an L shape an infinitesimal distance away from them oriented such that it either cuts the plane into all soldiers who are taller and older or lower and younger and always includes the soldier themselves. It is obvious that if two soldiers are in the same "region" of the plane after division, then they have the same schedule for every day. Now, we seek to prove that the maximal number of regions is $81$. We seek to prove by induction on $E$that $R=1+E+I$, where $E$ is the number of Ls, $I$ is the number of intersection points and $R$ is the number of regions. The base case of $E=1$ is trivial. Inductively, if we add an L which intersects at $n$ points, then we must show that 0the number of regions increases by $1+n$. This can be done by starting at one end of the L. Which ever region we are in has been cut into two. Now, following the L, every time we intersect another line, we go into a new region, which means this new region gets cut. It's obvious that these regions can't repeat since the lines are all straight. As a result, we are able to divide $n+1$ regions implying the result. Now we must notice that we wish to maximize the total number of intersection points to maximize the number of regions since $E=10$ is constant. Let $A$ be the number of Ls in one orientation and $10-A$ be the number in the other orientation. The number of intersections between two Ls of different orientations is $2(A)(10-A)$ and of the same orientation is ${A \choose 2} + {{10-A} \choose 2}$ which evaluates to $-A^2+10A+45$, which has a maximum at $A=5$ of $70$. Thus, the total number of regions is $70+10+1=81$. The original 10 people picked also exist in their own unique region because we pick the lines to be infinitessimally either down-left or up-right since no two people have the same age or height. By pigeonhole, at least 2 people will have to be in the same region and the result follows.