Group testing puzzle I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers.
I can't tell which layer is which flavor, but I can smell the vanilla. For any $m$ with $1\le m\le n$, I can test the top $m$ layers of the cake by removing them from the cake and taking them to another room. There, I can smell whether any of those layers are vanilla. Then I can replace those $m$ layers in their proper position on top of the cake.
Once I've performed enough tests to determine if a layer is vanilla, I eat it right out from the middle of the cake, leaving the $n-1$ layers intact. I need to be certain what I eat is vanilla. Then I can return to doing more tests to find the next vanilla layer.
How can I write an algorithm that takes in $n$
and $k$, and outputs the number of tests required to identify (and therefore eat) all of
the vanilla layers?

In my opinion, the only way we can do this is by checking every single layer individually... I don't see how taking multiple layers at a time would ever work.
Let vanilla = 1 and other flavors = 0.
Let's say we have a cake 011:
and we take 3 at a time, and find there is vanilla, then we anyways need to check every layer.
Let's say we have 0000001
and we take 3 layers, then yes, we can move on to the next 3. But why don't we take 4 or 5?
Or 7? if we take 7 though, we'd be back at the first issue.
I think we have to do this individually (it would take $n$ tests) because trying to shorten it simply does not give us enough information. Any clarification would be helpful as this does seem too simple to me!
Try to think in terms of binary search:
Start by checking half the cake. Then, if you didn't smell vanilla, you can be sure the first half does not contain vanilla, hence we don't need to check them anymore - hence we save time. This was only intuiton to why it might be possible to do better than $O(n)$, not the actual solution for it.
But something important to note is that any algorithm better than $O(n)$ must depend on $k$. Its not hard to show a lower bound of $\Omega(k)$