Gurmeet.Net
Puzzles

## Sum and Product

### Puzzle

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?

Do not remember.

### Solution

Previous Puzzle: 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?

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