Bonus question (still simple): Now you may stack pieces and then break them all in one go. What's the optimal solution then?
Hmm, it's still harder than the original problem, here's where I'm at:
I know the lower bound is ceil(log2(n*m)) = ceil(log2(n) + log2(m)), and the upper bound is ceil(log2(n)) + ceil(log2(m)), but I'm not sure yet which is the right answer.
Please don't hesitate to post puzzle you think some people may already know, probably they will be new to at least some. I didn't come up with my puzzles myself either.
Okay, here's a relatively famous one, hopefully it's new to at least one person but we'll see:
Problem description: You have 12 balls, all but one have identical weight. The "bad" one may have weight greater or less than the a "normal" ball. You have no further information about the actual values of the weight of either a normal ball or the bad ball.
You are given a scale. You can put a pile of balls on one end of the scale, and another pile on the other end, and the scale will either tip to the heavier side showing you which pile is heavier, or will show that the two ends are of equal weight. We will further stipulate that after using the scale as described above, you must take all balls simultaneously off the scale before you use the scale again on other piles of balls. (I'm not sure/don't remember if this really changes the solution, so I'll be conservative and make this part of the rule of scale usage; feel free as an additional exercise to establish that it does or does not matter.)
So we count a single "usage" of scale as taking any and all balls from a previous scale usage simultaneously off the scale, follow by putting 2 piles of balls of your choosing on each end of the scale, and finally reading the result (tellling you which pile is heavier, or that both piles are of equal weight).
Your challenge is to find the minimum number of times you must use the scale to identify which one of the 12 balls is the bad ball.================
To simplify things (read: I forgot the details of this part at the moment, so I won't make you do it, but feel free as an additional exercise), you don't have to prove optimality. You merely have to somehow arrive (by guessing or otherwise) at the correct minimum number, and then prove that it is sufficient, meaning that you can come up with a scheme provably guaranteed to always correctly identify the bad ball, using no more than this number of weighings.