Many, many moons ago there was a fair king who oversaw 10 villages. As the king, he required a village tax of 1 gold bar per day per village. Each gold bar is supposed to weigh 1000g and have the village name etched in to it. However, the king has learned through an informant that one village has been cheating him the whole time and only giving him a bar that weighs 999g.
The king is furious and orders a scale to be brought in to test the weight of the gold bars. Assuming the king has access to all the gold bars ever sent to him, how can he figure out which village has been cheating him the whole time by using the scale only once?
Comments:
Tim W - 10 years, 1 month ago
number the villages 0-9. Take ) gold bard from village 0, 1 from village 1, 2 from village 2 etc through to 9 from village 9.. and weigh the combined bars. You will be able to tell where the cheat village is by the final weight. If the final figure of the sum is 0, then village 0 was the cheat. If 9 - Village 1 Cheated If 8 - Village 2 Cheated If 7 - Village 3 Cheated If 6 - Village 4 Cheated If 5 - Village 5 Cheated If 4 - Village 6 Cheated If 3 - Village 7 Cheated If 2 - Village 8 Cheated If 1 - Village 9 Cheated
reply permalink
Jason - 10 years, 1 month ago
The King will write down on a scroll of parchment with a quill the names of the villages with the numbers 1-10 next to them:
The he will get the gold bars from what the villages have given him: 1 bar from village 1, 2 bars from village 2 ,etc..
The King will put all 55 bars on the scale and weight them. The weight should be 55000g, but it isn't, is it ?
The number of grams it is off by is the guilty village #.
reply permalink
Connor - 10 years, 1 month ago
This was the solution I came up with. You could do it with 45 bars by taking 0 from the first, 1 from the second etc.
reply permalink
Matt - 10 years, 1 month ago
Whoa!! I could have solved this but I made the assumption, since it was in ye olde times, that the scale did not give you an exact amount and that you had to compare one stack of gold to another for equivalence. I call shenanigans!! :)
reply permalink
theRemix - 10 years, 1 month ago
If you had a comparison scale, how would you have solved it?
reply permalink
El Ninja - 10 years, 1 month ago
Assuming no other village cheated, this method can use as little as 30 bars, but the difference in the angle of the scale could be two little to get a proper reading.
For a better view, using 62 bars would be enough.
We divide the gold of the 10 villages in to two groups, A and B representing the two sides of the scale.
A[0 1 2 3 4] B[5 6 7 8 9]
Then we place 1 bar of gold for the first village in each group. A[0] and B[5] respectively
and twice the gold for the second village in each group A[1], B[6] = 2
This is done for the 5 sets of vilages, resulting in a matrix:
A B G
0 5 01
1 6 02
2 7 04
3 8 08
4 9 16
A and B stand for the plates in the scale, G stands for the number of gold bars in each plate.
Measuring the angle of the scale we can deduce the village that is under performing.
The difference of the plates is equal to the row in the matrix.
Thus if the 6th village was the culprit (B[5]), the difference between the plates is only 1g with the B plate being the lightest.
Truth Table:
Village 0 =: A plate is lighter && diff is 1g
Village 1 =: A plate is lighter && diff is 2g
Village 2 =: A plate is lighter && diff is 4g
Village 3 =: A plate is lighter && diff is 8g
Village 4 =: A plate is lighter && diff is 16g
Village 5 =: B plate is lighter && diff is 1g
Village 6 =: B plate is lighter && diff is 2g
Village 7 =: B plate is lighter && diff is 4g
Village 8 =: B plate is lighter && diff is 8g
Village 9 =: B plate is lighter && diff is 16g
reply permalink
Zing - 10 years, 1 month ago
You can't rely on an angle. If one side is heavier than the other, the scale will tip all the way down.
reply permalink
El Ninja - 10 years, 1 month ago
Asumming the is a little bit of resistance (friction) at the joint of the scale, the difference can still be measured by the time it takes to touch the ground.
reply permalink
Richard J. Ross III - 10 years, 1 month ago
Easy - there's only 2 villages, the number is in binary.
reply permalink
Ezodev - 10 years, 1 month ago
Hmm, he can use scale on random bar. Then if weight isn't equal it is from cheating village. If equal, then he can use this bar as a scale until he find bar from cheating village.
You mean scale as stone that weight is equal to 1000g, right?
reply permalink
Notorious - 10 years, 1 month ago
On a smaller scale, to help in understanding lets use 2 villages:
We take 1 bar (999g or 1000g) from village 1. We take 2 bars (2000g or 1998g) from village 2.
So our total of 1 + 2 bars can be either: 2998 grams or 2999 grams.
If we only have 1 bar that weighs 999, it will be 2999 (and village 1 cheated), but if we have 2998 then village 2 cheated.
This works on a larger scale as well when we take: 1 bar from village 1 2 bars from village 2 3 bars from village 3 4 bars from village 4 ... 10 bars from village 10
Always try to break down the problem, because the number of villages is arbitrary. If we can figure out what one cheated out of two villages with only one weighing, than we can do it for any number of villages.
reply permalink
Tony B - 10 years, 1 month ago
My solution seems much simpler than the rest of these, so that makes me assume I am completely wrong.
Take one bar from each of the 10 villages (We're assuming 9 aren't cheating at all and 1 is always cheating). Put 5 bars on one half of the scale, and 5 on the other. The side that has 4999g has the cheating village on it. Simply remove two bars at a time, one from each side (Noting which side had the correct weight). When the scales become even, you know that you just removed the cheating village's bar from the previously unequal side.
reply permalink