Selection of weights to weigh a thing

Posted August 8, 2008 by simpple
Categories: Puzzles

Tags: ,

(Extracted from Leino’s puzzle page)

You are given a balance (that is, a weighing machine with two trays) and a positive integer N. You are then to request a number of weights. You pick which denominations of weights you want and how many of each you want. After you receive the weights you requested, you are given a thing whose weight is an integer between 1 and N, inclusive. Using the balance and the weights you requested, you must now determine the exact weight of the thing.

As a function of N, how few weights can you get by requesting?

Advertisements

The prisoners and the switch

Posted July 23, 2008 by simpple
Categories: Puzzles

Tags: ,

(Can be found in Leino’s puzzle page)

N prisoners get together to decide on a strategy. Then, each prisoner is taken to his own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there is a switch. The switch can either be up or down. The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch. The prisoner is then taken back to his cell. The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim “Now, every prisoner has been in the room with the switch”. If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?

(Note that the initial state of the switch is unknown to the prisoners. The state of the switch is changed only by the prisoners. You may start by considering the state is originally known.)

Product and Sum (unsolved)

Posted March 15, 2008 by simpple
Categories: Puzzles

Tags: ,

(Seen in a presentation by Rineke Verbrugge, in NVTI Theory day, 2007)
Of two unknown integers, each between 2 and 99 inclusive, a person P is told the product and a person S is told the sum. When asked whether they know the two numbers, the following dialog ensues:

P: “I don’t know them.”
S: “I knew that already.”
P: “Then I now know the two numbers.”
S: “Then I now know them, too.” 

What are the two numbers? Prove that your solution is unique.

1000 bottles of wine and 10 rats

Posted March 1, 2008 by simpple
Categories: Puzzles

Tags: ,

(Can be found in Leino’s puzzle page)
A mad scientist has 1000 bottles of whine, but one of them is poisoned. He also has 10 rats, for which the poison bottle will kill in any amount, within 10 days.
The scientist wants to have a party on the 11th day, and remove the poisoned bottle until there. How can he find the right bottle?

2 pairs of gloves for 3 doctors

Posted February 15, 2008 by simpple
Categories: Puzzles

Tags: ,

(Given by Lacramioara)
Three surgeons have to operate on a patient, one at a time. But there are only two par of latex gloves, and none of the doctors wants to touch the blood of the patient. Consider that each time a surgeon removes a pair of gloves it stays inside out.

Psycho killer

Posted February 1, 2008 by simpple
Categories: Puzzles

Tags: , ,

(Can be found in Leino’s puzzle page)
A building has 16 rooms, arranged in a 4×4 grid. There is a door between every pair of adjacent rooms (“adjacent” meaning north, south, west, and east, but no diagonals). Only the room in the northeast corner has a door that leads out of the building.
In the initial configuration, there is one person in each room. The person in the southwest corner is a psycho killer. The psycho killer has the following traits: If he enters a room where there is another person, he immediately kills that person . But he also cannot stand the site of blood, so he will not enter any room where there is a dead person.
As it happened, from that initial configuration, the psycho killer managed to get out of the building after killing all the other 15 people. What path did he take?

The fake coin

Posted December 15, 2007 by simpple
Categories: Puzzles

Tags: , ,

(Can be found in Leino’s puzzle page)
You have 12 coins, 11 of which are the same weight and one counterfeit coin which has a different weight from the others. You have a balance that in each weighing tells you whether the two sides are of equal weight, or which side weighs more. How many weighings do you need to determine: which is the counterfeit coin, and whether it weighs more or less than the other coins. How?