Logic Question: The Hard One

[The Armchair]

No, this isn't a re-post

You're playing 2/4 Hold'em at a card barn. Underground. Illegal. All that fun stuff. Somehow, all your white and red chips turned into greens over the course of the night. (Good for you!) Unfortunately. . . well, let's start from the beginning. Or rather, the beginning of the end.

You have a counter-balance (or a scale, the one Justice holds). You know the type -- a tray on either side, tethered together by some sort of bar. Like, uh, this:

http://www.ecu.edu.au/business/justice/images/scale2.gif

Good?

Good.

You also have 12 -- count 'em, twelve poker chips. All are green and unmarked, and if you try and cash them in at the cage, you'll get your kneecaps broken. Why?

One of them is a counterfeit *gasp*!

Which one? Well, the one that weighs an amount different (could be more, could be less) than the others, of course!

Of course, you didn't know this when you tried to redeem them for your $300. The floorperson takes you into the back room, acting all Grand Inquisitor on you:

"Where'd you get the chips?"
"Tell us and we'll go easy on 'ya!"
"And... where'd you get that weird counter-balance thingy?"

You, of course, have no idea. One too many Seven-and-Sevens.

The floorperson decides that you're honestly ignorant, but decided to have some fun. He puts your counterbalance on the table and lays the 12 chips out directly in front of it. He labels them 1 through 12, and tells you he's going to call the police unless you can help him identify the counterfeit. How? Well, with the scale of course! (Good thing you had it with you.)

Only... that'd be too easy, and he's got you by the . . . yeah, those. He adds a wrinkle: You can only use the counter-balance three times.

How do you find the counterfeit chip?

Or do you just lose your ability to walk?

[M2d]

Whip out your junior inspector badge that you got from your frosted flakes when you were twelve and have been carrying around in your wallet ever since. flash it so that he can't tell exactly what it is, then demand your $300 in protection money.

[swimfan]

Take 3 sets of 4. Let's name them A, B and C.

Compare A and B. If equal, you realize C contains the counterfeit chip. Let's take 2 sets of 2 from C. Let's name them C1 and C2. Take the two chips from C1 and weigh against each other. If equal, compare one chip from C1 to one chip from C2 (if not equal, you know the counterfeit). If equal, the counterfeit is the unweighed chip from C2, if not equal it is that chip you're comparing from C2.

If A<>B, use same steps from above example (C) to determine counterfeit chip in 3 steps or less.

[aloiz]

wow this is not easy, but I think I got something. Three weighs of four each.

first weigh: 1,2,3,4 and 5,6,7,8
2nd: 1,2,6,9 and 5,3,10,11
3rd: 11,4,7,6 and 12,1,5,10

Each weigh can go left, right, or equal. Assuming the counterfeit is heavier, the following are the weighs for each number (if the counterfeit is lighter just change all the lefts to rights):
1: left, left, right
2: left, left, equal
3: left, right, equal
4: left, equal, left
5: right, right, right
6: right, left, left
7: right, equal, left
8: right, equal, equal
9: equal, left, equal
10: equal, right, right
11: equal, right, left
12: equal, equal, right

aloiz

[aloiz]

This is the way I tried first, but if A<>B which set has the counterfeit, A or B?

aloiz

[The Armchair]

The other one is surprisingly easy. This one is incredibly hard. I like the paradoxical elegance. /images/graemlins/smile.gif

[moondogg]

LOL. I ask this in interviews, but it always bowling balls where one is slightly heavier than the others. I'll have to start using this version (with your permission, of course).

Thanks

[The Armchair]

It's not "mine," per say (but the underlying story is -- modicum of creativity and all, and you have my permission to use it.) However,

do not ask this in an interview.

Not because I don't want you to, but that it's really hard. I've been asking this for almost 10 years now, and I can't give the answer w/o taking notes along the way.

If you want ones that work well in an interview, I'll give you a couple, memory providing.

[moondogg]

[ QUOTE ]

do not ask this in an interview.

Not because I don't want you to, but that it's really hard. I've been asking this for almost 10 years now, and I can't give the answer w/o taking notes along the way.




[/ QUOTE ]

Exactly. During an interview, I don't care what a person CAN do, I want to find their outer-bound, i.e. what they CAN'T do. Obviously just about nobody is going to be able to answer this question completely and correctly in an interview. But if you give them a pen and paper and 10 minutes to fool around with it, you'll get a some sort of a gauge of their problem-solving skills.

Of course, you might offend the person by asking a really hard question that they probably can't answer. That makes the rest of the interview easy: I'm definitely not going to hire this emotional tissue paper, so we can talk about the weather or sports for the remaining 5 minutes of the interview.

[The Armchair]

I'm not going to give the answer to this one, or at least not for a few days. I will tell people why they are wrong, though.

[The Armchair]

I really don't understand your answer here, but from what I gather, you seem to be on the right track.

[aloiz]

I'll try and explain a little better.
I take the numbered chips and weigh them as I stated. The combinations that I listed is how the scale will tip each time for a given numbered chip to be the counterfeit chip. So using my three weighs, chip #1 will be the counterfeit if the scale either goes left, left, right or right, right, left. If the former we know #1 is the counterfeit and is heavier. If the later we know #1 is the counterfeit and is lighter. Since (barring any errors on my part) no sequence regardless of if the conterfeit is heavier or lighter can be repeated by two different number chips we can deduce which chip is the counterfeit.

aloiz

[The Armchair]

It looks like it works. Not only is nothing repeated, but neither are any "mirrors" (that is, the mirror of r,r,l would be l,l,r). Congrats!

[jdl22]

My answer is different from the others so I'll answer in white.

<font color="white"> suppose the counterfeit chip is light.

- Put all 12 on the scale 1-6 on left 7-12 on right
- cash in heavier 6
- put 6 lighter chips on scale ABC on left DEF on right
- cash in heavier 3
- put 2 of 3 remaining chips on scale i on left ii on right
- if scale balances then the one not on the scale is the culprit
- if scale tips then the lighter side is the culprit </font>

[aloiz]

[ QUOTE ]

suppose the counterfeit chip is light.


[/ QUOTE ]
But we can't assume that. The only thing we can assume is that the counterfeit chip is either lighter or heavier but you don't know which.

aloiz

[jwvdcw]

This was definitely a tough one. I think I got it though.

<font color="white">
Let me use the following key:

U=unknown, you don't know if it is the odd chip or not
K=knownyou know it is NOT the odd chip
H=heavier,a group of balls which weighed heavier than another group of chips
L=lighter,a group of balls which weighed lighter than another group of chips

You start off with 12U.


PATH #1
Weighing #1: Weigh 4U against 4 other U.

Lets suppose the weighing is even. You are then left with 8K and 4U.

Weighing #2: Weigh 3U against 3K.

Lets assume that they are equal. Then we are left with 11K and 1U. This is the easiest path, as you only need 2 weighings(I suppose you could use your third weighing to figure out if the odd chip is heavier or lighter).



PATH#2
Weighing #1: Weigh 4U against 4 other U.

Lets suppose the weighing is even. You are then left with 8K and 4U.

Weighing #2:Weigh 3U against 3K

Lets assume that the 3U weighs more. You are now left with 3H and 9K.

Weighing #3: Weigh 1H against 1H.

Whichever one is heavier, then that one is it. If they are equal, then the U that you didn’t weigh in weighing# 3 is the heavier one.



PATH#3
Weighing #1: Weigh 4U against 4 other U.

Lets suppose the weighing is even. You are then left with 8K and 4U.

Weighing #2:Weigh 3U against 3K

Lets assume that 3U weighs less. You are now left with 3L and 9K.

Weighing #3:Weigh 1L against 1L

Whichever one is lighter, then that one is it. If they are equal, then the U that you didn’t weigh in weighing #3 is the lighter one.



PATH#4
Weighing #1: Weigh 4U against 4 other U.

If they are not balanced, then you are left with 4H, 4L, and 4K(the 4 you didn’t weigh).

Weighing #2: Place 2H and 1L on each side of the scale.

If the scale is balanced, then you can eliminate all 6 that you just weighed, so you are left with 10K and 2L.

Weighing #3: Weight 1L against the other L

Whichever one is lighter is the odd chip(Note:You could also weigh one of the Ls against a K here if you wanted to do it that way instead).



PATH#5
Weighing #1: Weigh 4U against 4 other U.

If they are not balanced, then you are left with 4H, 4L, and 4K(the 4 you didn’t weigh).

Weighing #2: Place 2H and 1L on each side of the scale.

If one side weighs more, then you are going to be left with 2 H and 1L and 8K. This might be difficult to see at first but let me illustrate. If the right side weighs more, then you know that either one of the 2H on the right side is it or the L on the left side is it. Furthermore, you know that the 2Hs on the left and the 1L on the right are now Ks. And vise versa if the left side weighs more.

Weighing #3:Weight 1H and 1L against 2K.

If the weighing is equal then the other H(the one that you did not weigh in weighing#3) is the odd chip.

If the side with the 1H and 1L is lighter, then the 1L is the odd one. If the side with the 1H and 1L is heavier, then the 1H that you just weighed is the odd one.

I'm sure it could've been said a lot easier than this, but whatever /images/graemlins/tongue.gif.</font>

[jwvdcw]

[ QUOTE ]
wow this is not easy, but I think I got something. Three weighs of four each.

first weigh: 1,2,3,4 and 5,6,7,8
2nd: 1,2,6,9 and 5,3,10,11
3rd: 11,4,7,6 and 12,1,5,10

Each weigh can go left, right, or equal. Assuming the counterfeit is heavier, the following are the weighs for each number (if the counterfeit is lighter just change all the lefts to rights):
1: left, left, right
2: left, left, equal
3: left, right, equal
4: left, equal, left
5: right, right, right
6: right, left, left
7: right, equal, left
8: right, equal, equal
9: equal, left, equal
10: equal, right, right
11: equal, right, left
12: equal, equal, right

aloiz

[/ QUOTE ]

This does appear right. My I ask how your thought process went as you came up with this?

[aloiz]

I originally tried to do something similar to your solution, although I didn't come up with what you did Path 5. Then I thought about doing three weighs of four each. I figured out that I could get enough distinct combinations of tips one way or the other regardless of whether the counterfeit was lighter or heavier (this was done more by trial an error). Then I came up with 12 distinct combinations starting with LLR, LLO, LRO... and assigned a number to each. Now that I'm going back over this I think there are 15 distinct ways, so you might be able to increase the number of chips to 15 and still determine the counterfeit chip in three weighs. I'll have to double check.

aloiz

[GuyOnTilt]

I decided to try figuring this one out...Has anybody come to the right solution yet? I don't want to look in case I see the answer...

GoT

[GuyOnTilt]

This would be really easy to do in 3 weighings if we knew if the counterfeit chip was heavy or lighter...

Jerk. /images/graemlins/tongue.gif

GoT

[jwvdcw]

[ QUOTE ]
I decided to try figuring this one out...Has anybody come to the right solution yet? I don't want to look in case I see the answer...

GoT

[/ QUOTE ]

I'm almost positive that both mine and aloiz's are correct(even though they're different). Be careful because aloiz's isn't in white if you don't want to see the answer.

[jwvdcw]

[ QUOTE ]
This would be really easy to do in 3 weighings if we knew if the counterfeit chip was heavy or lighter...

Jerk. /images/graemlins/tongue.gif

GoT

[/ QUOTE ]

that was 'the easy one.'

[Lottery Larry]

Easy one

Weigh 4 chips on each side- if the same, repeat with the last 4 chips (2 per side), then switch a chip from each side and reweigh. You'll know which chip is the bad one

if the first 8 don't balance, switch 2 chips on each side. No change, you'll know which 2 chips to use last. it changes, you know which 2 chips you moved and use those last.

[elwoodblues]

Won't you only have it narrowed down to one of two (remember you don't know if it is heavier or lighter)

1234 v. 5678 = even
9 10 v. 11 12 = 11 12 heavier
9 11 v. 10 12 = 10 12 heavier
result: either 12 is heavier or 9 is lighter

[GuyOnTilt]

Okay, I was doing this all wrong...I was doing this for more chips than 12.. /images/graemlins/tongue.gif

12 is pretty easy. Answer:

<font color="white">First, weight chips ABCD against EFGH.

If ABCD is equal to EFGH:

weigh chips IJ against AB. If they are also equal, weigh chip A versus K. If they're equal, chip L is counterfeit. If not, K is countefeit. If IJ vs. AB was not equal, weigh I against A. If they're equal, chip J is counterfeit. If not, chip I is counterfeit.

If ABCD is heavier than EFGH:

Weigh ABEF against CDGH. If ABEF is heavier, weigh A versus C. If A is heavier, A is counterfeit. If not, B is countefeit. If CDGH was heavier than ABEF, weigh C versus A. If C is heavier, it's counterfeit. If not, D is countefeit.

If EFGH is heavier than ABCD:

Again, weigh ABEF against CDGH. If ABEF is heavier, weigh E versus A. If E is heavier, E is counterfeit. If not, F is countefeit. If CDGH is heavier than ABEF, weigh G against A. If G is heavier, G is counterfeit. If not, H is counterfeit.</font>

Edit: I just edited the last paragraph to make sense, and added one sentence to the first paragraph. My solution's complete now.

Edit: Crap. I just reread my answer and it's wrong. I'll leave it up, but I'm wrong. Still working...

GoT

[jwvdcw]

[ QUOTE ]
Won't you only have it narrowed down to one of two (remember you don't know if it is heavier or lighter)

1234 v. 5678 = even
9 10 v. 11 12 = 11 12 heavier
9 11 v. 10 12 = 10 12 heavier
result: either 12 is heavier or 9 is lighter

[/ QUOTE ]

Lottery Larry was referring to the easy one in which you know that the odd one is heavier. This one is much more complicated.

[GuyOnTilt]

Edit: Deleted.

[Lottery Larry]

You're right- I forgot we don't know if it's lighter or heavier.

Not so easy... whoops.

[aloiz]

Opps made an error. There are actually only 14 distinct possiblities, and since two of them are impossible because you must weigh an even number of chips on each weigh, 12 is the max number of chips for 3 weighs.

aloiz