Logic Puzzles

[ccexplore]

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.

Well #2 #3 and #6 fits the bill the most in that regard so far, at least I'm unable to find any other sensible interpretation leading to different answers (although I must admit, I tried to see if I can come up with a different answer to #6 after peeking at the answer http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />).

And in theory, to a person coming from a culture unfamiliar with sheep (Inuit say?), #6 isn't necessarily general knowledge, but I digress.  http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

I'm also aware that dissecting these kinds of riddles is not really the point, on the other hand, I'm fascinated because I feel that closely examining these kinds of riddles highlights some interesting points for natural language processing and other related topics.

[ccexplore]

Also, the reason I picked the 12-balls and scale puzzle is because I thought it's a nice logic puzzle that doesn't require specific knowledge or mathematical experiences.  A solid math background may lead you to the answer faster and more systematically (as geoo attested to), but at least it's quite possible to explain a working scheme to a layman and convince him/her that it works.

So I disagree that you must fall to the level of Clam riddles to have generally accessible logic puzzles.  Also, the problem is that some of the riddles aren't really about logic at all.  I do agree they can be good for a laugh though, especially the less they are about logic. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

[alfonz1986]

Wait! I got it! You're not actually in a coffee shop at all. You just have terrible dementia and you're 80 years old and in a nursing home.  http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />
Hence the cup of coffee can be whatever you want it to be.

Ok, and back to the not-so-logical puzzles:

You're in a DIY store looking to purchase some items for the house. If 1 costs $0.50, 12 costs $1.00 and 144 costs $1.50 .....
What is it you are buying?
 

[Simon]

I know alfonz' puzzle already, so I'll pass and let someone else take a guess.

This one here should be a bit more in the logic department again. I'll translate the story that goes with it, because it's really neat.


Have I told you how the mollusc tried to trick me?

Mollusc is the nickname of a collegue of mine, she teaches biology at our school. She got the name from her students as she has a faible for molluscs. One day, she sat next to me in the teachers' room, and raged about an exam she had just graded. "For years, I explain the seven classes of molluscs to the kids, and each year, the tests about this subject are catastrophically bad!"

She gave me a sheet of paper, which showed five pictures of some random slugs or worms. The task was to classify these five animals. "Here are the six best tests.", she continued. "Each of these kids gave exactly two correct answers, the twenty others didn't even get a single one right!" And then she announced, making sure everyone in the room could hear it, "Every somewhat intelligent person knows what these animals are, don't they?" Of course, I had no clue, and the mollusc knew that exactly. I carefully examined the six tests. Below the pictures, the students had written:

Student A: 1. Worm Snail, 2. Hairy Back, 3. Worm Snail, 4. Head Footer, 5. String Worm
Student B: 1. Worm Snail, 2. Band Worm, 3. Hairy Back, 4. Worm Snail, 5. Beetle Snail
Student C: 1. Scratch, 2. Clam, 3. Band Worm, 4. Amoeba, 5. Tusk Shell
Student D: 1. Wheel Animal, 2. Clam, 3. Worm Snail, 4. Clam, 5. Monoplacophorum
Student E: 1. Snail, 2. Clam, 3. Amoeba, 4. Insect, 5. Tusk Shell
Student F: 1. Worm Snail, 2. String Worm, 3. Amoeba, 4. Amoeba, 5. Tusk Shell

Luckily, I was able to classify all animals from these answers, without knowing even a single one. The mollusc stared at me with an open mouth. She never tried to trick me again. Can you do it as well?

-- Simon

[alfonz1986]

I also solved the bear one, on my way walking to uni http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

The only way you could walk two miles south, five miles west and two miles north again while managing to return to the starting point is if you began on the north or south pole. Polar bears live in the north pole, hence the colour of the bear is white  http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

[Simon]

North pole is correct, yep. The reasoning has subtle humps though (file this away as smart-arse blah blah):

• South pole is not possible even if there were bears, since one cannot walk south from there.
• North pole is not the only point. There are more points on earth that allow walking as given. Each of these points lies 2 miles north of a latitude circle whose circumference is 5 miles, or 5/n miles with n nonzero natural number, or even equal to the south pole. Since a circle with radius 2 miles has circumference greater than 5 (even on the earth surface, since the earth is large enough), none of this extra stuff can be close to the north pole, so all of the additional points lie close the south pole -- even though south pole itself isn't a possible starting point, but north pole is.

-- Simon

[alfonz1986]

Yeah I basically meant the principle is sound. Whether you start walking north or south makes no difference to the principle. Vice-a-versa

[ccexplore]

Good one for Simon's latest.  I think it's right there in terms of logic puzzles that are as unfettered by "outside knowledge" (math, physics, language, general knowledge, whatever) as you can get.

You have 12 correct answers to distribute across 5 questions.  Notice that there are no questions with same answer from 4 or more people, so each question is answered correctly by at most 3 people.  Let's focus on question 1, 2, and 5 since each has the same answer from 3 people.  Notice also that for each of those 3 questions, the remaining answers within the question are all different.

If only 2 of the 3 such answers are correct, then we have 6 more correct answers distributed amongst the remaining 3 questions, with no same answering appearing more than 2 times in each question.  So actually all 3 questions must be answered correctly by two people.  This includes the 3-same-wrong-answer question.  But none of the 3-same-answer questions has remaining answers that are the same from two people, ruling out this case.

So all 3 answers are correct.  We have 3 more correct answers to distribute amonst the remaining 2 questions, so at least one of the two questions are answered correctly by 2 people.  It can't be the amoeba because doing so results in someone answering 3 different questions correctly, which mollusc say isn't the case.  We're then left with the two "worm snail" answers from question 3, making it the correct answer for that question.  Now the only student left we haven't completely determined his 2 correct answers to is B, and the only question left is 4, so we're done:

1: worm snail
2: clam
3: worm snail
4: worm snail
5: tusk shell

[edit: minor wording edit]

[Simon]

Right on! A great systematic approach that rules out the existence of other solutions.

Another possible initial approach with the pidgeon hole principle: For any 3 of the six tests, there exist 2 ouf ot the 3 who share a correct answer (because we have six answers to five questions). Observe that A, B, and C share only the answer to question 1...

-- Simon

[alfonz1986]

Spoiler........Damn these invisible quote boxes to hell!

Solution for mollusc puzzle

1. worm snail
2. clam
3. worm snail
4. worm snail
5. tusk shell

I initially noticed that #1 had to be the worm snail. If it wasn't, theres no way pupils A, B and F could have two answers correct, since there are 4 questions left and there are no matches between anyones answers. The next obvious choice was clam for #2 since there were 3 answers for that one. Playing about with a few more options like tusk shell #5 gave the final solution shown above.

Took a little while before I realised two or more could be the same mollusc.

[Simon]

Yep, also a correct solution and argumentation!

Edit: I want geoo to reply now, stating that animal 1 is a scratch, 4 is an insect, and 5 is the beetle snail. >_>

-- Simon

[ccexplore]

Here's to wrap up geoo's #4 (the sphere/planet problem) once and for all.  I decided to forget the diagrams since at this point interest in the problem is probably low anyway.  Instead I'll just present a proof sketch (so some details omitted for reader's exercise--and yet it's still kinda a long read http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />), enough to satisfy geoo, say.  Ultimately I think the main concepts behind the proof is not too hard to visualize, but there are many technical details, enough that a full proof pretty much turns into a full-on exercise in advanced math.  (Indeed as mentioned earlier, I glossed over the 0-measure issue by simply asserting that curves have area 0.  Take a class in uni if you really want to know why. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />) [edit: minor reformatting]

First, a lemma A to characterize visibility and exposure:

Let P be a point on a planet. Ignoring other planets, visibility of P from other points in space can be characterized as follows:  take the plane tangent to the planet at P.  The plane divides 3D space into two sides.  All points on the tangent plane, as well as all points in space on the opposite side of the plane from the planet, will have full visibility to P.  The remaining points outside the planet that's on same side of plane as the planet, will have no visibility to P, the line of sight being blocked by some other point on the planet.  It's pretty easy to see when you consider drawing the line of sight from P to another point in space.

Lemma A has a corollary (call it lemma A'):  for P to be a non-exposed point, all other planets must be fully on the same side of the tangent plane as P's planet.  If another planet even merely "dips" slightly past the plane onto the other side, or even just tangent to the plane, then P becomes exposed.

In order to address the 0-measure issue, we also need lemma B concerning cases where a plane is tangent to more than 1 planet:  in that case, at least one of the tangent points will be a point on a boundary curve enclosing a non-exposed region (henceforth referred to as "a boundary point").  The key is to note that to be a boundary point, in all sufficiently and arbitrarily small neighborhoods of the point, you can find one point that's non-exposed, and another point that's exposed.  The basic idea of proving this is to consider what happens when you perturb the tangent plane around one of the tangent points. To give the basic gist of the argument, let's consider a simpler but roughly analogous situation, with 3 circles from left to right, and a line tangent to all 3.  Perturb the tangent line around (say) the rightmost tangent point, by rotating the line a small amount around that point, and then shift the line in an orthogonal direction until it becomes tangent to the rightmost circle again.  It's not hard to see that when you rotated the line counterclockwise (even by an arbitrarily small amount), the line ends up not touching the other two circles, while in the opposite direction (again even by an arbitrarily small amount, and even accounting for the shift to re-tangent the line to the rightmost circle) the line ends up fully intersecting both other two circles.

The 3D version of this observation is a little more intricate but basically the same idea.  You can perturb the plane around one of the planet's tangent points, so that all other planets came off the plane on the same side as the chosen planet.  By lemma A', you just found a non-exposed point on the chosen planet.  You can also perturb the plane in a different direction such that it intersects all of the other planets, which by lemma A', means you just found an exposed point on the chosen planet.  Lemma B proved.

Now consider the vector from a planet's center to a point on the surface, call it the orientation vector for the point.  Lemma C: you can't have two non-exposed points on different planets whose orientation vectors both point in same direction.  This is not hard to see by noting that the tangent planes on those two points are parallel, or in the degenerate case, one plane tangent to both planets at the two points.  It's then easy to see that with the parallel tangent planes, one planet will always dip past the tangent plane of the other planet, so lemma A' tells us one of the two points must be exposed.  For the degenerate case, lemma A' already showed that both points will be exposed.  Lemma C proved.

One final lemma D: given any direction, we can find at least one planet that has either a non-exposed or a boundary point, whose orientation vector points to the chosen direction.  The proof is basically a continuity argument involving "sweeping" the tangent plane orthogonal to the orientation vector in the orthogonal direction.  It's not hard to visualize and see that you can always end up moving the plane to a position such that every planet ends up on the same side of the plane (particular the side opposite to the direction of the orientation vector), with one or more planets tangent to the plane itself.  By lemma A' and lemma B, you've found a non-exposed point if exactly one planet's tangent to the plane, and a boundary point if multiple planets are tangent to the plane.

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

Now back to the main problem. The trick is to imagine merge all planets into one planet by translation only (ignore their solidity and imagine that they can freely pass through each other, and recall that they are all of same size), but don't adjust the exposed/non-exposed/boundary classification of the planet's points (ie. keep them classified to their original condition even as you move the planets).  Translation means no orientation changes, in particular, it preserves directions of orientation vectors.  With this transformation, lemma C transform to the property that after the merge, the non-exposed regions from two planets cannot overlap.  Lemma D transforms to the property that after the merge, every merged point of the merged sphere correspond either to a non-exposed point of some planet, or to a boundary point on at least one of the planets.

So we get sum(area of non-exposed regions) + area(remaining points on merged sphere) = surface area of one planet.  Regarding the remaining points, they are the result (by Lemma D's implication post-transformation) of tranaslating all the boundary curves onto the merged sphere, possibly with some overlap to each other.  So their total area on the merged sphere is no larger than sum(area of each boundary curve).  We now appeal to the boundary curves being normal, well-behaved curves, so we know each has area 0 and therefore the total is still area 0.  Thus area(remaining points on merged sphere) = 0, leaving us with sum(area of non-exposed regions) = surface area of one planet.  QED.

[geoo]

Here's to wrap up geoo's #4 (the sphere/planet problem) once and for all. [...]

Nicely sketched out proof. I use essentially the same idea of merging the planets into one and the tangential plane for each unit vector, and also make use of most of your lemmata, but I went with one simplification:

As you proved, if we got two or more points on one of these bordering tangential planes, they are exposed. Now pick any two planets, and any plane that touches both; the bordering tangential planes that touch 2 or more planets are obviously a subset of all these planes. Now for each pair of planets, the union of all the point pairs that are touched by such a plane are 1 great circle on each of the planets, thus a measure-0 set. Now there are only finitely many planets, so the union of these great circles from all pairs is still a null set. Now we translate/merge all the spheres into one, and the merged set of these great circles has the actual exposed points as subset, and has measure 0. So the exposed points on the merged sphere have measure 0 as well. The details to show that this is correct have to be copied from your proof.

I find your proof to the second chocolate problem pretty complicated though. I sketched out my line of thought below, and I don't think it has any leaks.

Let (m,n) denote a rectangle of the given dimensions. We know that if we break a single rectangle apart parallel to one of the sides, we always get two new rectangles. Now if we ignore the smaller one and only continue with the larger one, we have simplified the problem and analysing this, we get a lower bound (it's easy to see that it's also an upper bound because we can just fit the smaller piece somewhere under the big one). So lets model the breaking operation on (m,n) as replacing either of the two values with a new value larger or equal to its half. We know that after the breaking, both values must be 1. So we see that the operations on m and n are independent, i.e. it doesn't matter whether we start with m or n (rotating or anything else doesn't matter, obviously). So for each m and n, always dividing it by 2 gives us a lower bound, and to get this lower bound to 1 or lower, we need ceil(log m) and ceil(log n) respectively.

I thought about some of the other problems as well, and came up with possible solutions to the unsolved ones and also some alternative solutions:

Have I told you how the mollusc tried to trick me?

They're all Clams.
Nice puzzle though, first looks like brute force, until you see that there's three columns with a triple but no double entries.

You're in a DIY store looking to purchase some items for the house. If 1 costs $0.50, 12 costs $1.00 and 144 costs $1.50 .....
What is it you are buying?

You're buying sticks of constant length with the aim lay out iterations of some kind of Koch curve to decorate your room, and thus have to break the sticks into bits, and you're counting the substicks you get. But thinking of it, 144 should cost $2.00 then. Hmm...
Perhaps this is the answer then:

You're buying digits.

On to Clam's 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?

You ask the waiter to take it away, but nowhere is it said that he actually does. So it is possible that the coffee remains on the table, and the waiter brings just another cup, and 'it' in the last sentence refers to the coffee on the table. Then it obviously is the same.

4. can also be solved if there happens to be a cupcake baking device in the basket.

5. The forest is a subset of the sphere. For each point in the forest, take the supremum of the radii of balls around that point that are still completely in the set. Now take the supremum S over the radii. For any epsilon > 0, you can walk S - epsilon into the forest.

6. As black sheep absorb more sunlight than white sheep, they naturally gain more energy from the sunlight, thus requiring them to gain less enery from eating grass.


Simon doesn't want to post the infinite hats problem yet (and instead posted the boring 5^3 puzzle), so I'm gonna post 3 hard but elegant algorithmic puzzles here (sorry, but here you really need at least a bit of knowledge about complexity theory), so Simon can get a clear conscience that he's not posting too many puzzles while solving too few himself.

#C1: You got a http://en.wikipedia.org/wiki/Mobile_(sculpture)" class="bbc_link" target="_blank">mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.

#C2: You're given a subset of the decimal digits {0, 1, ..., 9} and a positive integer N, and you're to find out whether there is a positive multiple of N that only consist of these digits when written in decimal, and if there is, the smallest of these multiples. Run time complexity: O(N)

#C3: (This is more of an algebra problem) You're give a polynom of degree N with coefficients being integers (integers isn't really necessary here, but for computational purposes their are convenient). Your task is to find out whether it has root of degree greater than 1 in the complex numbers, i.e. a linear factor that appears at least twice. Run time complexity: O(N^2) I think

EDIT: Decided to add #C4:
Consider the following exercise, found in a generic linear algebra textbook.
Let A be an n × n matrix. Prove that the following statements are equivalent:

• (a) A is invertible.
• (b) Ax = b has exactly one solution for every n × 1 matrix b.
• (c) Ax = b is consistent for every n × 1 matrix b.
• (d) Ax = 0 has only the trivial solution x = 0.

The typical way to solve such an exercise is to show a series of implications. For instance,
one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d),
and finally that (d) implies (a). These four implications show that the four statements are
equivalent.
Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies
(b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d).
However, this way requires proving six implications, which is clearly a lot more work than
just proving four implications!
I have been given some similar tasks, and have already started proving some implications.
Now I wonder, how many more implications do I have to prove? Can you help me
determine this?
Run time complexity: O(N+M) I think, where N is the amount of statements and M the amount of implications already proven.
Hint about an algorithm required to know:

There's Tarjan's algorithm to detect strongly connected components, which has runtime O(N+M), where N is the amount of nodes and M the amount of edges.

[ccexplore]

6. As black sheep absorb more sunlight than white sheep, they naturally gain more energy from the sunlight, thus requiring them to gain less enery from eating grass.

Hmm, photosynthetic sheep?  What farm are you on again? http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

Simon doesn't want to post the infinite hats problem yet (and instead posted the boring 5^3 puzzle), so I'm gonna post 3 hard but elegant algorithmic puzzles here (sorry, but here you really need at least a bit of knowledge about complexity theory)

Yeah, I thought about posting a (relatively simple) computer science one yesterday (it's the one about linked list and loop detection, some of you probably heard of it anyhow), but just find that it's actually quite hard to rephrase the problem without making use of any computer science terminologies, and still be precise enough to disallow completely unintended answers breaking down the expected model of computation, time, and memory.  Yours are even more technical to state.  (Actually, C2 seems more like a number theory problem.)

I'm definitely going to take a break on this thread and play around with the SMS custom levels stuff happening in that other thread.  I think most of these problems are probably beyond me (or at least I'd need to go back to my old algorithm textbook to refresh memory on stuff).

[ccexplore]

#C1: You got a http://en.wikipedia.org/wiki/Mobile_(sculpture)" class="bbc_link" target="_blank">mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.

I haven't really bothered working on any of the problems, but I do have a Clam-style solution to C1:

You don't need to change any weights, since balance is determined by torque not weight.  You can just adjust the fulcrum at each bar to balance the torques. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />