Find a stone which is not the lightest one [closed]
$begingroup$
I've gotten this riddle and have been struggling with solving it:
Suppose you have 20 stones which have different weights [0 ... n] . You have no way of measuring the weight of any stone individually, instead you can only measure them by putting 10 on each side of a balance. After doing this you see which "group" of stones is heavier. You can do this only 10 times in total. You can also switch the stones from either side to the other as much as you want between the measurements.
Your task is to find a stone for which you can be certain is not the lightest of them all.
All the stones are marked, so you always know which is which. Their appearance or anything similar does not help you with to determine their weight, the only way you can do it is by putting it on the balance.
weighing
edited Apr 25 at 21:06
Gilles
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
$endgroup$
closed as off-topic by Rubio♦ May 4 at 5:25
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This looks like a puzzle you found elsewhere. For content you did not create yourself, proper attribution is required. If you have permission to repost this, please edit to include (at minimum) where it came from, then vote to reopen. Posts which use someone else's content without attribution are generally deleted." – Rubio
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
I've gotten this riddle and have been struggling with solving it:
Suppose you have 20 stones which have different weights [0 ... n] . You have no way of measuring the weight of any stone individually, instead you can only measure them by putting 10 on each side of a balance. After doing this you see which "group" of stones is heavier. You can do this only 10 times in total. You can also switch the stones from either side to the other as much as you want between the measurements.
Your task is to find a stone for which you can be certain is not the lightest of them all.
All the stones are marked, so you always know which is which. Their appearance or anything similar does not help you with to determine their weight, the only way you can do it is by putting it on the balance.
weighing
edited Apr 25 at 21:06
Gilles
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
$endgroup$
closed as off-topic by Rubio♦ May 4 at 5:25
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This looks like a puzzle you found elsewhere. For content you did not create yourself, proper attribution is required. If you have permission to repost this, please edit to include (at minimum) where it came from, then vote to reopen. Posts which use someone else's content without attribution are generally deleted." – Rubio
If this question can be reworded to fit the rules in the help center, please edit the question.
5
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24
add a comment |
$begingroup$
I've gotten this riddle and have been struggling with solving it:
Suppose you have 20 stones which have different weights [0 ... n] . You have no way of measuring the weight of any stone individually, instead you can only measure them by putting 10 on each side of a balance. After doing this you see which "group" of stones is heavier. You can do this only 10 times in total. You can also switch the stones from either side to the other as much as you want between the measurements.
Your task is to find a stone for which you can be certain is not the lightest of them all.
All the stones are marked, so you always know which is which. Their appearance or anything similar does not help you with to determine their weight, the only way you can do it is by putting it on the balance.
weighing
edited Apr 25 at 21:06
Gilles
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
$endgroup$
I've gotten this riddle and have been struggling with solving it:
Suppose you have 20 stones which have different weights [0 ... n] . You have no way of measuring the weight of any stone individually, instead you can only measure them by putting 10 on each side of a balance. After doing this you see which "group" of stones is heavier. You can do this only 10 times in total. You can also switch the stones from either side to the other as much as you want between the measurements.
Your task is to find a stone for which you can be certain is not the lightest of them all.
All the stones are marked, so you always know which is which. Their appearance or anything similar does not help you with to determine their weight, the only way you can do it is by putting it on the balance.
weighing
weighing
edited Apr 25 at 21:06
Gilles
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
edited Apr 25 at 21:06
Gilles
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
edited Apr 25 at 21:06
Gilles
3,44531937
edited Apr 25 at 21:06
Gilles
3,44531937
edited Apr 25 at 21:06
Gilles
3,44531937
3,44531937
asked Apr 25 at 12:46
podloga123podloga123
533
asked Apr 25 at 12:46
podloga123podloga123
533
asked Apr 25 at 12:46
podloga123podloga123
533
533
closed as off-topic by Rubio♦ May 4 at 5:25
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This looks like a puzzle you found elsewhere. For content you did not create yourself, proper attribution is required. If you have permission to repost this, please edit to include (at minimum) where it came from, then vote to reopen. Posts which use someone else's content without attribution are generally deleted." – Rubio
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Rubio♦ May 4 at 5:25
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This looks like a puzzle you found elsewhere. For content you did not create yourself, proper attribution is required. If you have permission to repost this, please edit to include (at minimum) where it came from, then vote to reopen. Posts which use someone else's content without attribution are generally deleted." – Rubio
If this question can be reworded to fit the rules in the help center, please edit the question.
5
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24
add a comment |
5
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24
5
5
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Measure 10 and 10.
In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.
At some point, the balance turns around.
The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.
If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.
answered Apr 25 at 13:20
HermesHermes
655111
$endgroup$
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
add a comment |
$begingroup$
Here's a solution that needs at most
5
weighings.
For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.
Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.
Step one:
Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2
Step two:
Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3
Step three:
Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4
Step four:
Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5
And there's your answer!
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
$endgroup$
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
add a comment |
$begingroup$
An optimization on Hermes's solution:
You have 2n stones numbered 0 to 2n-1.
Weigh stones 0..n-1 against stones n..2n-1.
If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.
Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.
Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.
To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.
From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.
This method requires at most 5 weighings for 20 stones.
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Measure 10 and 10.
In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.
At some point, the balance turns around.
The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.
If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.
answered Apr 25 at 13:20
HermesHermes
655111
$endgroup$
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
add a comment |
$begingroup$
Measure 10 and 10.
In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.
At some point, the balance turns around.
The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.
If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.
answered Apr 25 at 13:20
HermesHermes
655111
$endgroup$
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
add a comment |
$begingroup$
Measure 10 and 10.
In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.
At some point, the balance turns around.
The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.
If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.
answered Apr 25 at 13:20
HermesHermes
655111
$endgroup$
Measure 10 and 10.
In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.
At some point, the balance turns around.
The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.
If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.
answered Apr 25 at 13:20
HermesHermes
655111
answered Apr 25 at 13:20
HermesHermes
655111
answered Apr 25 at 13:20
HermesHermes
655111
answered Apr 25 at 13:20
HermesHermes
655111
655111
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
add a comment |
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
You didn't explicitly mention this, but it is impossible for the two scales to ever be equal with the given set of stones. But this solution would still work even if the weights were such that the scales could be balanced, provided you know that there is at least one stone that has a unique weight.
$endgroup$
– Jaap Scherphuis
Apr 25 at 13:51
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
$begingroup$
Well, never mind my previous comment about being late; I found a better solution.
$endgroup$
– Brandon_J
Apr 26 at 0:41
add a comment |
$begingroup$
Here's a solution that needs at most
5
weighings.
For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.
Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.
Step one:
Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2
Step two:
Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3
Step three:
Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4
Step four:
Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5
And there's your answer!
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
$endgroup$
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
add a comment |
$begingroup$
Here's a solution that needs at most
5
weighings.
For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.
Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.
Step one:
Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2
Step two:
Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3
Step three:
Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4
Step four:
Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5
And there's your answer!
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
$endgroup$
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
add a comment |
$begingroup$
Here's a solution that needs at most
5
weighings.
For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.
Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.
Step one:
Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2
Step two:
Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3
Step three:
Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4
Step four:
Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5
And there's your answer!
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
$endgroup$
Here's a solution that needs at most
5
weighings.
For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.
Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.
Step one:
Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2
Step two:
Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3
Step three:
Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4
Step four:
Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5
And there's your answer!
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
edited Apr 28 at 1:20
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
answered Apr 25 at 13:23
Brandon_JBrandon_J
4,420550
4,420550
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
add a comment |
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
What if neither side is heavier?
$endgroup$
– noedne
Apr 26 at 0:46
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne see JaapScherpius's comment above. Also, if neither side is heavier, a not-lightest stone could be identified in two weighings, one swap.
$endgroup$
– Brandon_J
Apr 26 at 0:51
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
$begingroup$
@noedne here's the better solution.
$endgroup$
– Brandon_J
Apr 26 at 1:31
add a comment |
$begingroup$
An optimization on Hermes's solution:
You have 2n stones numbered 0 to 2n-1.
Weigh stones 0..n-1 against stones n..2n-1.
If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.
Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.
Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.
To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.
From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.
This method requires at most 5 weighings for 20 stones.
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
$endgroup$
add a comment |
$begingroup$
An optimization on Hermes's solution:
You have 2n stones numbered 0 to 2n-1.
Weigh stones 0..n-1 against stones n..2n-1.
If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.
Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.
Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.
To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.
From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.
This method requires at most 5 weighings for 20 stones.
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
$endgroup$
add a comment |
$begingroup$
An optimization on Hermes's solution:
You have 2n stones numbered 0 to 2n-1.
Weigh stones 0..n-1 against stones n..2n-1.
If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.
Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.
Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.
To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.
From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.
This method requires at most 5 weighings for 20 stones.
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
$endgroup$
An optimization on Hermes's solution:
You have 2n stones numbered 0 to 2n-1.
Weigh stones 0..n-1 against stones n..2n-1.
If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.
Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.
Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.
To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.
From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.
This method requires at most 5 weighings for 20 stones.
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
answered Apr 28 at 10:47
Florian FFlorian F
9,91412462
9,91412462
add a comment |
add a comment |
5
$begingroup$
Please give credit to the author of the puzzle.
$endgroup$
– Gilles
Apr 25 at 21:06
$begingroup$
I have a new and improved solution!
$endgroup$
– Brandon_J
Apr 26 at 0:35
$begingroup$
One person noted attribution is required; 5 people upvoted that comment. NOBODY flagged or voted to close (we have a close reason specifically for this). Quick reminder: If you can tell (with reasonable certainty) that the OP is not posting their own content, we want to close that question until the attribution/no-plagiarism requirement is met, before people spend time answering something that may well end up closed and perhaps deleted.
$endgroup$
– Rubio♦
May 4 at 5:24