Nostalgia
I used to love math problems about weighing things. But then I got distracted by my own personal scale with its slowly rising numbers. However, having recently lost a few pounds, I want to get back to other scales!
Puzzle. You have a balance scale that is broken in a consistent way: if you put two objects on its two pans, the scale will show you that the left pan is heavier, lighter, or the same weight as the right pan, but it may be wrong. However, it will give the same answer each time you repeat this test with the same two weights. You have a bag of flour and a 1-kilo weight. How can you use this scale to measure out 1 kilo of flour?
Puzzle. This time, your scale is not broken, and, moreover, it is not a balance scale but a digital one that tells you the weight of the objects you put on it. The scale does have a quirk. It can only measure two objects at a time. You have 13 coins of potentially different weights. How can you figure out the total weight of the 13 coins in 8 measurements?
The next puzzle was sent to me by Konstantin Knop, a coin puzzle master. This time there is no physical scale involved; rather, some sort of god answers your questions.
Puzzle. 26 identical-looking coins are arranged in a circle. Two of the coins which are next to each other are fake. You are allowed to pick any set of coins and ask how many fake coins are in the set. What is the smallest number of questions you need to find both fake coins if you only get the answers after you have posed all your questions?
Share:
Sanandan Swaminathan:
Measuring out 1 kg of flour:
Start by putting the 1 kg weight on the left pan and nothing on the right pan. Slowly add small amounts of flour to the right pan until the scale says that the left pan is the same weight as the right pan (though this doesn’t necessarily mean that the weights on the two pans of this broken scale are equal). This equality might be shown even at the start, before any flour is added to the right pan, but this doesn’t matter. What we are interested in is having the scale show equality. Depending on the precision of the faulty scale, we might need to make some fine adjustments – by adding/removing small amounts of flour to/from the right pan a few times – before we get the scale to show equality (the scale might oscillate between showing “heavier” and “lighter” for a while). Anyway, once we get the scale to show “equality”, we know that replacing the 1 kg weight on the left pan with 1 kg of flour will also show equality. This is because the scale is known to be consistent in terms of giving the same answer for the same two weights on the two pans in multiple weighings. I assume that the inverse is true as well, though not explicitly stated in the problem: if the scale shows “equal” for weights A and B, and then we weigh A versus C where B and C weigh different, then “equal” is not the answer shown. Basically I assume that the faulty but consistent scale is not arbitrary/random.
So, on achieving “equality”, remove the 1 kg weight from the left pan, and slowly add flour to the left pan until the scale again shows that the two pans have “equal” weights. Again, some fine adjustment by adding/removing small amounts of flour from the left pan might be needed until we get “equality”. The final amount of flour on the left pan would weigh 1 kg since we simply replaced the 1 kg weight with flour.
Total weight of the 13 coins in 8 measurements:
Let the thirteen coins weigh w1, w2… w13. In the first five weighings, measure the weights of the pairs w1+w2, w3+w4, w5+w6, w7+w8, and w9+w10. Let the sum of the numbers shown for these five weighings be A (this is the sum of weights w1 through w10).
16 August 2023, 10:59 am6th weighing: w11 + w12
7th weighing: w12 + w13
8th weighing: w13 + w11
Let the sum of the numbers shown for these last three weighings be B.
B = 2 * (w11 + w12 + w13)
w11 + w12 + w13 = B/2
Thus, after 8 measurements, sum of weights of all thirteen coins is A + (B/2).
Sanandan Swaminathan:
Determining two fake coins that are adjacent somewhere in a circle of 26 coins:
Looks like this can be done with 6 questions to the god. All the questions have to be posed first, and then the two adjacent fake coins have to be determined by decoding the six answers that are given together.
One approach is to partition the coins into disjoint sets, including a set that contains coins that aren’t a part of any of the six questions. Each sequence of six responses must uniquely identify one adjacent pair as the fake pair.
Mark the coins as 1-26 in clockwise order starting from some coin. For each of the following questions, point to the appropriate coins, and ask the questions one after the other.
Q1: How many fake coins in coins numbered {11, 12, 22, 26}?
Q2: How many fake coins in coins numbered {9, 10, 15, 19}?
Q3: How many fake coins in coins numbered {7, 8, 17, 21}?
Q4: How many fake coins in coins numbered {5, 6, 14, 23}?
Q5: How many fake coins in coins numbered {3, 4, 18, 25}?
Q6: How many fake coins in coins numbered {2, 13, 16}?
Note that coins {1, 20, 24} are not a part of any question.
Here is the mapping from the god’s answers to the fake pair. On the left of the arrows, we have the god’s six answers as a ternary string (with decimal value in parentheses); on the right, we have the two adjacent fake coins identified. All 26 possibilities are covered.
000001 (1) -> Coins 1 and 2
000011 (4) -> 2 and 3
000020 (6) -> 3 and 4
000110 (12) -> 4 and 5
000200 (18) -> 5 and 6
001100 (36) -> 6 and 7
002000 (54) -> 7 and 8
011000 (108) -> 8 and 9
020000 (162) -> 9 and 10
110000 (324) -> 10 and 11
200000 (486) -> 11 and 12
100001 (244) -> 12 and 13
000101 (10) -> 13 and 14
010100 (90) -> 14 and 15
010001 (82) -> 15 and 16
001001 (28) -> 16 and 17
001010 (30) -> 17 and 18
010010 (84) -> 18 and 19
010000 (81) -> 19 and 20
001000 (27) -> 20 and 21
101000 (270) -> 21 and 22
100100 (252) -> 22 and 23
000100 (9) -> 23 and 24
000010 (3) -> 24 and 25
100010 (246) -> 25 and 26
100000 (243) -> 26 and 1
We can see that each of the 26 answer sequences above decodes to a distinct pair of adjacent fake coins (the ternary values in parentheses help check this quickly). With six questions, we can get 28 different response sequences: six zeros (one way), a single 1 answer and other answers 0 (6 ways), a single 2 answer and other answers 0 (6 ways), two single 1 answers and the other answers 0 (comb(6,2) = 15 ways). We have 26 different fake pair possibilities to decode, hence it seemed possible. Of course, it did take quite a bit of trial and error with pen and paper to come up with the above sets. Fun exercise though. It looks like 6 questions should be the minimum, given that we are restricted to asking only “how many fake coins?” questions, and all the questions must be asked in one shot before we get any answer. If we tried this with 5 questions, we would be able to cover at most 21 possibilities: five zeros (one way), a single 1 answer and other answers 0 (5 ways), a single 2 answer and other answers 0 (5 ways), two single 1 answers and the other answers 0 (comb(5,2) = 10 ways). Hence at least 6 questions needed for 26 coins, and we’ve seen that 6 questions suffice.
Tanya, thanks for the nice puzzles, especially the 26 coins one.
16 August 2023, 10:03 pmJames:
I don’t think I understand the first puzzle. It seems consistent with the puzzle statement for the balance to show “same weight” for every possible measurement. In which case it gives out no usable information at all…. Are there some other conditions that we should assume?
17 August 2023, 5:22 amSanandan Swaminathan:
James, my 2 cents, hopefully it helps… In my solution above for the flour problem, I have assumed that the inverse also holds for the condition “same weights give same answer every time”. It is stated that, if weighing A versus B gives an answer once, say “same weight”, it will give the same answer in future weighings of A versus B. If the display changes to “heavier” or “lighter” for other weighings between separate weighings of A versus B, it seems like it will switch to “equal” when A versus B is done again. It seemed reasonable to assume that the inverse is also true. If the scale shows “equal” for A versus B, and then we weigh A versus C, where B and C have different weights, then A versus C will not show “equal”. I don’t think the intent was for there to be a possibility that the scale is stuck at showing “equal” for any and every pair of weights being compared. Since it’s given that the scale “may” be wrong with answers, it’s not like it always needs to be wrong. Also, given that it is consistent, it’s not like it is giving arbitrary answers. One practical way a scale can sometimes be wrong yet consistent is for the scale to not have been perfectly balanced to begin with (under no load). I interpreted the problem simply as needing to measure 1 kg of flour by overcoming the fixed bias in the scale.
17 August 2023, 1:17 pmBert Dobbelaere:
The 26 coins problem can be solved with only three questions. Assuming numbering of the coins in range [0..25] (e.g. clockwise), the following three questions will result in a unique combination of answers for each of the 26 possibilities:
Q1: how many fake coins in {0, 1, 2, 6, 7, 8, 12, 13, 14, 18, 19, 20, 25} ?
18 August 2023, 11:40 amQ2: how many fake coins in {2, 3, 4, 6, 7, 8, 9, 10, 12, 19, 20, 21, 22} ?
Q3: how many fake coins in {1, 7, 8, 9, 10, 11, 12, 13, 14, 15, 21, 23, 24} ?
Ali Mohammadinia:
Bert Dobbelaere
2 September 2023, 4:07 amplease explaine your answer.
its correct but why?
Sanandan Swaminathan:
In my earlier posting, I had made the hasty, silly mistake of assuming that the questions have to be disjoint (distinct coins in each question). There is no such constraint given. Given Bert’s correct answer, I just wrote a short recursive program that found a solution in 2 seconds, as given below:
Q1: How many fake coins in { 6 11 14 16 17 18 19 20 21 22 23 24 25 }?
Q2: How many fake coins in { 4 8 9 10 11 12 13 14 19 22 23 24 25 }?
Q3: How many fake coins in { 2 3 7 8 12 13 14 15 16 20 21 22 23 }?
All 26 possible fake coin pairs give a different set of 3 answers. Given that the answers to 3 questions can provide upto 3^3 = 27 pointers to the fake pair, I tried to see if a cover could be found for 27 coins in a circle. The program ran for over 10 minutes, so I killed it (energy wastage). I’m wondering if there is a way to rule out the existence of a perfect cover for 27 coins without an exhaustive, resource consuming search. It would also be interesting to see if a cover can be found for 80 coins (or even 81) in a circle using just 4 questions. Or for 242 or 243 coins with 5 questions, etc.
2 September 2023, 7:33 pmAlan Listoe:
The three sets given by Bert Dobbelaere and the three given (2 Sep) by Sanandan Swaminathan all have some properties in common.
6 September 2023, 2:45 amEach set has exactly 13 coins, grouped into 4 contiguous groups of coins.
This is all necessary to ensure that each set will provide the answers 0 and 2 nine times each, and the answer 1 eight times.
A universal property for all query sets and all numbers of coins is that the answer 1 occurs once at each end of each group of coins in the set. Thus the number of answers 1 is twice the number of contiguous groups, and in particular is always even.
Thus it will not be possible to solve the 27-coin problem with only 3 sets; each set would have to provide the answer 1 nine times, which is an odd number.