Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Puzzles: Set 6

Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8

(A) An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2x1 rectangles (dominoes) such that all squares are covered? (B) Under what circumstances would removal of two squares from an 8x8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black square, can the remaining board be tiled?

Show that a chessboard of size 2^n by 2^n can be tiled with L-shaped figures of 3 squares, such that only one square remains uncovered. In fact, the uncovered square may be any square — for every choice, there exists a tiling. In fact, the puzzle may be extended to 3D: Eight unit cubes make a cube with edge length two. We will call such a cube with one unit cube removed a "piece". A cube with edge length 2^n consists of (2^n)3 unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces.

A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip.

Alice repeatedly draws a card randomly, without replacement, from a pack of fifty-two cards. Bob has a one-time privilege to raise his hand just before a card is about to be drawn. Bob must execute his privilege before the last card is drawn. If the card drawn is Red just after Bob raises his hand, Bob wins; otherwise he loses. Is there any way for Bob to be correct more than half the times he plays this game with Alice?

At the Secret Convention of Logicians, the Master Logician placed a band on each attendee's head, such that everyone else could see it but the person themselves could not. There were many, many different colours of band. The Logicians all sat in a circle, and the Master instructed them that a bell was to be rung in the forest at regular intervals: at the moment when a Logician knew the colour on his own forehead, he was to leave at the next bell. Anyone who left at the wrong bell was clearly not a true Logician but an evil infiltrator and would be thrown out of the Convention post haste; but the Master reassures the group by stating that the puzzle would not be impossible for anybody present. How did they do it?

One of twelve coins is counterfeit: it is either heavier or lighter than the rest. Is it possible to identify the counterfeit coin in three weighings on a beam balance?

In an n by n grid of squares, two squares are neighbors if they share an edge. Initially, some squares are "infected". At successive clock ticks, an uninfected square gets infected if at least two of its neighbors are infected. How many squares must initially be infected so that all squares eventually get infected?

An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified. Variation: what if the array may be written into but must be left unmodified by the algorithm?

triangle-puzzle Find the measure of angle "a" in the diagram.

A mathemagician asks a volunteer to give him five cards drawn from a pack of fifty-two. He hands one card back to the volunteer and arranges the remaining four in some sequence he chooses. He then hands the sequence to a second volunteer and leaves the room. His assistant enters. The assistant asks the second volunteer to read out aloud the sequence handed to him. The assistant ponders a little and correctly announces the identity of the card held by the first volunteer. How could this be done? In general, how large a deck of cards can be handled if n cards are drawn initially?

© Copyright 2008—2017, Gurmeet Manku.