Chef Nidhi strikes back!

Here is how to get tot the right answer by elimination.

When $k=n-1$ there are only 3 possible choices for Chef Nidhi: he take the $2k$ leftmost utensils, the $2k$ rightmost utensils or the $2k$ utensils in the middle. Now if the 2 leftmost and rightmost utensils are spoons, then Chef Nidhi is stuck: he will have to pick all the forks and leave two spoons out, leaving an unbalanced set. However this does not work for $n=3$ (because there are only 3 spoons).

So far: $k=n-1$ doesn't work when $n \geq 4$ . This rules out one answer: "for any $k \leq n$ ",

However this does not work for $n=3$ (because there are only 3 spoons). If the two utensils at the end are different (F----S), then Chef Nidhi picks the bunch in the middle. So we may assume that the utensils at the end are both spoons (S----S). Next if two spoons are at one end (SS---S or S---SS), then he may pick all utensils from this end (because the 3 utensils in the middle are forks: SSFFFS or SFFFSS). So we have at both ends a fork and a spoon (SF--FS). Hence the two middle utensils are also a fork and a spoon, so he may pick all utensils from some end.

So the trick works for $k=2$ and $n=3$ . So this rules out the remaining answers: "Exactly when $k \neq n-1$ ", "Exactly when $k$ divides $n$ " and "Exactly when $k \leq \frac{n}{2}$ or $k=n$ ".

Hence the only remaining answer is \fbox{"Exactly when \$k \leq \frac{n+1}{2}\$ or \$k=2\$"}

General proof?

I don't believe there is a general method to find the pairs $(k,n)$ where the trick works. But here are some facts.

So the easiest part is to check that $k=n$ always work since Chef Nidhi can simply pick up all the utensils.

The next easiest thing to do is come up with a line-up in which Chef Nidhi fails. This set up is $\lceil\frac{n}{2}\rceil$ spoons then $n$ forks then $\lfloor\frac{n}{2}\rfloor$ spoons. If $k > \lceil\frac{n}{2}\rceil$ and $k \leq \tfrac{1}{2} (n +\lceil\frac{n}{2}\rceil)$ , one sees that Chef Nidhi can pick at most $\lceil\frac{n}{2}\rceil$ spoons; which is not enough. If $k > \tfrac{1}{2} (n +\lceil\frac{n}{2}\rceil)$ and $k <n$ , he will pick all the forks (and hence not enough spoons).

Here is another family of counterexamples. Assume $n = ja = (j+1)b$ where $a$ and $b$ are even and $j$ is some integer. Then the line-up $b$ forks, $a$ spoons, $b$ forks, $a$ spoons, .... , $b$ forks, $a$ spoons and $b$ forks, will leave Chef Nidhi stuck if $k = \tfrac{1}{2}(a+b)$ .

The first nice example in this family is FFFFSSSSSSFFFFSSSSSSFFFF. This shows the trick does not work for $n = 12$ and $k=5$ . This example can be modified to show the trick does not work for $n = 14$ and $k=6$ as well as $n = 15$ and $k=6$ (and perhaps other, I did not check).

Here is an argument which show the trick indeed works:

Let $f(k) = +1$ if the $k^{\text{th}}$ utensils is a fork and $-1$ if it is a spoon. Then consider $g(i) = \displaystyle \sum_{j = i}^{i+2k-1} f(j)$ . We need to show that $g(x) =0$ for some $x \in [1,2n-2k+1]$ . Note that $g$ take values in the even integers and that either $g (x+1) = g(x)$ or $g(x+1) = g(x) \pm 2$ . So the main ingredient is to show that for some $i_0$ , $g(i_0) < 0$ and for some $i_f$ , $g(i_f) >0$ . Then by the "intermediate value theorem" one has that some $i$ between $i_0$ and $i_f$ has $g(i) =0$ .

The case $k$ divides $n$ is then done since $g(1) + g(2k+1) +\ldots + g(2n-2k1+1) = \sum_{i=1}^{2n} f(i) =0$ . This means that one of the member on the left hand side is $<0$ and another is $>0$ (that is unless they are all 0, in which case we are done anyway).

So far I could only check the remaining cases $k \leq \frac{n+1}{2}$ and $n \leq 11$ by writing a small program. It turns out the trick always work for $k \leq 7$ and $n = 13$ .