Will you finally post the answer to that 12 coins / dwarfs / dragons / jokers / gems / gold / washing machine... huh anyway :D :D :D
JeffB
Printable View
Will you finally post the answer to that 12 coins / dwarfs / dragons / jokers / gems / gold / washing machine... huh anyway :D :D :D
JeffB
Ok, if you want me to spoil the riddle then I'll do it ;) The solution is not simple by any means though.
Actually, here is the reason it's feasible :
You have to find one false coin in twelve (12) and it can be lighter or heavier (2), so you have to distinguish between 12*2 = 24 states. With one weighing you can distinguish three states : lighter, heavier or equal. With three weighings, you can distinguish 3^3 = 27 states. So since 24 < 27 you can actually solve the riddle theoretically. Now all you have to do is find an algorithm ;)
And this approach is guaranteed to return the result in three comparisons?
I would be interested in seeing a working algorithm.
There is an approach that will get the result in no more than four tries...
Divide the coins into two piles of six and weigh them.
Take the lighter pile, divide it into two piles of three
and weigh them.
if these piles weigh the same, the false coin is heavier;
divide the heavier pile of six in two piles of three and weigh them.
Select two coins from the heavier pile of three. If they weigh the same, the false coin is the one not weighed; otherwise the false coin is the heavier one.
On the other hand, if one of the two piles of three is lighter, the false coin is lighter. Select two coins from the lighter pile and weigh them. If they are equal, the false coin is the one not weighed; otherwise, it is the lighter one.
:D
As I said in the post before, it it feasible, since we can differentiate between 27 possibilities and there are only 24.
Here is a hint:
Each coin can have four different states in the process :
- You don't know anything about it. It could be the false coin (lighter or heavier) or a correct coin
- It's either the false coin and lighter or a correct coin.
- It's either the false coin and heavier or a correct coin.
- It's a correct coin.
I've left the state out when you have identified the false coin, since that's only at the end. Counting possibilities, 1) adds two possibilities, 2) and 3) add 1 possibility and 4) doesn't add any (it's certain)
In the first weighing you have 24 possibilities to start with. With one weighing you can divide that by three and remain with 8 possibilities for each outcome (pile 1 is heavier / lighter / same as pile 2).
So... The first weighing has to be four coins (pile A) versus four other coins (pile B). If A is lighter then all coins in A will be in state 2), all coins in pile B in state 3) and all coins of the remaining four will be in state 4). So we have 4 + 4 + 0 = 8 possibilities left.
If A were the same weight as B then we would know that A and B are in state 4 and the remaing 4 are in state 1), so we have 0 + 0 + 2*4 = 8 possibilities.
The rest is similar ;)
Since any one coin can be A)lighter, B)heaver, or C)equal in weight to a good coin, are there not in fact 12*3 (36)
possibilities to resolve?
No, because only one coin is false. So the correct way of calculating the possibilities is :
- choose 1 coin out of 12 to be the false coin (12 possibilities)
- choose whether it's lighter or heavier (2 possibilities)
which makes 12 * 2 = 24.
Then they are triellists, not duellists.Quote:
Originally posted by dimm_coderThere are 3 duellists:
...
They are all stand face to face ( like in triangle ).
His story checks out.Quote:
Originally posted by Simon666
I got hit by a car which may have damaged my brain. Have I mentioned yet I like [chicken chop]?
Yves,
Consider this scenario:
Pile1 and Pile2 weigh the same; this tells us that the false coin is in Pile3.
Take two coins from Pile3 and weigh them with two coins from Pile1 (Pile1 contains all good coins)
If these two coins weigh the same, you could weigh one of the untested coins from Pile 3 against a known good coin.
If the third comparison is also even, you have found the bad coin (the one not weighed from Pile3),
but you still don't know if it is heavier or lighter; you have to do a fourth comparison to find out! :(
(if you know a more efficient way to resolve this scenario, please let me know)
It's not as easy as that ;)
If you have 4 coins which you know nothing about (pile C), then you have to split the possibilities into three again. But, unluckily, 8 is not divisible by 3, so we divide the possibilities into 3, 3 and 2.
So you will weigh A1C1 (pile 1) versus C2C3 (pile 2) and leave C4 aside. If pile 1 is lighter then either C1 is false and lighter or C2 or C3 is false and heavier (3 possibilities). The same if pile 1 is heavier. If they are equal, then C4 is the false coin (2 possibilities).
So, you would recombine one of the good piles(PileA or PileB) with PileC to make 8 coins total and retest?
This is a second solution I've found, one which is much more dynamic than the first which I sent to Yves. I'll start you off: 1234v5678. If balanced, you can weigh 9(10)(11)v123 and go from there. If imbalanced, you can weigh 125v369 and go from there. See if you can finish my thought. Yves, msg me if you want me to send you this second solution (although I'll probably forget it by then...;)).
Well, it looks like your second solution is a bit closer to my original pen and paper one :)
Actually it's true that your solution to weigh 9,(10),(11) in one pile is actually nicer than mine where I weigh 1,9 vs (10),(11). But the net result is the same, you split the possibilities into 3, 3 and 2 :)
Nono :) Maybe my notation was misleading ;)Quote:
So, you would recombine one of the good piles(PileA or PileB) with PileC to make 8 coins total and retest?
A1 is the first coin from pile A. C1 is the first coin from pile C etc.
So I would weigh A1, C1 versus C2, C3 and leave C4 aside. I would only test 4 coins and not eight :)
But it's true that it's also possible by recombining to make 8 coins. After all, adding known correct coins on each side doesn't matter at all. This is what solarflare's original solution relies on (which is actually pretty nice, I have to say :) )
Thanks, Solarflare and Yves!
I understand it now:D
Theoretically, each weighing can have three outcomes: left, balanced, or right. There are originally 24 possibilities for the fake coin (12 coins, one of which is either heavier or lighter). You have three weighings, giving the possibility of narrowing it down 3^3(3 weighings, 3 possibilities each time)=27. Since 24<=27, the coin can be determined. It seems as though one of 13 coins could be determined using this information alone (26 possibilities < 27 possible outcomes) but don't be decieved. The first weighing presents a difficulty. Ideally, it should divide 26 possibilities into 8,9,or 9 possibilities. But the scale does not allow this: if balanced, the possibilities are either lighter or heavier for the coins not weighed, giving an even number of leftover possibilities. If unbalanced, there are an even number of coins on the scale (otherwise the scale would not work- same number on each side), and therefore an even number of possibilities leftover. So, the closest to 8,9,9 we can come with this scenario is 8,8,10. Since 10 isn't <= 3^2 (2 weighings left), this approach cannot always work. The only way it could work is if you had a special scale in which you could weigh 5 coins vs 4 coins, and it would tip one way if a coin on that side were heavier than average or a coin on the other side were lighter than average. This type of scale would not be a balance scale, however. In a balance scale, the side with 5 coins would always tip the scale, regardless of the location of the anomalous coin. Therefore, this problem cannot work with 13 coins unless the weighing rules were changed slightly. But it is still easily possible with 12 coins.
Hey Yves, I'm really beginning to like this problem, in case you haven't noticed ;).
I like your unbalanced scale idea ;)
Of course, you'd have to know the weight of a good coin first....
No you wouldn't, the scale would do all the work. That's why it doesn't work, because there's no such scale that does that.Quote:
Originally posted by gjs368
Of course, you'd have to know the weight of a good coin first....
Yves, got any more "interesting logical tasks" where that came from?
I know sort of a similar riddle. I think I'll post it here just for fun...
One day a big giant came down from his land to the land of the dwarves. There he captured x dwarves and took them back to his land to eat them. The giant, fortunately for the dwarves, was in a good mood and decided to give them 1 chance on freedom. Now the dwarves all have hats on but they don't know which color it is because their wives put them on, fortunately for you the dwarves only like blue and red so they only have blue and red hats. The giant told them: All of you stand in a line, you can't communicate with eachother and you don't know the colors of your hat, but, if all blue hats manage to step 1 step forward all at once and the red hats all stand still I'll let you all go free, I'll come look every morning if you'll do that, if you don't do anything at all I'll go back home and come back the next morning. If you do it wrong I'll eat you all.
Now the dwarves all went free. One day the giant came out and all the blue hats did a step forward. 2 things you need to know, the dwarves have to figure out for themselves which color their head is, no telepathy, kicking and stuff like that. Also, they all think the same solution, otherwise this won't work :-)
How did they do it?
[edit]
I forgot some stuff... Atleast both colors occur once :-) now the numbers don't manner pick any you like but if it helps you let's say 11 dwarves 6 blue ones and 5 red
[/edit]
can they see each other? and if not, what do they know?
yea they can see eachother.
they know that if they make a wrong move they die, they all think the same solution, they all know there's atleast 1 of each color and they know that each day they do nothing, nothing happens. They do get free though.
Ha, I know this one, I'll PM you the solution :)
By the way, dimm_coder has (nearly) solved the twelve coins riddle without looking at the solutions solarflare and I provided here in the thread :) That is of course if we believe him ;)
Well, dimm_coder is the godfather of this thread. Show some respect. :cool:
Ok, so we believe him then ;)
This one is particularly for solarflare, but open to everyone else (he asked for a new one, sorry ;)).
You have 9 coins with 2 false ones. The false ones are the same make, meaning that they have the same weight and are either both lighter or both heavier than a standard coin. Find out in four weighings which two coins are false and whether they are lighter or heavier than standard coins.
It's a hard one, I have to admit ;)
Wow, we are really beginning to become corrupt here, aren't we...Quote:
Originally posted by Yves M
You have 9 coins with 2 false ones.
I know you're expecting a brilliant answer immediately from me :rolleyes:, but I'm actually busy right now, so I'll come look at it later today, maybe tomorrow... ;)
No we just really like jokers :pQuote:
Originally posted by solarflare
Wow, we are really beginning to become corrupt here, aren't we...
Exactly, you have all the pressure on you ;)Quote:
I know you're expecting a brilliant answer immediately from me
Call me "treasurer" (that is to say, I solved the coins problem)
First:
Yves and others, I thank You for your reliance. ;)
Second: Please, Yves, don't post answer for task about 9 coins this week. Now I haven't enough time, but I hope to find it, and solve this task by this week:rolleyes: :)
Good luck, dimm_coder. solarflare has already nearly solved it correctly. The idea is there but there are a few small mistakes.
Argggg ! It's actually not solvable in four weighings in the general case :( Sorry, so the riddle with 2 false out of 9 is not solvable. You can do it in five weighings though.
Arg ;)
Really? I thought for sure that... oh well. Can you prove that it can't be done in 4? 'cause I thought I had it. Sometime this weekend I'll check it out.Quote:
Originally posted by Yves M
Argggg ! It's actually not solvable in four weighings in the general case :( Sorry
Highly probable, it could be just a typo, or maybe I messed up one of the weighings... a program like that is gonna be annoying to debug, its one huge series of "if" statements!Quote:
Originally posted by Yves M
solarflare has ... a few small mistakes.
By the way, here is the solution to the problem with 12 coins, one of which is false and you don't know whether it's lighter or heavier.
It's an HTML file and I hope it's clear enough :)
Of course there are many different ways of solving it, this is only one.
Well, it's not easy to prove. But in case pile A is lighter (or heavier) in the first weighing, you are left with 24 states. BUT these states can't be partioned into 8, 8, 8 or 9, 9, 6 states by any weighing. So you have to make do with 10, 7, 7 and since 10 > 3^2 you require one weighing more.Quote:
Originally posted by solarflare
Really? I thought for sure that... oh well. Can you prove that it can't be done in 4? 'cause I thought I had it. Sometime this weekend I'll check it out.
Incorrect, I believe. They can be divided into 8,8,8. More info when I pm u in a sec. (so dimm_coder doesnt see)Quote:
Originally posted by Yves M
in case pile A is lighter (or heavier) in the first weighing, you are left with 24 states. BUT these states can't be partioned into 8, 8, 8 or 9, 9, 6 states by any weighing. So you have to make do with 10, 7, 7 and since 10 > 3^2 you require one weighing more.
The 2 of 9 coins puzzle is certainly doable in 4 weighings, what I'm now wondering is whether or not it can be done in 4 predefined weighings ;)
Of course you are right ;)
Ok, so it is solvable, sorry for the Args ;)
Unfortunately, I have just proven it cannot be done this way. I'll have to stick with my original plan of attack.Quote:
Originally posted by solarflare
what I'm now wondering is whether or not it can be done in 4 predefined weighings ;)
Well nobody except solarflare seems to have tried the 9 coins 2 false problem, so I'll post the solution. Dimm_coder, you can still go on and try it, you just don't have to look at the solution ;)
here is the solution in HTML form
And for those wondering whether I did that HTML page all by hand, here is a small C++ program I wrote for generating the solution ;)
program source
Yves, if really, I spent some time near 1 hour trying to solve it, but I can't. :( Now I haven't enough time.
Don't worry it's really hard. I don't even know if solarflare tried to solve it by hand, I sure didn't ;)
If you are interested, have a look at my program which solves the problem automatically. That's what I used to generate the solution ;) I did check it by hand though, but that's a bit easier than trying to find a solution by hand.
Ok, Yves, I 'll look at your program. Thank U. :)
I tried to find solution only logical way, not programming.
Of course, it's more mathematical problem than pure logical.
New riddle
The russian mafia is looking for a hacker who will hack the World Bank for them to get tha phat loot. They are very civilised people they take their task very seriously and prepare a test for the candidates. So they kidnap their first programmer, a guy who calls himself code_by_dimm_light. Since they have a very peculiar sense of humour they present him with the following task.
He is put into a romm lit only with small candle. code_by_dimm_light suspects that the candle will go out in about five minutes so he's eager to get done with the task. Probably especially so since if he fails he'll get to see the potatoes grow from below or something to this effect.
The mafia ganglord (who shall remain unnamed for security purposes) explains the problem to him.
"Here are eight light switches in this room. This wall is in fact a window and there are eight light bulbs in the room behind it. Each switch is connected to one light bulb and vice-versa. You will have to figure out which switch is connected to which bulb. You can test a configuration by turning on the master switch here. But to make things interesting, you can only turn the master switch on three times."
The mafia sub-boss besides him mumbles somthing to the effect of "If we had a better battery you could have four tries", but is silenced directly by the ganglord.
How does code_by_dimm_light solve this task ? Will he hack the world bank or become an ex-code_by_dimm_light ?
Here is the configuration :
How should the switches be set for the three times that he can press the Master switch ?Code:O O O O O O O O <- Light bulbs
------------------------- <- Window
\ \ \ \ \ \ \ \ <- switches
X <- frightened code_by_dimm_light
M <- Master switch
C <- candle burning out
Yes, I solved it by hand, and what a waste of time it was ;). You wasted an hour and a half of my life, and I want it back! Oh who am I kidding, I'd only lose it again anyway...Quote:
Originally posted by Yves M
I don't even know if solarflare tried to solve it by hand
Wow, Yves! Ok, hehehe, I'll try it :)
I think that I mast solve it by logical way, not programming, because ganglord didn't gave computer and I haven't notebook :rolleyes:
At free time I'll try it.
Well that's still pretty good compared to me wasting something like 7 hours to write that program :pQuote:
Originally posted by solarflare
Yes, I solved it by hand, and what a waste of time it was ;). You wasted an hour and a half of my life, and I want it back! Oh who am I kidding, I'd only lose it again anyway...
True, the solution is purely logical and can be found without the usual (if this happens then do that etc...)Quote:
I think that I mast solve it by logical way, not programming, because ganglord didn't gave computer and I haven't notebook