Title: Blind Man and Cards

ID: blind

Puzzle:

A blind man was handed a deck of 52 cards with exactly 10

cards facing up. How could he divide it into two piles, each

of which having the same number of cards facing up?

Hint:

Yet to write.

Solution:

He divides the cards into two piles with 10 and 42 cards each. He

then flips all cards in the smaller pile.

2.

Title: Rope

ID: rope

Puzzle:

Rajeev is trapped atop a building 200m high. He has with him

a rope 150m long. There is a hook at the top where he

stands. Looking down, he notices that midway between him and

the ground, at a height of 100m, there is a ledge with

another hook. In his pocket lies a Swiss knife. Hmm... how

might he be able to come down using the rope, the two hooks

and the Swiss knife?

Hint:

Yet to write.

Solution:

Cut rope into 50m and 100m pieces. Tie one end of the 50m piece to

the top hook and make a noose at the other end. Pass the 100m piece

through the noose and tie its two ends.

3.

Title: Three boxes and a Ruby

ID: ruby

Puzzle:

Alice places three identical boxes on a table. She has

concealed a precious ruby in one of them. The other two

boxes are empty. Bob is allowed to pick one of the boxes.

Among the two boxes remaining on the table, at least one is

empty. Alice then removes one empty box from the table. Bob

is now allowed to open either the box he picked, or the box

lying on the table. If he opens the box with the ruby, he

gets a kiss from Alice (which he values more than the ruby,

of course). What should Bob do?

Hint:

Yet to write.

Solution:

If Bob switches his choice, he wins with probability 2/3.

Title: Choice of Three

ID: three

Puzzle:

In the previous problem, Bob had to pick one of the three

boxes lying on the table. If he wished to select them with

equal probability, how could he do it by using a penny in

his pocket? What if the penny was biased?

Hint:

Yet to write.

Solution:

Toss the coin twice. Let TH, HT and TT correspond to the three

boxes. If HH, repeat.

Title: Treasure Island

ID: island

Puzzle:

An old parchment contains directions to a treasure chest

buried in an island:

"There is an old unmarked grave

and two tall oak trees. Walk from the grave to the left tree,

counting the number of steps. Upon reaching the left tree, turn

left and walk the same number of steps. Mark the point with a

flag. Return to the grave. Now, walk towards the right tree,

counting the number of steps. Upon reaching the right tree, turn

right and walk the same number of steps. Mark this point with

another flag. The treasure lies at the midpoint of the two

flags"

A party of sailors reached the island. They find a pair of

tall oak trees merrily swaying in the wind. However, the

unmarked grave is nowhere to be found. They are planning to

dig up the entire island. It'll take a month. Can they do any

better?

Hint:

Yet to write.

Solution:

Yet to write.

Title: 30 Coins

ID: coins

Puzzle:

30 coins of arbitrary denominations are laid out in a row.

Ram and Maya alternately pick one of the two coins at the

ends of the row. Could Maya ever collect more money than Ram?

Hint:

Yet to write.

Solution:

The first player could pick all coins in odd-numbered positions or

all coins in even-numbered positions, whichever set is larger in

value.

Title: Cake Cutting

ID: cake

Puzzle:

Mary baked a rectangular cake. Merlin secretly carved out a

small rectangular piece, ate it and vanished! The remaining

cake has to be split evenly between Mary's two kids. How could

this be done with only one cut through the cake?

Hint:

Yet to write.

Solution:

Cut along the line joining the centers of the two rectangles.

Title: Cube Problems

ID: cube

Puzzle:

Imagine a cube on a flat table, tantalizingly balanced on one of

its vertices such that the vertex most distant from it is

vertically above it. (a) What is the length of the shortest path an

ant could take to go from the topmost vertex to the bottommost

vertex? (b) What will be the projection on the table

if there is a light source right above the cube? (c) What would be

the cross-section obtained if we slice the cube along a plane

parallel to the table, passing through the midpoint of the

topmost and the bottommost points of the cube?

Hint:

Yet to write.

Solution:

(a) Square-root of five times the side of the cube, (b) Regular

hexagon, (c) Regular hexagon.

Title: Tiling a Chessboard

ID: chessboard

Puzzle:

An 8x8 chessboard has had two of its diagonally opposite squares

removed, leaving it with sixty-two squares. Is it possible to

tile it with non-overlapping 2x1 rectangles such that all

squares are covered?

Hint:

Yet to write.

Solution:

Both squares have the same color.

Title: Cubes in Cube

ID: cubeslice

Puzzle:

Imagine a 3x3x3 solid cube. How many cuts do we need to break it

into twenty-seven 1x1x1 cubes? How about an n x n x n cube? What

if we are not allowed to stack pieces and cut them together?

Is there a way to repeatedly hop from a small cube to an

adjacent small cube (sharing a surface) within the large 3x3x3

cube such that there is a closed path covering all small cubes,

without ever passing through a small cube twice?

Hint:

Yet to write.

Solution:

The central 1x1x1 cube in a 3x3x3 cube has six faces, no two of

which can be revealed in a single cut. For the general a x b x c

cuboid, we need f(a) + f(b) + f(c) cuts, where f(y) = ⌈ log y

/ log 2 ⌉. This can be proved by induction. Note that at any point,

the "largest" cuboid requires the most steps; others can be sliced

in parallel with this cuboid. When the "largest" cuboid has

dimensions a x b x c, there are exactly 3 choices: to slice along

one of the three sides. For a lying in the range (2^i, 2^(i+1)], any

cut that results in the new "largest cuboid" being z x b x c, where

z lies in the range (2^(i-1), 2^i], is optimal. This is because f(z)

for all these z's is identical. For example, for 10 x 34 x 98

cuboid, any of the following could be the maximal cuboid for the

remaining steps:

5 x 34 x 100 6 x 34 x 100 7 x 34 x 100 8 x 34 x 100 | 10 x 17 x 100 10 x 18 x 100 10 x 19 x 100 ... and so on till 10 x 32 x 100 | 10 x 34 x 49 10 x 34 x 50 10 x 34 x 51 10 x 34 x 52 .. and so on till 10 x 34 x 64. |

If a slice can pass through exactly one existing cuboid, then the

number of slices is n

^{3}- 1 because a slice increases the

total number of cuboids by exactly 1.

Title: Forty-five Minutes

ID: fortyfive

Puzzle:

How do we measure forty-five minutes using two identical

wires, each of which takes an hour to burn. We have

matchsticks with us. And yeah, the wires burn non-uniformly.

Hint:

Yet to write.

Solution:

Light three out of four ends. When two ends meet, light the fourth.

Section: Easy

Title: Bigger or Smaller

ID: biggersmaller

Puzzle:

Alice writes two distinct real numbers between 0 and 1 on

two chits of paper. Bob selects one of the chits randomly to

inspect it. He then has to declare whether the number he

sees is the bigger or smaller of the two. Is there any way

he can expect to be correct more than half the times Alice

plays this game with him?

Hint:

Yet to write.

Solution:

Let the number revealed to Bob be x. Then Bob should say "bigger"

with probability x, "smaller" otherwise.

Title: Thousand Jars

ID: thousandjars

Puzzle:

Imagine an array of one thousand jars, labeled one thru

thousand. Jars can be colored red or black. Initially, all jars

are red. The color of a jar changes on successive days as

follows: On the i-th day, jars whose labels are divisible

exactly by i, switch their color. How many jars are red at

the end of the thousandth day?

Hint:

Yet to write.

Solution:

A number has an odd number of divisors iff it is square.

Title: Working Computer

ID: workingcomputer

Puzzle:

A room has n computers, less than half of which are

damaged. It is possible to query a computer about the status of

any computer. A damaged computer could give wrong answers. The

goal is to discover an undamaged computer in as few queries as

possible.

Hint:

Yet to write.

Solution:

(a) Pick a computer at random. Ask other computer whether it is

damaged or not.

(b) Yet to write a second solution.

Title: Average Salary

ID: averagesalary

Puzzle:

Four honest and hard-working computer engineers are sipping

coffee at Starbucks. They wish to compute their average

salary. However, nobody is willing to reveal an iota of

information about his/her own salary to anybody else. How do

they do it?

Hint:

Yet to write.

Solution:

The first engineer picks a random k-digit integer for some large k,

adds his salary to it and writes the sum on a chit. The chit is

passed around. When it returns to the first engineer, he subtracts

the k-digit integer.

Title: Number Guessing Game I

ID: numberguessingi

Puzzle:

Shankar chooses a number between 1 and 1000. Geeta has to guess the

chosen number as quickly as possible. Shankar will let Geeta know

whether her guess is smaller than, larger than or equal to the

number. (a) What should Geeta's strategy be? (B) In a modified

version of the game, Geeta loses if her guess is "larger than the

number" two or more times. (c) What if Shankar is allowed to choose

an arbitrarily large number?

Hint:

Yet to write.

Solution:

(a) Binary search. (b) and (c) Guess 1, 4, 9, 16, 25, and so on, to

discover k such that Shankar's number lies between k

^{2}and

(k+1)

^{2}. Then guess k+1, k+2, k+3 and so on. On the

whole, this requires O(√n) steps.

Title: Number Guessing Game II

ID: numberguessingii

Puzzle:

Shankar chooses a number uniformly at random between 1 and

1000. Geeta has to guess the chosen number as quickly as

possible. Shankar will let Geeta know whether her guess is smaller

than, larger than or equal to the number. If Geeta's guess is larger

than the number, Shankar replaces the number with another number

chosen uniformly at random [1, 1000]. (a) What should Geeta's strategy

be? (b) In a modified version of the game, Shankar gets to choose a

number arbitrarily / adversarially. (c) And finally, what if Shankar

just says "equal to" or "not equal to" when Geeta guesses (the rest

of the setup remains the same)?

Hint:

Yet to write.

Solution:

(a) Repeatedly guess g = n - n/k until Shankar says "greater

than". Then guess g+1, g+2, g+3 and so on. The expected number of

steps is ≈ k + n/2k, which is minimized for k ≈

√(n/2). (b) and (c) Yet to write.

Title: Four Ships

ID: fourships

Puzzle:

Four ships are sailing on a 2D planet. Each ships traverses

a straight line at constant speed. Their journeys started at

some time in the distant past. Sometimes, a pair of ships

collides. A ship continues its journey even after a collision.

However, it is strong enough only to survive two collisions; it

dies when it collides a third time. The situation is grim.

Five of six possible collisions have already taken place and two

ships are out of commission. What fate awaits the remaining two?

Hint:

Yet to write.

Solution:

Let z-axis denote time. Then the four trajectories are straight

lines. Three of the lines are known to be coplanar. The fourth line

intersects two of these three. Still, the sixth collision may or may

not happen!

Title: f(f(x))

ID: ffx

Puzzle:

Is it possible to write a function

*int f(int x)*in

C that satisfies f(f(x)) == -x? Without globals and static

variables? Is it possible to construct a function f mapping

rationals to rationals such that f(f(x)) = 1/x?

Hint:

Yet to write.

Solution:

Function f can be defined iff we can divide non-zero integers into

quadruples of the form (a, b, -a, -b). This is because f(0) must be

0. For any other integer "a", let f(a) = b. Then f(b) = -a, f(-a) =

-b and f(-b) = a. Now, C integers are either 32-bit or 64-bit. So

it is impossible to create such quadruples because the number of

positive and the number of negative integers are not the same!

Title: Measuring Weights

ID: measuringweights

Puzzle:

(a) Customers at a grocer's shop always want an integral

number pounds of wheat, between 1 pound and 40 pounds. The

grocer prefers to measure wheat in

exactly one weighing with a beam balance. What is the least

number of weights he

needs? (b) Customers come to a pawn shop with antiques. An

antique always weighs an integral number of pounds,

somewhere between 1 pound and 80 pounds. The owner of the

pawn shop is free to do as many weighings as necessary to

ascertain the unknown integral weight by using a beam

balance. What is the least number of weights he needs?

Hint:

Yet to write.

Solution:

(a) Four weights: 1, 3, 9 and 27. (b) Four weights: 2, 6, 18 and 54.

Title: Counting with a Magical Bird

ID: magicalbird

Puzzle:

An evil goblin assembles 100 gnomes together. He tells them

that they will be locked up into individual cells. Each

cell will have a window and a large supply of

grains. Thereafter, a magical bird will hop from window to

window, ad infinitum. Initially, the bird is white in

color, and it will switch its color from white to black and

vice versa if a grain is fed to it. The bird will be fair

in the sense that it will visit every cell infinitely often.

As soon as some gnome is sure that the bird has visited

every cell, he should say "abracadabra" aloud. If the bird

has indeed visited every cell, all gnomes will be

released. Otherwise, all of them will be killed. The gnomes

have ten minutes to arrive at a strategy. How can they save

themselves?

Hint:

Yet to write.

Solution:

Yet to write.

Title: Troll n Gnomes

ID: trollgnomes

Puzzle:

An evil troll once captured a bunch of gnomes and told them,

"Tomorrow, I will make you stand

in a file, ordered by height such that the tallest gnome can

see everybody in front of him. I will place either a white

cap or a black cap on each head. Then, starting from the

tallest, each gnome has to declare aloud what he thinks the

color of his own cap is. In the end, those who were correct

will be spared; others will be eaten, silently."

The gnomes set thinking and came up with a strategy. How many

of them survived? What if hats come in 10 different colors?

Hint:

Yet to write.

Solution:

The tallest gnome should declare the "parity". For example, he could

say "white" iff the number of white caps he sees is odd.

Section: Moderate

Title: Red-black Squares

ID: redblacksquares

Puzzle:

Given k arbitrary points in a grid of size m by n, is it

always possible to color them either red or black such that

each row and each column is balanced? A row or column is

said to be balanced if the difference in the number of red

and black points in it is at most one.

Hint:

Yet to write.

Solution:

Thanks to Iman

Hajirasouliha for this elegant solution!

Model the grid with a bipartite graph G[X, Y], a vertex in

part X for each row and a vertex in part Y for each

column. Add edges between x

_{i}and y

_{j}

iff there is a point in the corresponding place. If G has a

cycle (it must be an even cycle), we color the edges

alternatively and remove those edges, continuing this

procedure we can assume that G is a tree. When G is a tree,

we can solve the problem by induction on the number of edges

as follows: remove e a leaf edge, color the remaining edges

balanced, now look at the parent of that leaf and choose the

right color for e to maintain the induction hypothesis.

Title: Four Cards

ID: fourcards

Puzzle:

Four cards are placed on a square table, one card at each

corner. A blind gnome and an evil goblin take turns to play

the following game. The blind gnome gets to choose a subset

of the four cards and flip them simultaneously. If all four

cards are face up, he wins the game. Otherwise, the evil

goblin get to rotate the table by an amount of his choice.

Show that for any initial configuration of cards chosen by

the evil goblin, the blind gnome can win the game in a

finite number of steps with a

*deterministic*

strategy.

Hint:

Solution: Yet to write.

Title: And-Or Gates

ID: andorgates

Puzzle:

Alice and Bob were working in the hardware design lab one

morning giving final touches to their 4-bit microprocessor,

when suddenly they discovered that three of their NOT gates

were malfunctioning! They opened the inventory cupboard and

received another shock: only two NOT gates were available.

"Look. All we have is hundreds of AND

and OR gates but just two NOT's! Damn! Just six hours before

the deadline. We're out of luck. Any ideas?", asked

Alice.

"Well, we obviously cannot hope to

get three NOTs out of two NOTs", replied Bob.

"I guess you're right ...", said Alice

with a frown on her face and her shoulders dropping. Then

suddenly she jumped and said, "No, wait!

It can be done! Here it it!" And pulling out a pen

from her pocket, she sketched a circuit of a piece of paper.

"Wow! You're a genius, Alice!",

cried Bob.

Are you as smart as Alice? In general, how

many signals can we invert using n NOT gates and any number

of AND and OR gates? No other gates may be used.

Hint:

Yet to write.

Solution:

Yet to write.

Title: Dijkstra's Problem

ID: dijkstra

Puzzle:

There are n+1 processors named 0, 1, ..., n. Processor i has

a counter C(i) that takes values in the range [0, n]. Its

initial value is arbitrarily chosen from [0, n]. Processor 0

is said to be

*privileged*if C(0) = C(n). Processor

i, where i > 0, is said to be privileged if C(i) is not equal

to C(i-1).

At successive clock ticks, exactly one out of

possibly several privileged processors is arbitrarily chosen

and its counter is updated as follows:

If processor 0 is chosen, we set C(0) =

(C(0) + 1) mod (n+1).

Otherwise, we set

C(i) = C(i+1).

Prove that after a bounded number of clock

ticks, exactly one processor will be privileged. And that

this will continue to hold forever.

Hint:

Yet to write.

Solution:

Yet to write.

Title: Tiling Problem

ID: tiling

Puzzle:

A big rectangle is composed of smaller rectangles, each having an

integral width or integral height or both. Does the big

rectangle enjoy the same property?

Hint:

Yet to write.

Solution:

Yet to write.

Title: Marked Squares

ID: markedsquares

Puzzle:

Consider an n by n grid of squares. A square is said to be a

neighbour of another one if it lies directly above/below or

to its right/left. Thus, each square has at most four

neighbours. Initially, some squares are marked. At

successive clock ticks, an unmarked square marks itself if

at least two of its neighbours are marked. What is the

minimum number of squares we need to mark initially so that

all squares eventually get marked?

Hint:

Yet to write.

Solution:

Yet to write.

Title: Horses on Auction

ID: horsesauction

Puzzle:

You are the chief guest at an auction, where an unknown

number of horses will be revealed and auctioned, one after

the other, in no particular order. You are a connoiseur of

horses, and can judge whether one horse is 'better' than

another. Being the chief guest, you have a one-time

privilege of selecting a horse, after it is revealed, but

before it gets auctioned off. You get to keep this horse

for yourself. Your objective is to maximize the probability

of selecting the best horse. What do you do?

Hint:

Yet to write.

Solution:

Strategy: Pick the first horse that is superior to all horses that

have been revealed so far. Analysis: If the very first horse is the

k-th best horse, then the probability of picking the best horse with

this strategy is 1 / (k - 1). The overall probability of picking

the best horse is approximately [c + log (n - 1)] / n where c is

Euler's constant. One could extend this idea to wait even more,

i.e., pick the s-th horse that beats all horses that went

by. Identifying the optimal value of s is an interesting

exercise. Is s = 1 optimal?

Title: Red Card

ID: redcard

Puzzle:

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. 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?

Hint:

Yet to write.

Solution:

No, Bob cannot be right more than half the times. Yet to write proof.

Title: Geometry without a Ruler

ID: noruler

Puzzle:

Using only a compass (and without a straight edge or a ruler),

is it possible to identify (a) the midpoint of two points? (b)

the center of a circle? (c) all four corners of a square, given

two of them?

Hint:

Yet to write.

Solution:

Using only a compass, all those points can be constructed which can

be constructed using a compass and a ruler. Surprising, isn't it!

The constructions are far more complicated though.

Title: Chessboard with Signs

ID: chessboardsigns

Puzzle:

An 8x8 chessboard has either a plus or a minus written in each

of its sixty-four squares. You are allowed to repeatedly choose

a 3x3 or a 4x4 block of squares and invert all signs within

it. How would you go about getting rid of all the minuses?

Hint:

Yet to write.

Solution:

There are 36 3x3 blocks and 25 4x4 blocks. An arbitrarily long

sequence of inversions is equivalent to inverting some subset of

these 36 + 25 = 61 blocks in any order. Thus at most 2^61 distinct

chessboard positions can be derived if we start with all minuses.

Title: Five Card Trick

ID: fivecardtrick

Puzzle:

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?

Hint:

Yet to write.

Solution:

Yet to write.

## No comments:

Post a Comment