I can’t solve the problem below, I tried assigning a value to each student based on the difference between the amount of girls in the k students in front of him (him included) and the amount of girls in the k students before him but I couldn’t figure it out. I also tried Bottom down induction but that also failed. Any ideas?
Best Answer
Let $a_i=1$ if $i$ is a girl, $0$ otherwise. Let $f(n,k)=\sum_{i=n}^{n+k-1}a_i$, so we want to show that $f(n,k)=f(n+k,k)$ for some $1\leq n\leq1000$ and $100\leq k\leq 300$.
Define $g(n,k)=f(n+k,k)-f(n,k)$, and assume for contradiction that $g(n,k)\neq0$. Then as $\lvert f(n+1,k)-f(n,k)\rvert\leq1$, it follows that $\lvert g(n+1,k)-g(n,k)\rvert\leq 2$.
Now $\sum_{n=1}^{1000}g(n,k)=0$, so somewhere $g(n,100)$ goes from $-1$ to $+1$, WLOG $g(0,100)=-1$ and $g(1,100)=1$. So this implies $a_0=0$, $a_{100}=1$, $a_{200}=0$. If $a_{201}=1$, then $g(0,101)=0$, so we must have $a_{201}=0$. Similarly, $a_{-1}=0$. Continuing like this, we see that $$a_{201}=a_{202}=\dots=a_{402}=a_{-1}=a_{-2}=\dots=a_{-200}=0,$$ but then $g(201,101)=0$, a contradiction.