Finding both fake coins in a set of $5$
$begingroup$
There are $5$ rupees on Arnav's table. He knows that exactly $2$ of the rupees are counterfeit. One of these $2$ coins is lighter than a normal (non-counterfeit) rupee, and one of these $2$ coins is heavier than a normal rupee. Arnav conveniently has a balance scale next to him, and he would like to identify both fake coins, and determine which one of the fake coins is heavier and which one is lighter. What is the minimum number of weighings that Arnav needs to do so?
mathematics logical-deduction weighing coins
asked Dec 9 '18 at 10:56
user591814user591814
282
$endgroup$
add a comment |
$begingroup$
There are $5$ rupees on Arnav's table. He knows that exactly $2$ of the rupees are counterfeit. One of these $2$ coins is lighter than a normal (non-counterfeit) rupee, and one of these $2$ coins is heavier than a normal rupee. Arnav conveniently has a balance scale next to him, and he would like to identify both fake coins, and determine which one of the fake coins is heavier and which one is lighter. What is the minimum number of weighings that Arnav needs to do so?
mathematics logical-deduction weighing coins
asked Dec 9 '18 at 10:56
user591814user591814
282
$endgroup$
add a comment |
$begingroup$
There are $5$ rupees on Arnav's table. He knows that exactly $2$ of the rupees are counterfeit. One of these $2$ coins is lighter than a normal (non-counterfeit) rupee, and one of these $2$ coins is heavier than a normal rupee. Arnav conveniently has a balance scale next to him, and he would like to identify both fake coins, and determine which one of the fake coins is heavier and which one is lighter. What is the minimum number of weighings that Arnav needs to do so?
mathematics logical-deduction weighing coins
asked Dec 9 '18 at 10:56
user591814user591814
282
$endgroup$
There are $5$ rupees on Arnav's table. He knows that exactly $2$ of the rupees are counterfeit. One of these $2$ coins is lighter than a normal (non-counterfeit) rupee, and one of these $2$ coins is heavier than a normal rupee. Arnav conveniently has a balance scale next to him, and he would like to identify both fake coins, and determine which one of the fake coins is heavier and which one is lighter. What is the minimum number of weighings that Arnav needs to do so?
mathematics logical-deduction weighing coins
mathematics logical-deduction weighing coins
asked Dec 9 '18 at 10:56
user591814user591814
282
asked Dec 9 '18 at 10:56
user591814user591814
282
asked Dec 9 '18 at 10:56
user591814user591814
282
asked Dec 9 '18 at 10:56
user591814user591814
282
asked Dec 9 '18 at 10:56
user591814user591814
282
282
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
$endgroup$
add a comment |
$begingroup$
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
$endgroup$
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
add a comment |
$begingroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered 9 mins ago
deep thoughtdeep thought
3,2831738
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76232%2ffinding-both-fake-coins-in-a-set-of-5%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
$endgroup$
add a comment |
$begingroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
$endgroup$
add a comment |
$begingroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
$endgroup$
There are only 3 comparisons needed. There are 20 (=5*4) permutations of the coins (5 positions where the first counterfeit coin can be, and then only 4 positions where the other counterfeit can be located). The following image depicts those permutations (N=normal, H=heavier, L=lighter) on its left side. There are of course multiple possibilities how to solve this problem in 3 steps. The most easiest is comparing (1.) coin# 1 to coin #2 and (2.) coin#3 to coin #4; dependent on the outcome of the first comparison we then need to do different comparisons; if the outcome of (1.) was that both are equal, we need to compare one of the two to the last coin. For example: (3.) coin #1 to coin #5. If the outcome of (1.) was not equal, we can e.g. compare: (3.) coin #4 to coin #5. Having done the 3 measurements this way, we can then deduct which of the coins must be of which kind;
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
edited Dec 9 '18 at 19:31
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
answered Dec 9 '18 at 14:39
SDwarfsSDwarfs
2013
2013
add a comment |
add a comment |
$begingroup$
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
$endgroup$
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
add a comment |
$begingroup$
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
$endgroup$
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
add a comment |
$begingroup$
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
$endgroup$
Here's a solution in at most:
$6$
Reasoning:
Weigh any two coins. If they are the same, we have $3$ coins left, L, N and H. It will take $3$ further weighings to identify which is which.
If they are not the same, we know we have either LN, LH or HN. Leave these to the side, and remember which was heavier. From the remaining coins we know we have at least $2$ normal coins. Weigh any two from this set, if the same, we have a set of $3$, LNH, and we continue as before.
If different, we need $2$ further weighings to identify the fake coin, and repeat as in the first step. This is the worst case scenario, and takes a total of $6$ weighings, using our memory of a previous weighing.
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
answered Dec 9 '18 at 11:09
JonMark PerryJonMark Perry
18.6k63888
18.6k63888
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
add a comment |
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
$begingroup$
This is correct - the bound can be significantly improved.
$endgroup$
– user591814
Dec 9 '18 at 11:57
add a comment |
$begingroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered 9 mins ago
deep thoughtdeep thought
3,2831738
$endgroup$
add a comment |
$begingroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered 9 mins ago
deep thoughtdeep thought
3,2831738
$endgroup$
add a comment |
$begingroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered 9 mins ago
deep thoughtdeep thought
3,2831738
$endgroup$
Here is a short text version
- Compare A to B, and C to D.
- If A=B, they are real. Compare one to E. If E is real, then C and D are fake, and they've been compared, telling you which is heavy and which is light. If E is heavy, then C or D is light and the other is real, and they've been compared, telling you which is which. If E is light, same idea.
- If C=D, they are real. Compare one to E. Same idea.
- If neither, E is real. Compare E to any other. Say A is lighter than B and C is lighter than D. Either: A and D are real, B is heavy, and C is light; or, B and C are real, A is light, and D is heavy. Comparing E to any one of these tells you which.
answered 9 mins ago
deep thoughtdeep thought
3,2831738
answered 9 mins ago
deep thoughtdeep thought
3,2831738
answered 9 mins ago
deep thoughtdeep thought
3,2831738
answered 9 mins ago
deep thoughtdeep thought
3,2831738
3,2831738
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76232%2ffinding-both-fake-coins-in-a-set-of-5%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
