## Problem of the Day #423: Cookie QueriesDecember 31, 2012

Posted by Saketh in : potd , trackback

Albert is hungry. He visits a local djinn and wishes for a bottomless jar of cookies.

As always, there’s a catch. The crafty djinn marks $n$ of the cookies from $1$ to $n$ using some icing. He then arranges them in some fixed order $\pi([n])$ hidden away from Albert’s view.

Now, if Albert can name a subset $S$ of $[n]$ such that some permutation of $S$ is a contiguous subsequence of $\pi([n])$, he gets to eat $|S|$ cookies from the jar.

All queries (Albert’s choices for $S$) must be written down before any of them are processed. What is the least number of queries Albert can make to guarantee he will receive at least one cookie?

$\textbf{Bonus:}$ Determine, for fixed $n$ and $q$, the set of $q$ queries that maximizes the expected number of cookies Albert will get to eat.