Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.