Sorting Puzzle (Take 2) ... ISE ...

[b-e-a-n-s]

What is the fewest number of weighings needed to find the odd ball out of 22,964 balls if all you know is that ONE ball is heavier or lighter than the other 22,963?

[robichelli]

Well, the largest number would be 22,963. Now all we have to do is work backwards from there

[ralphmerridew]

I think 10 will do.

[Cadmium]

[happy happy joy joy-mode]
Uhm, 1 weighing? Hypothetically speaking, you could pick two balls including the right ball, compare them and then you know which ball is heaver than the others . But that a change I wouldn't take.
[/happy happy joy joy-mode]

If you divide all balls in two groups and compare them, one groups lighter. Take the other group and divide it in two.....and so on until there are 2 left. Or am I overseeing something here?

------------------
There are three kinds of people, those who can count and those who cannot.

[Orbiting]

ummm... yeah, you might pick the right two balls to start out with, but then how would you know which one was the different one?

Seriously though, the half-then-half-again would be my method of choice, except that at some point fairly quickly you get an odd number of balls and have to use a different procedure. I didn't work through the rest of it, so I don't have a good answer.

-o-

[Zealot]

Do thirds instead of halves... and you end up with the answer ralphmerridew got.

[Quailman]

araya (anyone remember him?) had put up the formula for figuring this in the discussion of The Counterfeit Coin a couple years ago. I could figure out the method for the counterfeit coin, but I didn't follow the math, nor do I remember it.

[ralphmerridew]

Cadmium: You don't know whether the ball is lighter or heavier.

[CrystyB]

I'm quoting here from a file which i saved 3 years ago - i actually never had the time to thoroughly check it BTW. Ths first part is the header, which is irrelevant except if anyone wants to track this (but i'm not sure how helpfull it is in THAT case ).

Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.69.0.28]) by bloom-picayune.MIT.EDU (8.6.13/2.3JIK) with SMTP id PAA05127; Sat, 20 Apr 1996 15:09:33 -0400
Received: from [199.164.164.1] by MIT.EDU with SMTP
id AA15782; Sat, 20 Apr 96 14:12:20 EDT
Received: by questrel.questrel.com (940816.SGI.8.6.9/940406.SGI)
for news-answers-request@mit.edu id LAA25252; Sat, 20 Apr 1996 11:13:19 -0700
Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
From: chris@questrel.questrel.com (Chris Cole)
Subject: rec.puzzles Archive (logic), part 26 of 35
Message-Id: <puzzles/archive/logic/part5_745653851@questrel.com>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
and answers that may be of interest to
puzzle enthusiasts.
Part 1 contains the index to the archive.
Read the rec.puzzles FAQ for more information.


==> logic/weighing/balance.p <==
You are given 12 identical-looking coins, one of which is counterfeit
and weighs slightly more or less (you don't know which) than the
others. You are given a balance scale which lets you put the same
number of coins on each side and observe which side (if either) is
heavier. How can you identify the counterfeit and tell whether it
is heavy or light, in 3 weighings?

More generally, you are given N coins, one of which is heavy or light.

==> logic/weighing/balance.s <==
Martin Gardner gave a neat solution to this problem.

Assume that you are allowed W weighings. Write down the 3^W possible length W strings of the symbols '0', '1', and '2'. Eliminate the three such strings that consist of only one symbol repeated W times.

For each string, find the first symbol that is different from the symbol preceeding it. Consider that pair of symbols. If that pair is not 01, 12, or 20, cross out that string. In other words, we only allow strings of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^W-3)/2 strings left. This is how many coins you can handle in W weighings.

Perform W weighings as follows:

For weighing I, take all the coins that have a 0 in string
position I, and weigh them against all the coins that have
a 2 in string position I.

If the side with the 0's in position I goes down, write down
a 0. If the other side goes down, write down a 2. Otherwise,
write down a 1.

After the W weighings, you have written down an W symbol string. If your string matches the string on one of the coins, then that is the odd coin, and it is heavy. If none of them match, than change every 2 to a 0 in your string, and every 0 to a 2. You will then have a string that matches one of the coins, and that coin is lighter than the others.

Note that if you only have to identify the odd coin, but don't have to determine if it is heavy or light, you can handle (3^W-3)/2+1 coins. Label the extra coin with a string of all 1's, and use the above method.

Note also that you can handle (3^W-3)/2+1 coins if you *do* have to determine whether it is heavy or light, provided you have a single reference coin available, which you know has the correct weight. You do this by labelling the extra coin with a string of all 2s. This results in it being placed on the same side of the scales each time, and in that side of the scales having one more coin than the other each time. So you put the reference coin on the other side of the scales to the "all 2s" coin on each weighing.

Proving that this works is straightforward, once you notice that the method of string construction makes sure that in each position, 1/3 of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a string occurs, then the string obtained by replacing each 0 with a 2 and each 2 with a 0 does not occur.

If you already know the odd coin is heavy (or light), you can handle 3^W coins. Given W weighings, there can only be 3^W possible combinations of balances, left pan heavy, and right pan heavy.

The algorithm in this case:

Divide the coins into three equal groups... A, B, and C. Weigh A against B. If a pan sinks, it contains the heavy coin, otherwise, the heavy coin is in group C. If your group size is 1, you've found the coin, otherwise recurse on the group containing the heavy coin.

[CrystyB]

incidentally, with 10 weighings, the coins could be as much as 29523.

Ow and bah @ mith for posting that AFTER i searched my hard-drive... :P

[This message has been edited by CrystyB (edited 04-11-2002 10:10 PM).]

[mith]

http://www.greylabyrinth.com/Puzzles/answer019.htm

[Sumudu2]

what do you do when the number of coins is not divisible by 3?

[CrystyB]

Weigh the required number regardless. If the balance doesn't tip, you have 2N known goodies, from which you can add to the leftover pile to make up to N.