Anyone want a challenging question? (1 Viewer)

[drolle]

Here's one of my favourite questions that I've ever solved -- it lasted for weeks of a few minutes a day!

It's actually a modified (by me!) version of a very well known type of question, the "find the counterfeit coin in x weighings with a balance scale" question.

I found it in a puzzle book, but I changed it a bit to make it harder. So here it is:

Say you have a pile coins, that all appear identical, and a balance scale. You know that one and only one is counterfeit, and that the counterfeit coin is either heavier or lighter than the others.

If there are a small number of coins, say 5, you can find the counterfeit coin easily in three weighings on the balance scale. But what if there's more? It gets harder and harder to solve. So the question is, what is the maximum number of coins (call it X) which allows you to always be able to find the counterfeit coin in 3 or less weighings, how do you do it with X coins, and prove that you can't always do it with X+1 coins.

If this is too difficult, start with only 2 weighings (it's harder than it sounds!), then work up to 3. Once you've done 3, try 4, and even 5 weighings! Each one has a new trick that you have to use to find the counterfeit, that's one of the reasons I love this problem.

Then, find a formula for the value of X, when you're allowed N weighings. (this is probably the easiest part of the problem)

Then, if you're still after more (by this point I'd been working on the problem for a very long time, but I was enjoying it so much I wanted to make it harder) write an algorithm for finding the counterfeit coin that will work for any number of weighings!

If any of this is unclear, let me know. Please post your thoughts on this problem, and I'd be very interested to see if anyone solves the whole thing or even part of it! (my maths teachers couldn't get past even the first part)

I'm sure people will want to post their comments / solutions on this thread (unless it turns out I'm the only one weird enough to do this kind of problem for fun), so I'd advise against reading too much further untill you've tried the problem yourself.

Enjoy!

EDIT:
Given that so far only spice girl and blackjack have responded to this question so far, I'm guessing a lot of people are putting it in the "too hard" basket.

If you fall into that catagory, here is one of the easier permutations of the question for you: if you are given 4 coins and told that one is counterfeit, can you figure out how to identify it in only 2 weighings?

Also I forgot to say explicitly that you are not allowed to use anything other than the coins in the pile (ie no other weights or reference coins).

 

[spice girl]

X = 2^N ?

 

[BlackJack]

Oh, um you can find the counterfeit in 2 weighings for 5 coins.

 

[spice girl]

Originally posted by BlackJack
Oh, um you can find the counterfeit in 2 weighings for 5 coins.

how?

 

[drolle]

it's not X = 2^N, but you've got the right idea.

I found it more fun to work at the problem from a practical perspective first though, rather than going straight for the formula

Umm... I haven't looked at this problem for a few months so I could be wrong, but I'm 99% sure I proved that you can only do 4 coins with 2 weighings, and I proved it from a practical approach as well as the "splitting the universes" mathematical approach. I'll check it again when I get a minute.

Yep, I just checked and if you can do more than 4.5 coins in 2 weighings then my idea of the basic laws of maths needs some very severe overhauling!

 

[drolle]

Hint: X is more than 8 when N = 3

 

[spice girl]

Originally posted by drolle
it's not X = 2^N, but you've got the right idea.

I found it more fun to work at the problem from a practical perspective first though, rather than going straight for the formula

Umm... I haven't looked at this problem for a few months so I could be wrong, but I'm 99% sure I proved that you can only do 4 coins with 2 weighings, and I proved it from a practical approach as well as the "splitting the universes" mathematical approach. I'll check it again when I get a minute.

Yep, I just checked and if you can do more than 4.5 coins in 2 weighings then my idea of the basic laws of maths needs some very severe overhauling!

Well firstly I did work the problem out properly, so X = 2^N is not a guess. I just haven't posted the whole solution so others can have a go.

And besides the reason why you can't do 9 coins when N=3 is the same reason why you can't do 5 coins with N=2.

Show me how to do 9 coins with 3 weighings.

 

[drolle]

When I woke up this afternoon at 3pm (gotta love those byron bay NYE parties!) I realised there was a flaw in the proof I used when I said "if you can do more than 4.5 coins in 2 weighings then my idea of the basic laws of maths needs some very severe overhauling!". But I made a new proof that limits X <= 4 when N = 2.

No, you've missed some things in your sol'n spice girl, the same reasons don't limit X <= 8 when N = 3. (I said this was a tough question didn't I )

Yes you can do 9 coins in 3 weighings, I'll send you a PM telling you how, or anyone else who asks me.

 

[spice girl]

Originally posted by drolle
Yes you can do 9 coins in 3 weighings, I'll send you a PM telling you how, or anyone else who asks me.

well?

 

[drolle]

I couldn't send it to you because your mailbox was full.
I've sent it now though.

 

[BlackJack]

Okay... I was thinking of a different problem. Back on track...

max for 2 is four...

I'm not getting max for 3 is nine yet...

 

[drolle]

yeah I figured you probably were thinking of just your standard "one coin is heavier" problem.

Just to clarify, just cause I said you can do 9 for N=3 doesn't mean it's the maximum.

 

[BlackJack]

ah.... you CAN do 9 with three weighings... Now to prove whether there can be more... edit: ....wait a minute... more edit: ...no I'm right...

conc: have found max for 3 weighings...

 

[spice girl]

ok there's no full solution cos it's just a guess:

my guess is X(3) = 11 where X(N) = max X for N weighings.

And the recurrence is X(n+1) = 3X(n) - 1

or something like that

someone can solve the recurrence for me

 

[drolle]

Originally posted by spice girl
ok there's no full solution cos it's just a guess:

my guess is X(3) = 11 where X(N) = max X for N weighings.

And the recurrence is X(n+1) = 3X(n) - 1

or something like that

someone can solve the recurrence for me

I'll let you think about it for a while longer before I say anything about your guess, but I think that recurrence would be X(N) = 7/18 x 3^N + 1/2. (blech!)

and while we're defining functions, how about we number coins 1,2,3,... and use
1,2,3 / 4,5,6 to mean weigh 1,2, and 3 against 4,5, and 6?

Also we can have L for left side goes down, R for right, and - for balanced. in multiple weighings, you could say the result was (L,L,R).

 

[drolle]

this is just to let you know I added some stuff to the end of the opening post... something for people who find this question too daunting, and a clarification.

 

[drolle]

Originally posted by spice girl
ok there's no full solution cos it's just a guess:

my guess is X(3) = 11 where X(N) = max X for N weighings.

And the recurrence is X(n+1) = 3X(n) - 1

or something like that

someone can solve the recurrence for me

Ok I can't wait any longer (low self-control strikes again!), so...

(Warning: Minor spoiler ahead)

You're getting warmer, but still not high enough yet!

 

[BlackJack]

Well... have confirmed the blech formula for a particular method of finding the counterfeit coin for 3,4, 5 and 6 weighings... working on the theory for this method... Not breaking new ground yet.

I wonder what wuld be the name for it if it was an algorithm... Not the greedy algorithm, but hopefully something as humourous.

Can we go higher? (rhetoric)
*tense as search continues...*

 

[spice girl]

Well, after 2 boring hours on the train to canberra I've managed to come up with: Xk = integer part of (3^N)/2

this is the theoretical maximum because of the fact that each weighing gives you either L, M, R (base 3 information), and that you don't know whether it's heavier or lighter (divide by 2).

And yes there's an algorithm for doing 3^N / 2 (and it can be proven by induction).

It basically involves finding the optimal number of coins you should weigh on the first go. The recurrence for that is Wk = 3*W(k-1) + 2.

Using a more complex form of the 5 coins in 2 weighings using 1 real coin, you can weigh the rest of the coins in N-1 weighings (if you did the above first weighing and got a balanced result (M). The recurrence for this is Uk = 3*U(k-1) - 1

For 3 weighings, W3 = 8, U3 = 5.

Algorithm will be up maybe in several days time

ciao

 

[drolle]

nice work spice girl!