My top Riddles
Solution:
Riddle 1: You are given an array of length n+1 of integers between 1 and n. Find in constant memory and linear time a value that repeats itself. Note that you cannot change the array and that the array does not necessarily contain all values between 1 and n.
Solution:
Riddle 2: There are 11 integers that satisfy the following constraints: each 10 of them can be partitioned to groups of 5 of an equal sum. Prove that all 11 integers are equal.
Riddle 3: There are 2n colinear points on the plane, half blue and half red. Prove the existence of a perfect matching (set of straight lines) between the two sets that do not intersect.
Solution:
Solution:
Riddle 4: 100 ants on a 1 meter stick. Each ant is facing towards an arbitrary endpoint of the stick. All ant move at 1 cm/s. When 2 ants collide they reverse their directions. When an ant reaches the end of the stick it falls. After how many seconds it is guaranteed that all ant fell of the stick?
Solution:
Riddle 5: In a dark room there are n boxes in a row. A rabbit sits in one of them and your goal is to shoot him. You shoot one box at a time. If you hit the rabbit you win. Otherwise, the rabbit jumps to one of his neighboring boxes. Devise a minimal (in bullets) series of shots that guarantees hitting the rabbit.
Solution:
Riddle 6: 2 players (red & blue) color edges of a black infinite grid. Each turn one player chooses a black edge and changes its color to his color. Red starts and his goal is to close a cycle. Blue's goal is preventing red from closing a cycle. Who wins?
Solution:
Riddle 7: Two players, a deck of 16 cards: 1,2,...,16. The cards are randomly equally partitioned between the players. A counter start at 0 (mod 17). Player 1 starts. Each turn one player (if it's his turn) throws one of his cards x and increases the counter by x (mod 17). If the counter is 0, that player wins. Otherwise the turn goes to the other player. With what probability player 1 wins?
Solution:
Riddle 8: You and your friend devise a strategy for the following scenario: Your friend will enter a room with a chessboard. On each of the 64 squares there is a coin showing either heads or tails (both of you don't know the configuration in advance). A laser will point your friend on one square. Then all he is allowed to do is flip one coin and go home. Now, you enter and you must point the square that the laser showed.
Solution:
Riddle 9: 4 lions stand on the vertices of a square looking towards their clockwise neighbor. The lions start to move at a speed of 1 m/s (at each point in time all lions move directly to their clockwise neighbor, not necessarily in straight lines). Analyze this process (will they converge? will they diverge? will they circle?).
Solution:
Riddle 10: You are given an NxM size chocolate bar. At each step you are allowed to take one chunk (you cannot put one chunk on another) of chocolate and break it according to a horizontal/vertical line. What is the best algorithm to separate all N*M chocolate pieces (in terms of number of cuts).
Riddle 11: You are given an array R representing pixelated rocks (see example below). Imagine you fill the gaps with water, how much water can you pour without it leaking out? Devise a linear time algorithm that uses constant memory (you are only allowed to read R) that solves this problem.
The example below corresponds to R = [1,3,1,4,1,2]. The answer is 3.
Solution:
water = 0, start = 0, end = len(R)-1
while start < end:
rocks = 0, i = 1
if R[start] <= R[end]:
curr = start, limit = end, direction = 1
else:
curr = end, limit = start, direction = -1
while R[curr+i*direction] < R[curr] and
if direction*(limit - (curr+i*direction) ) <= 0:
break
rocks += R[curr+i*direction]
i++
water += (i-1)*R[curr] - rocks
if curr == start:
start = curr+i*direction
else:
end = curr+i*direction
return water
Riddle 12: A game between black and white. In an array of length n, 4 checker pieces (2 are black and 2 white) are scattered in A. The initial configuration must satisfy that the order of the pieces is B,W,B,W (see example below). At each move, a player takes one of his pieces and moves it to some square within its borders (i.e. not crossing its sorrowing pieces/edges of A, see example below). The loser is the player who cannot move any of his pieces at his turn. You are given a configuration of the game, which color wins?
Solution:
Riddle 13: You have a herd of an odd number of elephants and notice that whenever one of
the herd is missing the remaining elephants can be split into two equal-sized groups
so that the total weight of each group is the same. Prove that all the elephants
have the same weight when: a) All weights are natural numbers. b) General case.
Solution: