Find the Angle

Find the measure of angle "a" in the diagram.

▸
Solution

Five Card Trick

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?

▸
Solution

Sum and Product

P is told the product of two integers chosen from [2, 99] and S is told the sum. The following dialogue ensues:

(1) P says, "I do not know the two integers."

(2) S replies, "I knew that already."

(3) P exclaims, "Ah! I now know the two numbers.",

(4) S smugly replies, "Now I know them too."

What are the two numbers?

▸
Solution

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?

▸
Solution

Empty the Bucket

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.

▸
Solution

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.

▸
Solution

Horses on Auction

You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. 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. One strategy is to pick the first horse. Can you do any better?

▸
Solution

Polya's Urn Process

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the urn with fewer balls?

▸
Solution

Flipping Bits in a Matrix

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?

▸
Solution

Rectangle with Integer Side

A big rectangle is composed of smaller non-overlapping rectangles, each having integer width or integer height or both. Prove that the big rectangle enjoys the same property.

▸
Solution

© Copyright 2008—2018, Gurmeet Manku.