Waisting My Time? Possible?

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!:D

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.

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 :p

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?" :)

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

NotLKH is referring to the Chinese Remainder Theorem

Quote:

---

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:

Quote:

---

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

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. :)

Quote:

---

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.

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).

Quote:

---

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 :confused: ? So now we don't know if the side with 5 is heavier or not and have just wasted a weighing?

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.

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.