Logic Puzzles

[ccexplore]

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.

[EricLang]

This riddle is in one of the old Columbo series. I'll watch it tonight to get the exact details of the problem.

[geoo]

I think I heard about this puzzle or a variation thereof, but I can't remember anything about the solution, if I was even ever told about it.

So I gave it a shot. I found a lower bound on the amount of weighings, and using that idea, I got a systematic approach to constructing the weighing procedure:

Each weighing gives you one ternary unit of information (henceforth referred to trit, just like in that one topic from ages ago, where ccexplore avoided the more natural naming for certain reasons http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />). There are 24 possible solutions (12 indices for the ball, and either 'too heavy' or 'too light'), and as it takes 3 trits to be able to represent all numbers from 0 to 23, we require at least 3 weighings to solve the problem.

Now we try to construct a solution. I will henceforth refer to balls that have been verified to have the correct weight as 'verified', ones that are possibly too heavy but not too light as 'heavy', ones that are possibly too light but not too heavy as 'light', and ones we don't know anything about as unknown.
So we start off with 12 unknown balls.  The first weighing has to be chosen so that independent of the outcome, it reduces the solution space to at most 9 possible solutions, as that's what fits into 2 trits. As we can only choose how many balls to put on the scale, there's not many solutions to scan through, and we find that we have to put 4 on either side. If the outcome is '=', then we got 8 verified balls and 4 unknown ones (1), reducing the solution space to 8 possible solutions. If the outcome is '>' or '<', then we got 4 verified balls, 4 heavy and 4 light balls (2), also reducing the solution space to 8 possible solutions.
Consider (1) first: we want to reduce the solution space to at most 3 possible solutions after the weighing, independent of the outcome. One will find that one solution to this is weighing 2 unknown balls against 1 unknown and 1 verified one. If the result is '=', then we verified the weighed ones and got 1 unknown ball left (1.1), i.e. 2 possible solutions. In the case '<' we got that the two unknown balls on the one side are light, and the unknown one on the other side is heavy, and the one we didn't weight is verified (1.2), reducing the solution space to 3 possible solutions. '>' is essentially the same with light and heavy switched (1.3). To solve (1.1), we simply weigh the unknown ball against a verified one, and get whether it is too light or too heavy. For (1.2), we weigh the two light balls against each other. If the result is '=', then they are verified and the heavy ball is indeed too heavy. If the result is '<' or '>', then the heavy ball is verified, and the light ball on the lighter side is too light while the other one is verified. (1.3) works analogously.
So let's consider (2). After a bit of searching, we see that if we weigh 2 light and 1 heavy balls against 2 light and 1 heavy balls, we can reduce our solution space sufficiently: Is the result '=', we got two light balls left (2.1), while the 6 weighed balls are verified, solution space reduced to 2. Otherwise, either one of the light balls on the lighter side is indeed too light, or the heavy ball on the heavy side is too heavy, so we got 2 light and 1 heavy ball (2.2), while the other 3 and the not weighed 2 balls are verified, solution space reduced to 3. (2.1) can be solved by weighing the two light balls against each other to see which of the two is really too light. (2.2) is analogous to (1.2).
Following this procedure, we are certain to get the solution after 3 weighings.

As for the problem with the planets, I think it's indeed a bit tricky to accurately prove that it is the surface of a sphere minus a set of measure 0. But I think I found a solid proof to this.

As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.

[ccexplore]

So I gave it a shot. I found a lower bound on the amount of weighings, and using that idea, I got a systematic approach to constructing the weighing procedure:

Wow, good job! http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" /> It's a tricky problem (and an easy one to forget the details off top of head because it's somewhat intricate), but not only did you nail it, but you have a very nice systematic approach that not only proves the weighing procedure is sufficient, it actually provides the logic behind how to come up with the procedure in the first place.

As for the problem with the planets, I think it's indeed a bit tricky to accurately prove that it is the surface of a sphere minus a set of measure 0. But I think I found a solid proof to this.

My current progress on the problem reduces the measure-0 (aka "zero area") issue to an appeal to intuition, that we can consider the boundary curves for each non-exposed area from a sphere to each be a well-behaved curve that has measure 0.  If we accept that we don't need to rigourously prove that particular assertion, then I think I can complete the proof.  But again a bunch of words and diagrams that will have to wait.  I think this is a reasonble concession, given that a rigorous proof seems likely more of an exercise in analysis (ie. the mathematical topic, not the general meaning of the word) than is the core concepts behind the proof.

As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.

Yeah, I'm pretty sure the two bounds only differ by at most 1, and I think I know which bound is the right one, but somehow I haven't convinced myself 100% yet.  I guess that's what I get for saying the original problem is too obvious. http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" /> http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />

[Clam]

Most of the above puzzles are solved it seems, so I guess it's about time I posted some puzzles too. Since geoo suggests posting puzzles even if people may have heard of them, I decided I should hit you with something a little different. These are less maths/physics puzzles like most of the ones so far, and more groan-worthy thinking puzzles.


1. I'm at a cafe and I find a fly in my coffee. I ask the waiter to take it away and bring back another cup. However, when he comes back with a cup of coffee, I can tell it is the same coffee as before. How?

2. What occurs once in a minute, twice in a week and once in a year?

3. Imagine you are a taxi driver as opposed to a taxi drier or taxi diver and you are driving a 1978 yellow cab. Your passengers are an older couple, and they want to travel 6 miles. You are driving at 40 miles per hour with the tank one-third full, when, 2 miles into the trip, the tank is down to one-quarter full. Ten minutes later, the trip is over. What is the age of the cab driver?

4. I have five cupcakes in a basket. How can I give one cupcake to each of five people and still leave one in the basket?

5. How far can you go into a forest?

6. Why do black sheep eat less grass than white sheep?

[ccexplore]

4. I have five cupcakes in a basket. How can I give one cupcake to each of five people and still leave one in the basket?

Not my type of riddles, but nevertheless here's an answer I come up with for #4.

Imagine the basket in question is really the "basket" for a hot air balloon (ie. where the passengers would be located; maybe it's not really called a basket in English but humor me, or imagine instead maybe you have a ridiculous giant basket that can fit people in).  If one of the receiving person is himself sitting inside the basket, you can give the cupcake to him while allowing the cupcake to remain inside the basket along with that person.

Since I didn't laugh nor groan, somehow I think the actual intended answer is something else. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

[edit2: Okay, here's a more likely answer for #4, although it still doesn't fit into the groan/laugh category I was expecting]
[edit3: move position of edit2 in the post to intended place]

Give the cupcake and the basket to the fifth person, so the person can receive the cupcake while the cupcake remains inside the basket

[edit: here's a hint for #3, I'm pretty sure I know what the expected answer is]
[edit4: updated hint since "sentence" is not specific enough]

Read the first sentence (up to but not including the word "and") carefully again.

[Clam]

Since I didn't laugh nor groan, somehow I think the actual intended answer is something else. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

I guess you're more likely to groan if you see the answer instead of figuring it out for yourself. I like the creativity of your first answer though, very nice http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> (and yes, your second answer is the "right" one)

[alfonz1986]

#2 (invis) the letter e

#3 my age is 25

#4 I give 4 cupcakes to 4 people and the 5th one I give to myself, keeping it in the basket

#6 black sheep are far more rare than white sheep

[ccexplore]

As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.

Okay, I finally got it, but somehow the proof ends up going much longer than I thought.  It's not hard, but it feels nowhere as straightforward as the 1st chocolate bar problem.  Maybe there's a better way about this that better appeals to logic and intuition:

Lemma:  to reduce any set of rectangular pieces to 1x1 squares in K cuts, each rectangular piece must fit within one of the rectangles from the set of rectangles of dimensions 2^i x 2^(K-i), i ranging from 0 to K.  This is both necessary and sufficient.

Proof by induction: base case (K=0): This is trivially true, with no cuts all pieces must already be 1x1 squares (and trivially true conversely), and they of course all do fit within a 2^0 x 2^0 = 1x1 rectangle.

Induction case (K ==> K+1): We need to show necessary and sufficient.

Sufficient: this is obvious. A 2^i x 2^(K+1-i) rectangle can always be cut down the middle into two 2^j x 2^(K-j) rectangles. So take any piece and consider the 2^i x 2^(K+1-i) rectangle bounding it.  The same cut on the bounding rectangle will split the piece into one or two subpieces, one fitting in one of the 2^j x 2^(K-j) rectangle, the other (if any) fitting in the other rectangle of identical dimensions.  Now consider stacking all pieces together to do this cut on all pieces in one go, and it's clear that with 1 cut, we have reduced all pieces into new pieces, all of which will fit within a 2^j x 2^(K-j) rectangle.  Induction then shows that it's sufficent to use the remaining K cuts to get everyone down to 1x1.

Necessary: Let's say we have a rectangular piece that can't fit into any rectangles of dimension 2^i x 2^(K+1-i).  I'll show that a single cut to that piece will always leave a rectangle that will not fit into any 2^j x 2^(K-j) rectangles, and therefore it can't be further reduced to 1x1 rectangles with only the remaining K cuts.  And so to reduce everything to 1x1 with only K+1 cuts, all rectangular pieces must indeed fit into a 2^i x 2^(K+1-i) bounding rectangle.

There are a few subcases to examine.  A diagram is probably easier to show and understand, but it's a hassle so instead I'll try words/algebra only:

A) the piece is so large that its area is larger than 2^(K+1).  Then any way of splitting the piece in 2 must result in a piece of at least half the original area, so larger tha 2^K, which is the area of any rectangle of dimensions 2^i X 2^(K-i). So it definitely can't fit (anything that could fit must have area smaller or equal, not larger).

B) the piece has dimensions SxT, S >= T >= 1, and area (which happens to be S*T) smaller than or equal to 2^(K+1). So clearly T is smaller than or equal to 2^(K+1).  The piece can't fit into any 2^i x 2^(K+1-i) rectangle, so in particular, consider the rectangle of dimension 2^(ceil(log2(T)) x 2^(K+1-ceil(log2(T))).  The T part of the rectangle can fit against the 2^(ceil(log2(T)), so the S part must not fit against the other dimension, meaning S > 2^(K+1-ceil(log2(T))). [$]

Also note that 2^(ceil(log2(T))) = 2^(log2(T) + t'), where t' is what you add to log2(T) to bring it up to the ceil(log2(T)).  Obviously t' < 1, so 2^(ceil(log2(T))) < 2^(log2(T) + 1), equivalent to T > 2^(ceil(log2(T)) - 1). [$$]

Now, if we do the 1st cut on the SxT piece across S, then the resulting two rectangles still has T in one dimension, and one of the two will have at least ceil(S/2) in the other dimension.  We now need to show that we can't fit this ceil(S/2)xT subpiece into any 2^j x 2^(K-j) bounding rectangle. The relation T > 2^(ceil(log2(T)) - 1) shows that you need one side of the bounding rectangle to be at least 2^(ceil(log2(T))) to fit T, but then we have at most 2^(K-ceil(log2(T))) to try to fit ceil(S/2). But ceil(S/2) >= S/2 > 2^(K-ceil(log2(T)) (from [$]), so no fitting possible with a cut across S.

If we instead do the cut across T (assuming T > 1 so that you can even do such a cut), then the resulting 2 rectangles still has S in one dimension, and one of the two will have at least ceil(T/2) in the other direction. But ceil(T/2) >= T/2 > 2^(ceil(log2(T)) - 2) (from [$$]), so to fit ceil(T/2) we need one side of bounding rectangle to be at least 2^(ceil(log2(T)) - 1), leaving the other side of bounding rectangle at most 2^(K+1-ceil(log2(T))).  But then as established earlier (from [$]), S > 2^(K+1-ceil(log2(T))) = 2^(K-(ceil(log2(T))-1)), so again no way to fit the ceil(T/2)xS subpiece into any 2^j x 2^(K-j) bounding rectangle.

QED

Now go back to the original problem, which is really a set consisting of a single NxM rectangular piece.  The lemma we just proved shows that it has to fit within a 2^a x 2^b rectangle and then we know it can be reduced to 1x1 with a+b cuts.  The lemma also shows that with a 2^c x 2^d rectangle of smaller (c+d) that the NxM piece can't fit in, you cannot reduced to 1x1 with c+d cuts only.

This effectively shows that we indeed need ceil(log2(N)) + ceil(log2(M)) cuts, because 2^ceil(log2(N)) x 2^ceil(log2(M)) is the smallest rectangle the NxM piece can fit within.

[ccexplore]

1. I'm at a cafe and I find a fly in my coffee. I ask the waiter to take it away and bring back another cup. However, when he comes back with a cup of coffee, I can tell it is the same coffee as before. How?

It seems there's really only one good answer to this:

I rarely visit cafes but it seems like most of them have kind of "open counter" setup, as opposed to something like a restaurant where everything happens in a closed kitchen hidden from view behind double steel doors.  At the very least I don't think they go out of their way to make what they do totally hidden.

With that in mind, it's pretty reasonble to say that you know exactly what the waiter did with the coffee because you were able to see how he handled the coffee from where you're sitting.

I somehow have a feeling that my answer is not the point of the question, but if the question is aiming towards other solutions, I feel I can argue that any other such solutions are inferior in some way:

If you are indeed unable to actually see what the waiter did with the coffee, then any method you rely on to support your hypothesis that the coffee remained the same, can in principle also be explained by the waiter doing whatever it takes to make the second cup of coffee as identical as possible to the first coffee, including what you did with it before it was returned.   For example, if you based it on temperature, or maybe something as crazy as you drop some specific chemical marker in the coffee before it was returned, it is conceivable (however unlikely) that the waiter could've done a bunch of stuff behind the scenes to mimic all the effects on the original coffee between the time you received it and the time it was returned, so that it really is a new cup of coffee that just happens to appear like the original cup under the set of tests you devise.

So given any situation in which you can't actually see what the waiter did, but you strongly suspect that he gave you back the same coffee, there is an alternative hypothesis in which the coffee is not the original.  The probability of such alternative hypotheses may be astronomically small, but it's still non-zero.

So what I'm saying is that any solution in which you can't observe what the waiter actually did with your coffee, your certainty that the coffee was unchanged is less than the certainty when you can observe.  Therefore the solution that you can observe what the waiter did is the superior answer. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

======================

It wouldn't surprise me if the "real" solution is probably one that takes advantage of language ambiguity and other things, and ends up describing a situation that is not quite how you normally picture/interpret things based on the given statements (and thus making my proposed solutions all not applicable).  However, while I've briefly considered that sort of reasoning, I've yet to find a good "alternative interpretation" that works well across all the given statements of the problem.  But we'll see I guess......

[Simon]

I will be silent in regard to the current puzzles, since I already know each of Clam's riddles. I also did a few of geoo's puzzles in IRC already. So there aren't any unsolved problems that seem interesting to me. <_<; Here's another one for the rodent fraction (= the critters from IRC, and cce because he's the busy beaver, but really anyone). Care should be taken not to eat the wooden blocks, even if they look tasty.


You have a hollow cube-shaped box, measuring 5 x 5 x 5. You wish to completely fill out this box with wooden cubic blocks, but no filling block may stick out of the box after you're done. At your disposal are arbitrarily many cubic blocks of side lengths 1, 2, 3 and 4.

What is the smallest number of blocks necessary to fill the box? (Some proof of minimality would be nice, it's not that many cases fortunately.)

-- Simon

[ccexplore]

Okay, I finally got it, but somehow the proof ends up going much longer than I thought.  It's not hard, but it feels nowhere as straightforward as the 1st chocolate bar problem.  Maybe there's a better way about this that better appeals to logic and intuition

Hmm, my brain must be fried.  I can explain it a bit easier than what I posted earlier, in fact this better captures the original intuition that led to the proof I posted.

Once again the key is the lemma that to reduce any set of rectangular pieces to 1x1 squares in K cuts, each rectangular piece must fit within one of the rectangles from the set of rectangles of dimensions 2^i x 2^(K-i), i ranging from 0 to K. [This is both necessary and sufficient.]  I just find an easier way to explain the induction proof step:

Proof from case K to case K+1:  the process of reversing a cut of any piece is to find the two resulting smaller pieces and join them back together at their cut sides.  From case K, we have that the two smaller pieces must each fit inside a 2^i x 2^(K-i) bounding rectangle.  Let T be the length of the common cut side of the two rectangles.  Then the smallest 2^i that can fit T is 2^(ceil(log2(T))), any smaller and we can't fit length T.  This means both smaller piece's bounding rectangles, the lengths of the non-joined sides must each be at most 2^(K-ceil(log2(T))), in order to have both rectangles each fit inside a 2^i x 2^(K-i) bounding rectangle.  Now observe that joining the two bounding rectangles together at their common 2^(ceil(log2(T))) sides, results in a new bounding rectangle covering the original bigger piece before the cut, and this new bounding rectangle has one side of length 2^(ceil(log2(T))), and other side of length at most 2^(K-ceil(log2(T))) + 2^(K-ceil(log2(T))) = 2 * 2^(K-ceil(log2(T))) = 2^(K+1-ceil(log2(T))).  So this new bounding rectangle for the pre-cut piece is a 2^j x 2^(K+1-j) bounding rectangle.  Thus we've just proved that case K implies case K+1.

Below is an ASCII art example depiction of what I just described above, for the case where we join two 3x3 pieces back together to form the 6x3 piece they originated from before getting a cut.  The 3x3's bounding rectangles can correspondingly be joined together to form an 8x4 bounding rectangle for the whole 6x3 piece:

XXXXXXXX
X***+++X
X***+++X
X***+++X

[ccexplore]

You have a hollow cube-shaped box, measuring 5 x 5 x 5. You wish to completely fill out this box with wooden cubic blocks, but no filling block may stick out of the box after you're done. At your disposal are arbitrarily many cubic blocks of side lengths 1, 2, 3 and 4.

What is the smallest number of blocks necessary to fill the box? (Some proof of minimality would be nice, it's not that many cases fortunately.)

Yeah, seems like a simple exercise in case analysis more than anything else.  Maybe it's a sign for us to give this thread a rest. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" /> Though I don't think I'd personally mind another alfonz1986-style physics problem or a Clam-style riddle.[/font]

If there's a 4x4x4 cube then the rest has to be 1x1x1 to fit.  You end up with 62.
If there's a 3x3x3 cube then the rest has to be 2x2x2's or 1x1x1 to fit, and to make use of 2x2x2's you have to put the 3x3x3 against a corner.  It's pretty easy to see that you can fill the rest with at most 7 2x2x2's.  You end up with 50.
With 2x2x2's only and nothing larger, it's pretty clear that you can't fit more than 8 of them, so you're clearly doing worse than 3x3x3.  And 1x1x1's only is silly.

[Clam]

(Re. #1) It seems there's really only one good answer to this:

While that's not "the" solution (i.e. the solution given by the author of the puzzle), I guess the wording of the puzzle is vague enough to allow numerous answers. I'm not sure I understand your idea of an answer being "superior" to another, but that's probably just because I have a specific answer in mind, and it's not the same as yours. Actually, you were perilously close to "the" solution at one point:

You mention a "chemical marker"...

But rather than dissecting the scenario and debating possible answers, the point of these types of puzzles is to find a simple solution, groan (or laugh), and move on. Though I will say, despite me having some background in maths and physics, when I think of "logic puzzles", these kinds of riddles are the first thing that comes to my mind. Maths and physics puzzles are logical too of course, but (as we've seen) they often require some specific knowledge, which these riddles don't.

By the way, strictly speaking, the whole thing is a trick question since I don't drink coffee http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

[ccexplore]

While that's not "the" solution (i.e. the solution given by the author of the puzzle), I guess the wording of the puzzle is vague enough to allow numerous answers. I'm not sure I understand your idea of an answer being "superior" to another, but that's probably just because I have a specific answer in mind, and it's not the same as yours.

Yeah, don't take it too seriously.  But it is a very logical argument don't you think?

I'm merely saying that if you can't actually see what the waiter did, then theoretically, the waiter can always make a second cup of coffee that nevertheless has characteristics as close to the original coffee as possible (with decreasing plausiblity the closer the characteristics are).  You added sugar and cream?  The waiter could've done that to your second cup of coffee also even though it's not usual practice, or the exact same thing that happened to you could've happened to a 2nd customer, and the waiter ends up swapping you and the other customer's coffees, and by coincidence both you and your customer added the same amount of sugar and cream.  And so forth with many other scenarios.  Even if you say you tested for your DNA, there is the theoretical (and disgusting http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />) possibility that the waiter extracted a sample of your DNA from the original coffee, filter any traces of the original coffee out, and add the sample back to the second coffee.  Again, highly implausible I agree, but not barred by the laws of physics.  As you pointed out, the vagueness of the puzzle opens up a lot of possibilities as to what happened.

So what I'm saying is, the answer that you saw what the waiter did is the one where you have the least uncertainty about the coffee.  What I glossed over of course, is that there can also be a small probability that what you saw happening is not necessarily what actually happened, as anyone observing a magician's act can attest to.  So it was never really a watertight argument to begin with but hey, I was hoping at least it was funny to think up all these implausible alternatives that you can't rule out 100% when you lack the observation. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />