Problem of the Day
A new programming or logic puzzle every Mon-Fri

King's Gold

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?

Permalink: http://problemotd.com/problem/kings-gold/

Comments:

  • Tim W - 10 years, 8 months 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, 8 months 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:

    1. Ye Olde Village1
    2. Ye Olde Village2
    3. Ye Olde Village3 ..
    4. Ye Olde Village10

    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, 8 months 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, 8 months 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, 8 months ago

    If you had a comparison scale, how would you have solved it?

    reply permalink

  • El Ninja - 10 years, 8 months 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, 8 months 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, 8 months 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, 8 months ago

    Easy - there's only 2 villages, the number is in binary.

    reply permalink

  • Ezodev - 10 years, 8 months 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, 8 months 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, 7 months 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

Content curated by @MaxBurstein