Vlad draws 100 rays in the Euclidean plane. David then draws a line $\ell$ and pays Vlad one pound for each ray that $\ell$ intersects. Naturally, David wants to pay as little as possible. What is the largest amount of money that Vlad can get from David? Proposed by Vlad Spătaru
Problem
Source: 2024 Nepal TST, P4 and The Golden Digits Contest, April 2024, P1
Tags: combinatorics, geometry, game
25.04.2024 14:51
We will prove that the required maximum is 49. For every configuration $C$ of 100 rays in plane we note with $M_C$ the amount of money that David pays to Vlad (It is known that David draws $l$ so that $M_C$ is minimal). We will prove that $M_C \leq 49$ for any configuration C of 100 rays in the plane. WLOG : Let $r_1$ be the first ray and assume that it is in a vertical position. Let $l_1$ the support line of radius $r_1$ that divides the plane into two half-planes. How we have at most 99 non-parallel rays with $r_1$ thus there is a half-plane between the two determined by $l_1$ such that at most 49 non-parallel rays with $l_1$ intersect this half-plane in a half-line. Let this half-plane be the one on the left of the line $l_1$.Thus there is a line $l_0$ parallel to $l_1$ sufficiently to the left such that it intersects at most 49 rays out of the 100 drawn by Vlad. So $M_C \leq 49$. Now we will find a configuration C for which $M_C$=49. Let there be 50 straight lines that pass through the origin of the plane. Obviously any 2 of them are different and non-parallel. Thus they form a configuration $C$ with 100 rays starting from the origin of the plane .And we will have $M_C$=49.
25.04.2024 15:47
@above I don't follow your construction of C for which $M_c$ is 49. Can you illustrate it a bit?
25.06.2024 13:19
The answer is $49$ pounds. Firstly, note that Vlad can win least $49$ pounds if the $100$ rays are split into pairs, thus forming $50$ non-parallel lines. David's line will be parallel to at most one of Vlad's lines and will intersect all the others: thus, $\ell$ intersects at least $49$ rays. Next, we will show that regardless of the way Vlad draws the $100$ rays, David can draw a line $\ell$ which intersects at most $49$ rays. Fix a point $O$ in the plane and consider a disk centered at $O$ which is large enough that it contains all the endpoints of the rays. [asy][asy] size(10cm); pen blu,grn,blu1,blu2,lightpurple; blu=RGB(102,153,255); grn=RGB(0,204,0); blu1=RGB(233,242,255); blu2=RGB(212,227,255); lightpurple=RGB(234,218,255); filldraw(circle((0,0),1),blu1);dot("$O$",(0,0));draw(circle((0,0),1),blu); pair A=dir(60)*0.5; pair B=dir(140)*1.8; dot(A); draw(A--B); pair X=2.5*dir(180); pair Y=2.5*dir(0); pair Z=1.5*dir(90); pair T=1.5*dir(270); draw(Y--T); draw(X--Z); pair YY=1.15*Y-0.15*T; pair TT=1.15*T-0.15*Y; draw(TT--YY,dashed); pair U=0.25*T+0.75*Y; label("$\ell_1$", U, 2*dir(90)); pair ZZ=1.15*Z-0.15*X; pair XX=1.15*X-0.15*Z; draw(XX--ZZ,dashed); pair V=0.75*X+0.25*Z; label("$\ell_2$", V, 2*dir(90)); pair BB=1.15B-0.15A; draw(B--BB,dashed); [/asy][/asy] If David draws two parallel lines $\ell_1{}$ and $\ell_2{}$ outside this disk, any ray may intersect at most one of them, since any ray pierces the disk exactly once. Furthermore, if David draws these lines parallel to one of the Vlad's rays, it won't intersect either $\ell_1{}$ or $\ell_2{}$. This leaves a total of $99$ rays which can intersect at most one of $\ell_1{}$ and $\ell_2{}$. Thus, by the pigeonhole principle, some $\ell_i{}$ crosses at most $49$ rays, hence by drawing that line David can pay Vlad at most $49$ pounds, which finishes the proof.