Integer Dimensions

A large rectangle is partitioned into smaller rectangles, each of which has integer length or integer width. Prove that the large rectangle also has integer length or integer width.

This problem can be solved using graph theory, but the most elegant solution is based on some basic calculus.

Place the big rectangle in the plane so that its sides are parallel to the X and Y axes. Now integrate the function f(x)=sin(πx)sin(πy) over the boundary of any small rectangle. Since at least one of its sides has integer length, the result will be 0. If you sum all integrals taken over the boundaries of the small rectangles and cancel the opposite terms, you will get that the integral of f(x) over the boundary of the large rectangle is also equal to 0. Therefore at least one of its sides has integer length.

Fair Split

It is well known how to split fairly a cake between two people – one of them cuts, the other one picks. The question is, how can you split fairly a cake between three people?

Easy: “Fairly” means that every person gets at least 1/3 of the cake.

Hard: “Fairly” means that every person has the opportunity to get at least as much cake as any other.

Easy (Banach-Knaster method):

The first person cuts 1/3 piece of the cake. If the second person thinks it is larger than 1/3, he can trim it to 1/3. If the third person thinks the cut (and possibly trimmed) piece is larger than 1/3, he can trim it to 1/3 and keep it. Otherwise, the second person takes the piece if he decided to trim it, or the first one, in case he did not. After that, there are two people left, and they can easily split the remaining cake between them. This approach works for any number of people.

Hard (Selfridge-Conway method):

The first person cuts the cake in 3 pieces. The second one takes the biggest piece and trims it so that it becomes as large as the second biggest piece, puts the trimmings aside. The third person picks one of the three big pieces. Then, if the trimmed piece is still available, the second person takes it, if not – he picks whichever he likes. The first person takes the last remaining big piece. Among the first two people, whoever did not pick the trimmed big piece, splits the trimmings into 3 parts. The other one picks one of these parts, then the first person picks another. The last part goes to the person who split the trimmings.

Zombie Attack

Oh no, zombies are attacking your house!

Every second, a new zombie drops down on one of the 9 spots of your lawn, which is currently unoccupied. All zombies move towards your house on the left with constant speed, and each of them needs exactly 1 second to traverse a spot of the lawn. Once a zombie steps out of the lawn, it enters your house and waits there for the others (thus each zombie travels total distance between 1 and 9 spots).

Show that after some time, the total distance traversed by any 1000 consecutive zombies will be within the range of just 50 spots.

Remark: Assume your house can accommodate an unlimited amount of zombies.

Since the number of zombies on the lawn never decreases, it must stabilize at some point. Therefore after some time T, there will be exactly K zombies on the lawn at all times, 1 ≤ K ≤ 9.

Consider any 1000 consecutive zombies appearing past time T and take a picture of the lawn at the moment each of them gets dropped on it – this makes a total of 1000 pictures. Since on every picture, there are exactly K zombies, we see exactly 1000K zombies on these pictures.

Now notice that almost all of the selected 1000 zombies appear on as many pictures as lawn spots they traverse. The zombies for which this is not true are just the K zombies, which appear on the last picture. We easily see that they have traveled between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8 spots more than the number of pictures they appear on.

Similarly, on the 1000 pictures we have taken, there are K−1 additional zombies, which appear multiple times (you can see all of them on the first picture). The total number of times they show up is again between 1 + 2 + … + K − 1 and (10 − K) + (11 − K) + … + 8.

Therefore we conclude that the total distance the selected 1000 zombies travel is equal to 1000K ± {[(10 − K) + (11 − K) + … + 8] − [1 + 2 + … + K − 1]} = 1000K ± (9 − K)(K − 1).Since (9 − K)(K − 1) is a number between 0 and 16, this solves the problem.

Gold and Nickel

You have 15 identical coins – 2 of them made of pure gold and the other 13 made of nickel (covered with thin gold layer to mislead you). You also have a gold detector, with which you can detect if in any group of coins, there is at least one gold coin or not. How can you find the pure gold coins with only 7 uses of the detector?

First, we note that if we have 1 gold ball only, then we need:

  • 1 measurement in a group of 2 balls
  • 2 measurements in a group of 4 balls
  • 3 measurements in a group of 8 balls

Start by measuring 1, 2, 3, 4, 5.

  1. If there are gold balls in the group, then measure 6, 7, 8, 9, 10, 11.
    • If there are gold balls in the group, then measure 5, 6, 7.
      • If there are no gold balls among them, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 8, 9, 10, 11, so we can find the gold balls with the remaining 2 measurements.
      • If there are gold balls in 5, 6, 7, then measure 5, 8, 9. If there are gold balls there, then 5 must be gold, and we can find the other gold ball among 6, 7, 8, 9, 10, 11 with the remaining 3 measurements. If there is no gold ball among 5, 8, 9, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 6, 7, so again we can find them with only 3 measurements.
    • If there are no gold balls in the group, then measure 5, 12, 13.
      • If there are no gold balls among them, then measure 14, 15. If none of them is gold, then measure individually 1, 2, and 3 to find which are the 2 gold balls among 1, 2, 3, 4. Otherwise, there is a gold ball among 1, 2, 3, 4, and among 14, 15, and we can find them with the remaining 3 measurements.
      • If there are gold balls among 5, 12, 13, then measure 5, 14, 15. If none of them is gold, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 12, 13, so we can find them with 3 measurements. Otherwise, 5 is gold, and again we can find the other gold ball among 1, 2, 3, 4, 12, 13, 14, 15 with 3 measurements.
  2. If there are no gold balls among 1, 2, 3, 4, 5, then we measure 6, 7, 8.
    • If there are gold balls in the group, then measure 9, 10, 11, 12, 13.
      • If there are no gold balls among them, we measure individually 6, 7, 8, 14.
      • If there is a gold ball among 9, 10, 11, 12, 13, then there is another one among 6, 7, 8. We measure 8, 9. If none of them is gold, then we can find the gold among 6, 7, and the gold among 10, 11, 12, 13, with 3 measurements total. If there is a gold ball among 8, 9, then we measure 10, 11, 12, 13. If none of them is gold, then 9 is gold and we find the other gold ball among 6, 7, 8 with 2 more measurements. If there is a gold ball among 10, 11, 12, 13, then we can find it with 2 measurements. The other gold ball must be 8.
    • If there are no gold balls in the group, then measure 9, 10.
      • If there are no gold balls among them, then measure individually 11, 12, 13, 14.
      • If there are gold balls among 9, 10, then measure 11, 12, 13, 14. If there is a gold ball among them, then there is another one among 9, 10, and we can find them both with 3 measurements. Otherwise, we measure 9 and 10 individually.
Discuss this puzzle in the forum.

The Troll Brothers

There are four troll brothers – Wudhor, Xhaqan, Yijlob, and Zrowag.

  • Wudhor always says the truth.
  • Xhaqan always lies.
  • Yijlob lies or says the truth unpredictably.
  • Zrowag is deaf and never answers.

You must ask these brothers four YES/NO questions (one troll per question), and figure out their names. What questions would you ask?

Source: Puzzling StackExchange

Coming soon.

Pawns on the Chessboard

Six pawns are placed in the middle squares of the main diagonal of a chess board – b7, c6, d5, e4, f3, g2. You are allowed to take any pawn on the chessboard and replace it with two pawns – one on the square above it and one on the square on its right, in case there are empty squares there. If after several moves there are no more pawns on the main diagonal, show that all the squares above it except for h8 are covered by pawns.

Assign the following weights on the squares of the chessboard:

  • 1 on the main diagonal a8 – h1
  • 1/2 on the diagonal b8 – h2
  • 1/4 on the diagonal c8 – h3
  • 1/8 on the diagonal d8 – h4
  • 1/16 on the diagonal e8 – h5
  • 1/32 on the diagonal f8 – h6
  • 1/64 on the diagonal g8 – h7

Every time you make the splitting move, the total sum of the numbers of the squares covered by pawns remains a constant. At the beginning that sum is 6. Since 7/2 + 6/4 + 5/8 + 4/16+ 3/32 + 2/64 = 6, all 27 squares above the main diagonal, except the top-right corner (on which you can not place a pawn in any way), must be covered by pawns at the end.

Obtuse Angle

Prove that among any 9 points in (3D) space, there are three which form an obtuse angle.

Let the points be labeled A1, A2, … , A9, and P be their convex hull. If we assume that all angles among the points are not obtuse, then the interiors of the bodies P + A1, P + A2, … , P + A9 should be all disjoint. That is because, for every Ai and Aj, P must be bounded between the planes passing through Ai, Aj, and orthogonal to the segment AiAj. However, all of these 9 bodies have the same volume and are contained in the body P + P, which has 8 times larger volume. This is a contradiction, and therefore our assumption is wrong.

Cover the Grid

You must cover a 7×7 grid with L-shaped triminos and S-shaped tetrominos, without overlapping (flipping and rotating is permitted). What is the minimum number of pieces you can use in order to do this?

Remark: All pieces must be placed entirely on the board.

Consider all cells in the grid which lie in an odd row and odd column – there are 16 of them. Since each of the two pieces can cover at most 1 of these cells, we need at least 16 pieces. Giving an example with 16 pieces is easy.