Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Empty the Bucket

Puzzle

Three buckets have marbles. You are allowed to double the number of marbles in a bucket by borrowing from one of the other two buckets. Prove that it is possible to produce an empty bucket with a series of such operations.

Source

Do not remember.

Solution

Previous Puzzle: Fast Bit Counting

Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer?

Next Puzzle: Balanced Coloring

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.

17 Aug 2011
© Copyright 2008—2017, Gurmeet Manku.