Waisting My Time? Possible?

[ThomasJones]

Hello,

I was presented a problem and I am sure it is possible. Sort of hard for me to explain but here goes:

I have a random number within a set of 256 numbers (i.e 0-255, 1-256, -1-254 etc...) I need to be able to figure out what the number is using 7 or less questions (for lack of a better term).

I started out by taking the mid points of the range but it did not work. For example (Using 0-255):

A - Is the number > 256/2? [i.e. 128]
-------If yes then
-------------(b)Is the number > (256 - (256/2)) + ((256/2)/2) [i.e 192]
------------------If yes then
-------------------------(c)Is the number > (256 - etc...) [i.e. 224]
------------------If no then etc...
--------------------------------If Yes Then etc..
--------------------------------If No Then etc...

It always takes me 8 questions to get the answer using mid points when I need 7. I've been trying for a while using other methods. Is this possible?

Thanks for helping me bring closure!

[Guv]

In theory, you need 8 questions. In practice, you could get lucky.

After 6 questions, you should be down to 4 choices. You then have a 1/4 chance of guessing which. The seventh question would narrow it to two, with no questions left.

Note that using 7 questions and guessing (50-50 hance) might get the correct number, but you would not know if it were the correct one.

If you had 256 doors, with a prize behind one. Asking 7 questions and guessing which of two doors would be your best strategy.

[sql_lall]

If the questions have to have yes/no answers, then the best you can get is 2^7/2^8 = 50% probability

However, if you can ask questions that have more than 2 possible answers, then it might be possible.
Like, splitting it into three groups each time, not too, and having 'maybe' as an answer

[twanvl]

If you can only ask 7 questions, each question needs to have 256^1/7 ~= 2.20817902 answers. But if a question can have more then one answer, why not ask "which one is the right number?"

[NotLKH]

I just tested a theory, and it turns out to be valid.
All the numbers from 0 to 255 each has a unique Primal Coordinate, useing 2, 3, 5, 7, and 11.

ie, if you have a Number X, and do the following assignments:

c2 = X mod 2
c3 = X mod 3
c5 = X mod 5
c7 = X mod 7
c11 = X mod 11

you will find, in actuality, all the numbers from 0 thru 2309 {2*3*5*7*11 - 1} {{2310 is identical to 0}} all produce unique c sets.

I know this isn't the answer, {after all, you could do the same with Mod 10, Mod 100, and Mod 1000, which illustrates its just asking what the number is} but I thought it interesting.

The problem sounds similar to a Balance Scale problem, where, given a group of identically shaped items, and knowing they all weigh the same, except for 1, find the one thats different, with X comparisons.




-Lou

[bugzpodder]

NotLKH is referring to the Chinese Remainder Theorem

[NotLKH]

Originally posted by bugzpodder
NotLKH is referring to the Chinese Remainder Theorem

Hmm, Cool! I've played with it off an on for years, and now I know its name!

You might want to check this link out:

http://www.oz.net/~alden/puzzles/balls.html

It poses the following question:

You are given 12 seemingly identical metal balls, but one of them weighs slightly more or less than the others. With a balance scale and three weighings only, how can it be determined which is the oddball and whether it is heavier or lighter

Perhaps this concept could be adapted to your problem? Hmm, Dim WhichOne(255) as integer, All are equal to 0 except a randomely chosen one, which = 1, thus establishing "weight", {and it would take 1 variable out, you'd know the random number weighs more than the rest}
and your scale would, when given two sub arrays, weigh them against each other, and return 0, 1, or 2, indicating 0 = They weigh identically, 1 = the first array weighs more, 2 = the second array weighs more, puzzled....

hmmm...

No, thats not right. Your scale should return only 2 answers, so have it return 0 if equal or 1 if not. hmmm.
-Lou

[ThomasJones]

Thanks for all the advice!! I will take into consideration every post. I really will. I've been struggling with this for a while and I now have some new interesting light shed on the problem.

[alkatran]

You are given 12 seemingly identical metal balls, but one of them weighs slightly more or less than the others. With a balance scale and three weighings only, how can it be determined which is the oddball and whether it is heavier or lighter

Easy stuff

First of all, seperate the balls into 3 groups of 4, take groups A and B and place them on the scale.

Assuming there is an imbalance:

We now know all of group C is balanced.
We remove 2 bags from group A and 1 from group B.
Now, switch one bag from A with a bag from C

It'll look something like this:
AAB - BAC (off) A B B CCC

Now we place them on the scale, so:
-If the scale tips to the OPPOSITE side it originally tipped towards, we know that it is one of the bags we switched.
-If it tips in the same direction, it's one of the bags we didn't touch
-if it doesn't tip it's one of the bags we removed

No matter what comes out here we have 3 bags that are still not proven as balanced (or 2 in one case, but that's better then 3)

Place 1 of the 3 bags on each side, depending on where it tips/doesn't tip we can figure out if it's heavier/lighter and which it is by looking at previous weighs.


Now, assuming it is balanced.

We now Groups A and B are balanced, C is unknown.
Put 3 bags from C on one side and one bag from C with a bag from A or B on the other.
CC - CA (off)C AAAABBBB


If the scale doesn't tip we know it's the C we didn't weigh. If that hapens we just compare it to one we know is balanced.. easy stuff.
If the scale tips, take one C from the CC side, compare it to a balanced bag. We then use those results along with previous to know which.

[Guv]

The problem can be solved with 13 balls if you have a 14th known to be standard.

The solution is essentially the one posted by Alkatran, except that the first weighing tests 4 balls against 5. The standard ball is used on the side with only 4 unknowns.

If the scale balances, follow the posted solution. If the scale does not balance, you have 9 candidates for the odd ball. The second weighing follows the posted scheme: Swap 3, leave 3 as is, and remove 3 from the scale.

The method generalizes for more balls. I think you can do 39 with four weighings (40 if you have a standard ball), and 120 with 5 weighings (121 if you have a standard ball).

[alkatran]

tests 4 balls against 5. The standard ball is used on the side with only 4 unknowns.

If the scale balances, follow the posted solution. If the scale does not balance, you have 9 candidates for the odd ball

If they were all the "correct" weight it should tip towards the side with 5 balls ? So now we don't know if the side with 5 is heavier or not and have just wasted a weighing?

[Guv]

Alkatran: The first weighing I proposed was five versus five, or ten balls. Nine unknowns and one known to be standard.

The 12 ball (or 12 coin) problem is a variation on a 13 ball problem, which can be solved in 3 weighings due to having a 14th ball known to be standard.

[Kantalope]

Back to the original question - using the midpoint method it will always take 8 questions because you reduce the range of possible answers by half for each question:

1- 128
2- 64
3- 32
4- 16
5- 8
6- 4
7- 2
8- 1

The question would be - is there a way to speed up this regression.