World's most popular travel blog for travel bloggers.

On the generalization of two recreational problems: request for references, if there's any

, , No Comments
Problem Detail: 

I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.

Here's the first. We have 13 balls, all looking absolutely the same, with 12 of them having the same weight; we don't know whether the ball that has a different weight is heavier or lighter. We have a balance with two arms and, using it at most 3 times, it is required to identify the ball with different weight. For the generalization below, I will consider a slightly different version of it: same scenario, but requesting the needed minimum number of times by which, in all cases, using the balance we can identify the different ball.

Here's the second. We have three card and we are in front of a door with three slot in which we can insert the cards. Each card is the correct one for exactly one slot and vice versa. Each slot is connected to a hidden circuit and, at the beginning, we don't know wheter a circuit is opened or closed (but at least one of them is opened). The door will open only if all three circuits are closed. We can change the state of a circuit solely by inserting all the three cards; when we insert all the cards, the circuits change state according to these rules: if a circuit is closed, it will open; if a circuit is opened, it will close only if the correct card is inserted in its slot. In general, without knowing the initial states of the circuits, what is the minimum number of insertions by which the door will certainly open?

We can generalize the above problems in obvious ways: the first problem by having $n$ balls (possibly, with $k$ of them having different weight), the second problem by having $n$ cards/slots/circuits (possibly, each card being correct for more than a slot/circuit).

Are these general problems new? Any similar and well-studied one?

Asked By : Immanuel Weihnachten
Answered By : Yuval Filmus

The first problem is well-known. Lots of different generalizations appear in this paper, which is listed in the Wikipedia entry on the 12 coins problem.

I've never heard of the second problem, but it is similar in spirit to the carrom board puzzle (which probably goes under other names as well), described in a note by Dijkstra. A further generalization appears in this writeup.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9289

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback