Logic Puzzles

[geoo]

Here's a few more puzzles. #1 is similar in spirit to Johannes' puzzle, #2-#4 are tricky but can still be solved pretty elementarily, and for #5 the general idea is interesting, whereas fully solving it is pretty tedious and should be avoided. http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />
EDIT: Added for clarification: always prove the correctness of your result.

#1. Assume you have a chocolate bar consisting, as usual, of a number of NxM
squares arranged in a rectangular pattern. Your task is to split the bar into
small 1x1 squares (always breaking along the lines between the squares) with a
minimum number of breaks. A break consists of a straight line cut through a
piece of the bar that goes from one side to the other. You can not break the
squares. You can only break one piece at a time. Stacking two pieces and
breaking them in one go counts as two breaks. What is the minimum amount of
breaks needed?

#2. Let N be the set of integers from 0 to n-1. How many ways are there to choose subsets A, B and C of N so that the union of the three sets is N, and the intersection is the empty set? Solutions that result as permutation of another solution are counted separately.

#3. There is a positive, finite amount N of spherical planets of radius R in space. We consider a point on the surface of a planet as non-exposed if it cannot be seen from any other planet. What is the total surface (summed over all planets) that is made up by non-exposed points?

#3.5. There's an infinite amount of light bulbs in a row, labeled 1, 2, ...
At the beginning, all of them are switched off. Now you toggle the state (i.e. off -> on and on -> off) of every light bulb, then you toggle every second one (i.e. those with index numbers dividible by 2), then every third one (i.e. those with index numbers dividible by 3), and so on. Once you're done with that (haha), which ones are switched on?

#4. You're given an acute-angled (this is not actually required, but then you can freely choose the base side) triangle with a base side. You're supposed to put N disjoint rectangles into this triangle so that the first is aligned with the base side and its edges touch the other two sides, the next is aligned on top of the previous rectangle and its edges touch these same two sides of the triangle, and so on, stacking these rectangles on top of one another. What is the optimal arrangement to cover as much of the area of the triangle as possible with these N rectangles?

#5. There are two persons, A and B. There are two secret positive integers whose sum is less than 100. A is told the product of the numbers, and B is told the sum. There is the following conversation:
A: I don't know the two numbers.
B: I knew that you didn't know.
A: Now I know them.
B: Now I know them too.
What are the two numbers?

[ccexplore]

Am I the only one who finds #1 to be a complete joke?  I almost wonder if I'm misreading the puzzle statement somehow.

If you can only break one piece at a time, then each break can only increase the total number of pieces you have by 1, so duh!

Unfortunately I've been exposed to the types of puzzle as #5, but #2-#4 is new to me and does seem tricky so far.

Speaking of exposure, I've actually tried to contribute to this thread, but since I'm unable to come up with any original puzzles myself, I'm sure anything I post someone else probably already have heard.

[geoo]

Yep, #1 is totally trivial, yet most people seem to take a minute or two to realize it. I found it similar to Johannes' puzzle in that regard, though perhaps it's still a bit more obvious in the chocolate bar case.
Bonus question (still simple): Now you may stack pieces and then break them all in one go. What's the optimal solution then?

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.

EDIT: I added another one I forgot to my post, labeled #3.5 because I feel it fits in the range #2-#4 style-wise.

[alfonz1986]

Is #3  4*Pi*R^2 ? ie the surface area of one sphere.


Is #3.5  4^n, ie 1, 4, 16, 64, 256, 1024...

[geoo]

#3 is correct.

#3.5 is incorrect, but the numbers you got are a subset of the numbers that correspond to switched on light bulbs.


Here's another fun one I just remembered, don't know how well known it is:
A camper has set up his tent, and is going for a hike. He walks 2 miles to the south, 5 miles to the west, and 2 miles to the north. Having arrived at his tent again, to his dismay he sees a bear plundering his tent.
Question: What color is the bear?

[alfonz1986]

Damn, I only solved it as far as 8 before I noticed the pattern. Turns out 9 is ON as well! So the formula is a little more complex than I first thought.

EDIT: Aha! Is it all squared integers? 1,4,9,16,25,36,49,64 , n^2 ?

[geoo]

Yep, that is correct. Now prove it. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

btw, that wu::riddles site Johannes pointed to is really awesome!

[Clam]

Answer to #2:

The union of A, B, C is all numbers, so each number is contained in at least one subset. The intersection of A, B, C is empty, so each number is absent from at least one subset (i.e. present in at most two). This means each number is in either one or two of the subsets, meaning there are 6 possibilities for each number: A only, B only, C only, A and B, A and C, or B and C. There are n numbers, and thus there are 6^n ways to choose the subsets.

[alfonz1986]

#3 is actually very very easy since you didn't specify a number of planets, you only said planets, ie more than one. Therefore the rule must be identical assuming 2 or more planets up to any finite number. Solving the situation for just two planets its very easy to see that the non-exposed surface is equal to the surface area of one planet.

[geoo]

I could have put the number N for the amount of planets in the problem statement again.
Anyway, as always, you still got to prove the correctness of your solution, i.e. that it applies for any amount of arbitrarily positioned planets.
(I silently assumed in the problem statements that the correctness is to be proven, which is kinda self-evident to a mathematician.)

As for Clam's solution to #2, that is correct of course.

[ccexplore]

Hmm, I could get #4 with a lot of math (hopefully I did my math correctly too), but there's gotta be a much more elementary way to approach it if it's worthy to be a puzzle and not a mere exercise in math:

With n rectangles you can cover at most n/(n+1) of the triangle's area, by making all rectangles have the same height.

n=1: if the original rectangle has base B and altitude H, and the rectangle's width is b', then simple geometry shows its height will be H (1 - b'/B). So the ratio of rectangle's area to whole triangle is 2 * (b'/B) * (1 - b'/B).  You can then use calculus techniques (find where derivative of function is zero) to show that the maximum occurs at b'/B = 1/2, resulting in a rect/triangle ratio of 1/2 also.  So f(1)=1/2.

n from n-1:  Similarly, consider that the bottommost rectangle's width is b'.  You get a smaller triangle with base being the top edge of the rectangle, where you should fit the remaining n-1 rectangles in optimal manner.   With a bit of geometry, math and calculus similar to what we did for n=1 (which I'll gloss over because it's just literally doing the math), you wind up with this relation for f(n) the area ratio of recntangles to triangle:  f(n) = 1 / (2 - f(n-1)).

Calculating the first few values by hand (starting from f(1)=1/2) readily shows that f(n) = n/(n+1), and then formally using mathematical induction and the recurrence equation above you can formally proved that f(n) = n/(n+1).  Also as you do the math for the recurrence relation for f(n), you'll find that the value of b'/B ratio for optimal f(n)chop  is itself always equals f(n), which gives you the construction method to realize f(n).

[edit: correct a mistake in wording near the end]

[edit: move edit to correct post!]

[ccexplore]

Hmm okay, I think there's a slightly more insightful approach for #4.  But I still can't eliminate the 2 maximization problems that seem to need calculus to solve.

Instead of triangle, I think if we do the exercise on a trapezoid instead, and using 2 rectangles, one can show that the 2 rectangles must have equal height to maximize coverage of the trapezoid.

Back to the original triangle problem, you can see that the "strip" of triangle that spans over 2 consecutive rectangles in the stack, is a trapezoid.  So using the "equal height" property we can show that each pair of consecutive rectangles, and therefore all rectangles, must have equal heights.

This gets us to the desired construction more directly, but notice we still end up with 2 maximization problems to deal with:
  a) showing that we want equal height on the 2-rectangle-in-trapezoid problem
  b) Even though we show that all rectangles must have equal height, it doesn't tell you what height to use to maximize coverage for the triangle (eg. you can have the n rectangles of equal but very small heights, so that the stack leaves most of the upper portion of the triangle not covered, obviously not optimal).

So I'm not sure if we're at a better place than before, but maybe the math for these maximization problems are slightly easier?

[edit: hey, here's an improvement.  But you still have 2 maximization problems, but hopefully easier ones]

Solve the following 2 problems:
1) the 2-rectangles-in-trapezoid problem, showing that the optimal arrangement is for both rectangles equal height.
2) the 1 rectangle in triangle problem, showing that the optimal arrangement is for rectangle's height be half the triangle's altitude.

With these two properties, we can go back to show that in the original problem, each pair of consecutive rectangles must be of equal height, and at the very top, the height of that top rectangle must equal the height of the "leftover triangle tip" that we run out of rectangles to cover with.  Together we can find an explicit construction with explicit height value for each rectangle and we're done.

I'm still using calculus to solve #1 and #2, but with both problems involving only small number of rectangles, perhaps it's possible to handle them with pure geometric techniques instead?

[edit: hey, just notice the 2 sub-problems are the same]

The 2-rectangles-in-trapezoid problem is totally equivalent to the 1-rectangle in triangle problem:  to see this equivalence, just chop off two triangles from the trapezoid like this:

   ____
  /|  |\
 / |  | \
/  |  |  \
----------

[ccexplore]

Okay, I finally have a simple, non-calculus, fully geometric way to approach the one base problem in #4 (maximize area of 1 rectangle in 1 triangle), which I can only show with a diagram (too hard to draw in ASCII art for me).  I'll attach it once the diagram is drawn.

[edit: diagram attached, explanation below]

First, you can split any triangle by the altitude (top half of diagram) to get 2 right triangles, and apply the same reasoning to both "halves".  So now lets look at one of the right triangles (bottom half of diagram).

If the rectangle's height is not exactly half of the original triangle's altitude, then the corner of rectangle on the hypothenus will be off the midpoint of the hypothenus.  The rectangle splits the right triangle into 3 areas: the rectangle itself, and 2 smaller right triangles whose hypothenuses are 2 parts of the big right triangle's hypothenus.  Take the smaller of the 2 right triangles and rotate it as shown in the diagram.  Because it is the smaller of the two triangles, it will not reach or reach past the topmost vertex.

Now obviously this rotation preserves area, but notice that with this new shape of same area, you can readily identified it as 2 rectangles of identical width and height (and therefore same area) plus the leftover triangular "tip":  as shown in the bottom right part of the diagram, you get this by extending the base of the rotated right triangle to form the 2nd top rectangle.

So what we're saying is that 2 * the area of the rectangle we're trying to maximize (ie. the bottom one) + the area of the leftover tip = the whole area of the new shape = the whole area of the big right triangle we started from.  With the area of the tip being positive (or zero in the degenerate, maximal case where both smaller triangles are congruent, resulting in no tip), we see that we get 2 * area of rectangle we try to maximize is less than or equal to the area of the whole big right triangle, so area of rectangle must be less than or equal to half the whole big right triangle.  This is just another way to say that the maximum area of rectangle is half the whole big right triangle, the result we want for the base case.

[geoo]

Really interesting to see your process of breaking down your solution into increasingly elementary sub-problems, and finally solving the remaining base problem geometrically in a pretty nifty way. http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />
I still think the solution I found is a bit more short and elegant (but not quite so fully elementary as yours), even though technically it reduces the problem to an optimization problem, which has an obvious solution however:

Hint: Consider the shape of the area that is not covered by the rectangles.

Solution:Divide the tringle along the altitude into two halves and consider them separately (tringle from now on refers to one half):
The part of the triangle that is not covered by the rectangles consists of n+1 triangles which are similar to the main triangle, i.e. scaled versions of it. Let the scaling factors be denoted by l_i, 0 <= i <= n, they add up to 1, as the sum of the altitudes of the small triangles is the altitude of the main triangle. The area of each triangle is (l_i)^2*A where A is the area of the main triangle. So we want to minimize the sum over the squares of the l_i. It is kinda obvious that the value is minimal iff all l_i are equal (e.g. realize that you can lower the value if you got two l_i that are not equal by replacing both of them with their mean), proving our claim that heights of the rectangles are the same and of value h/(n+1).
(Alternatively this identity can be proven using the Cauchy-Schwartz inequality: let v = (1,...,1) and l the vector containing the l_i. Cauchy-Schwartz now implies <v,l>^2 <= |v||l| and equality iff v and l are linear dependent. Now the scalar product on the right is 1, as the l_i add up to 1, and |v|=(n+1)^2. So we got 1/(n+1)^2 as a constant lower bound on |l|, and the lower bound is reached iff all entries in l are the same.)

[ccexplore]

I've made good progress on the sphere problem, but there's a technical issue that I'm finding a little tricky to get around:

Picture the following:  imagine coloring the non-exposed areas of each planet red, and then move each planet by translation (so no orientation changes) until they all merge into one sphere (possible since all planets are same size). [Note: we're not adjusting the coloring during the translation process; another way to think of it is to map each red point of each planet onto the surface of one planet]

I can show that during this translation process, the red areas of 2 different planets will never end up as overlapping areas on the merged sphere.  This would show that the sum of red areas from all planets is less than or equal to the area of one sphere.

What I would like to then show is that every point on the merged sphere belongs to at least 1 red point of some planet, but unfortunately that is not true.  For example, with just 2 planets, when we merged the red areas together, we're missing the set of points that form the boundary of the 2 hemispheres, namely a great circle.  So I think what I need to do is also to show that the "missing points" always belong to the boundaries of red areas (this is the technical issue I need to resolve).  With that established, then I can say their inclusion or exclusion will simply add or subtract 0 from the total area, and therefore doesn't matter whether we include or exclude them.

Anyway, I'll try to fill out the details when I have time.  I find it hard to explain without a bunch of diagrams, so it's going to take some time to put everything down on paper even though intuitively the ideas are easy to grasp once seen.  And my work week has started again.