Problem 1-1 Kookie's Cookies

Problem Posts

Problem 1-1 (Number Theory) [Difficulty 1] [PDF]

QUESTION
(Sipnayan 2012 High School Final Round: Weightlifting 4) Kookie has a kooky way of eating cookies. He lays them out on a circle. After Kookie eats a cookie, he skips the next (clockwise) remaining cookie in the circle and eats the next (clockwise) remaining cookie after that. Kookie places a batch of $2012$ cookies numbered $1, 2, \ldots 2012$ in that clockwise order, and begins to eat them, cookie $2$ first. Let $k$ be the number on the last of the $2012$ cookies that he eats. Kookie, unsatisfied, arranges another batch of $k$ cookies numbered $2, 4, 6, \ldots 2k$ in that clockwise order, and begins again with the cookie numbered $2$. What is the number on the last cookie Kookie eats from this batch?

Overview
This problem comprises two iterations of the Josephus problem.




Discussion
Disclaimer: This is one of those problems easier done than discussed.

You will note that $2012$ is a contrived number. This means you probably need to find some formula or pattern that will work for an arbitrary $n$. If you don't outright know the formula, you'll want to try small numbers.

Let's demonstrate this by returning to the original Josephus Problem, dressed in the current context: There are cookies arranged $1,2,\ldots n$ in a circle, and Kookie eats them cookie $2$ first in his kooky manner. You will quickly notice that when $n$ is a power of $2$, the last cookie to be eaten will be cookie $1$¹. So what happens when $n$ is not a power of $2$?

Well, reduce the problem by having Kookie eat the cookies until there's a power of $2$ left! Let $n=2^{m}+p$ for nonnegative integers $m$ and $p$ so that $0\le p<2^{m}$. (You will find that $m=\left\lfloor \log_{2}n\right\rfloor$.) Now have Kooky eat the first $p$ cookies. Once he finishes this, there will be $2^{m}$ cookies left. The first cookie he skips over is numbered $2p+1$. So immediately, we know that that is the last cookie to be eaten! So, essentially, we have $$k\left(n\right)=1+2\left(n-2^{\left\lfloor \log_{2}n\right\rfloor }\right)$$ which is an ugly-looking but actually easily applicable formula.²

So $k\left(2012\right)=1977$.

The next part of the problem is meant to be a trap. Kooky starts with cookie $2$ again, but this time, cookie $2$ is first in line. That's very, very different.

Since this is confusing enough, let's renumber: $2\times1977\rightarrow1, 2\rightarrow2, 4\rightarrow3$ and so on until $2\times1976\rightarrow1977$ (note how we nicely renumbered so that it mirrors Standard Josephus). Now there are $1977$ cookies and we start with the one re-numbered $2$. $k\left(1977\right)=1907$. Now $1907$ was the renumbering of cookie $\boxed{3812}$.

Strategy

No discernible strategy here. If you knew the Josephus problem, this should be a straightforward double application. Otherwise, the problem extols the virtues of opening by trying small numbers, and proving your findings through induction.

---

1 We can easily prove this through induction. The case $n=1$ is trivial. Now suppose you knew this would happen for $2^{k}$ cookies. Suppose Kooky arranged $2^{k+1}$ cookies. He eats all the even numbered cookies. Now he's left with $2^{k}$ cookies, and he's going to skip cookie 1 again. By inductive hypothesis, he'll eat cookie 1 last.

2 For those doing this in computer, there's a simpler way to describe $k\left(n\right)$: Simply express $n$ in binary, remove the first digit, then append it to the end of the number! Indeed $$k\left(2012_{10}\right)=k\left(11111011100_{2}\right)=11110111001_{2}=1977_{10}$$