Which Coin is False ----- ---- -- ----- Consider the following problem. You are given N coins, exactly 1 of which is false, in that its weight differs from the others, though you do not know whether the false coin is lighter or heavier than it should be. You are also given 1 additional coin known to be true and a scale. You are asked to make a series of weighings of equal numbers of the coins and at the end tell which coin is false. You are asked to minimize the number of weighings required. Professor Toowit Toowoo (TT to his friends) has come up with the following strategy for solving this problem. There are two cases: first, where you do not know whether the false coin is lighter than or heavier than a true coin, and second where you do know. If you do know whether the false coin is lighter than or heavier than a true coin, divide the N coins into three almost equal groups, and weigh two of these that have equal numbers of coins against each other. The result will tell you which of the three groups the false coin is in. If on the other hand you do NOT know whether the false coin is lighter than or heavier than a true coin, divide the N coins into three groups two of which have the same number J of coins, and weigh these two groups against each other. If the scale balances, the false coin is in the group not weighed. Otherwise, move some number K of the coins originally on the left scale to the right scale, replacing them by coins not originally weighed, and remove K coins origin- ally on the right scale, so they are not weighed. This second weighing has three outcomes. If the scales now balance, the false coin was removed from the right scale. If the balance (which side is heavier) changes, the false coin was moved from the left to the right scale. If the balance remains the same, the false coin was not moved from either scale. In the first two cases, you now know whether the false coin is lighter than or heavier than a true coin. In the last case, you still do not know. If N is 2, then you can use the 1 known true coin to solve the problem with a single weighing, as a special case. Notice that the number of weighings necessary may depend upon the actual results of the weighings. For example, if N=5, the first step might be to weigh 2 coins against 2 coins, and in the best case the scale balances and the false coin is known immediately to be the coin you did not weigh. But in the worst case, where the scale is unbalanced, you have to move 1 coin from one scale to the other, and if the scale remains unbalanced, then you have only narrowed it down to 2 coins and need a third weighing. We want to use TT's strategy to minimize the number of weighings required if every result turns out to be worst case. Thus you are asked to find the minimum worst case number of weighings needed to solve the problem using TT's strategy, for a given N, and to find the number J to be used in the first weighing, and the number K to be used in the second weighing should the first weighing not balance. Input ----- One line for each test case. This line just contains N, with 3 <= N <= 500. The input ends with an end of file. Output ------ One line for each case. This line contains W J K where W is the minimum worst case number of weighings required using TT's strategy to solve the problem for N coins, when you do NOT know whether the false coin is lighter or heavier than a true coin; J is the number of coins on each scale in the first weighing; and K is the number of coins moved in the second weighing if the first weighing has an imbalance. If several values of J give the same W, output only the minimum such J. If for this J several values of K give the same W, output only the minimum such K. Example Input ------- ----- 3 4 5 6 7 8 0 Example Output ------- ------ 2 1 1 2 1 1 3 1 1 3 1 1 3 2 1 3 2 1 Note: This problem is derived from a problem stated in `Engaging Students with Theory', by Shilov and Yi, Communications of the ACM, Sept 2002, Vol. 45 No. 9, p 98. File: whichcoin.txt Author: Bob Walton Date: Sun Oct 19 08:27:39 EDT 2003 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2003/10/19 12:35:01 $ $RCSfile: whichcoin.txt,v $ $Revision: 1.8 $