How to pick n-1 out of n winners?
February 1st, 2011 at 10:54:33 PM
permalink
To make the question a bit simpler I'll use a specific number. Let's say there are 8 events such as tossing a coin all with 50/50 probability. In order to guarantee guessing the 8 events correctly one has to submit 2**8 or 256 guesses.
What is the least number of entries one has to submit in order to guarantee correctly guessing 7 of the 8 events correctly and what is the strategy for choosing those guesses?
The simplest answer is 128 where you choose each combination of the first 7 events and then don't care about the eight event because you know you'll have 7 correct, but I believe the answer to be 16 but I can't figure out how to search for an answer. I'd also like to see the strategy for choosing the "n" number of guesses that guarantees 7 out of 8 correct.
kindest regards,
Tom
Sydney, Aus.
What is the least number of entries one has to submit in order to guarantee correctly guessing 7 of the 8 events correctly and what is the strategy for choosing those guesses?
The simplest answer is 128 where you choose each combination of the first 7 events and then don't care about the eight event because you know you'll have 7 correct, but I believe the answer to be 16 but I can't figure out how to search for an answer. I'd also like to see the strategy for choosing the "n" number of guesses that guarantees 7 out of 8 correct.
kindest regards,
Tom
Sydney, Aus.
February 2nd, 2011 at 1:55:32 AM
permalink
For the coin toss event there are 256 possible outcomes. If you guessed differently 256 times, only one guess would correctly predict the 8 outcomes in a row and 8 guesses would correctly predict exactly 7 outcomes. I think the correct solution should be 32 and the correct strategy to minimize the number of guesses you have to take would be to change the guess of several events at the same time, however I am not sure how. If you chose the first 7 correctly and the last one incorrectly, changing only the last guess would 'waste' a guess so changing more than 1 variable every time is necessary to minimize the number of combinations you chose. I hope that made sense.
February 2nd, 2011 at 5:35:35 AM
permalink
You are allowed to get 1 of 8 wrong. So, it's 256/8 = 32.
"When two people always agree one of them is unnecessary"
February 2nd, 2011 at 6:45:01 AM
permalink
There are a million ways you could divide up the events to get 6/8, but to get 7 correct the lowest I could come up with was 64. Do every combination for the first 5 flips, then treat the last 3 as a single event (HHH/TTT only)
February 2nd, 2011 at 8:39:03 AM
permalink
Nice question... Using simple graph theory & connectivity, I can prove you need at least 2^n / (n+1) guesses. So, you need at least 256/9 ~ 29 guesses to get at least 7 out of 8 right.
I'm not sure that weaselman's approach is going to work, because you can do 3 with only 2 guesses (his solution implying it takes 8/3 guesses). Maybe it will turn out to be that easy, but I'm going to run a program in matlab to be sure.
I'm not sure that weaselman's approach is going to work, because you can do 3 with only 2 guesses (his solution implying it takes 8/3 guesses). Maybe it will turn out to be that easy, but I'm going to run a program in matlab to be sure.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 9:01:38 AM
permalink
That was actually my first thought, and so I was going to post, but I couldn't prove it or even be sure.
My reasoning was putting it in binary with correct answer standing for 1. That way, there are 4 correct answers for 3 questions (111, 110, 101, 011) and generally n+1, so your probability of hitting is 2^n/(n+1); therefore it's impossible to do it with any fewer guesses than that. What I can't do is strictly formulate the strategy for doing so (a casual formulation would be to make all choices differ exactly by two bits) or prove it being always possible to hit with 2^n/(n+1).
My reasoning was putting it in binary with correct answer standing for 1. That way, there are 4 correct answers for 3 questions (111, 110, 101, 011) and generally n+1, so your probability of hitting is 2^n/(n+1); therefore it's impossible to do it with any fewer guesses than that. What I can't do is strictly formulate the strategy for doing so (a casual formulation would be to make all choices differ exactly by two bits) or prove it being always possible to hit with 2^n/(n+1).
Resist ANFO Boston PRISM Stormfront IRA Freedom CIA Obama
February 2nd, 2011 at 9:22:49 AM
permalink
I have been thinking about whether there is a set covering algorithm to find the general strategy, but I haven't found any nice upper bound yet. I am thinking of solving an optimization problem on the binary connectivity matrix, but that may be overkill. If anyone sees the answer intuitively (e.g. possibly weaselman), I will be impressed.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 10:00:33 AM
permalink
First thing first, are you positive it can always be solved with as few as 2^n/(n+1) [rounded up] picks? I can't say I'm certain, rather I suspect that more picks may be needed.
Experimenting, I can't seem to find a 6-pick solution for 5 answers. Any first pick eliminates 6 numbers, say entering 00000 and 11111 eliminates 6 numbers each. But any following pick faces the fact that all single-zero and single-one numbers are eliminated, so it can't cover more than 4. Should probably make a C check for all possible pick sets, but it's a bit boring.
Experimenting, I can't seem to find a 6-pick solution for 5 answers. Any first pick eliminates 6 numbers, say entering 00000 and 11111 eliminates 6 numbers each. But any following pick faces the fact that all single-zero and single-one numbers are eliminated, so it can't cover more than 4. Should probably make a C check for all possible pick sets, but it's a bit boring.
Resist ANFO Boston PRISM Stormfront IRA Freedom CIA Obama
February 2nd, 2011 at 10:44:36 AM
permalink
No, I'm really not sure that it can be solved in the min. 2^n/(n+1) is just a lower bound. It would be really neat if you could, but I'm not sure how you could generalize the strategy if this did work out
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 11:55:00 AM
permalink
I've got my program running. Already for 5 flips we have an interesting result. It takes 7 guesses (not 32/6 ~ 6) to guarantee you get 4 out of 5 right. If my program works right, you can't do better.
I'm using a free solver, which is taking forever even on n = 6. Maybe I will switch solvers if this doesn't finish soon.
EDIT: I've got a better solver going. I'll post 6,7 and 8 as they become available.
I'm using a free solver, which is taking forever even on n = 6. Maybe I will switch solvers if this doesn't finish soon.
EDIT: I've got a better solver going. I'll post 6,7 and 8 as they become available.
| n | Lower Bound | Optimal Strategy |
|---|---|---|
| 3 | 2 | 2 |
| 4 | 4 | 4 |
| 5 | 6 | 7 |
| 6 | 10 | 12 |
| 7 | 16 | 16 |
| 8 | 29 | 32 |
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 12:24:09 PM
permalink
What is the solution for n=5, by the way? I mean the set of 7 answers.
Resist ANFO Boston PRISM Stormfront IRA Freedom CIA Obama
February 2nd, 2011 at 12:34:40 PM
permalink
One solution for 5 picks (almost certainly not the only one), are the binary numbers corresponding to 3,5,7,8,16,25,30.
So:
00011
00101
00111
01000
10000
11001
11110
That looks like it works. Cool.
So:
00011
00101
00111
01000
10000
11001
11110
That looks like it works. Cool.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 12:44:35 PM
permalink
It turns out the answer for n=8 is indeed 32.
I'm not sure it's a simple to explain as weaselman's approach, because it doesn't explain why with n=6 the answer is 12 (and not something like 64 / 6 ~= 10 or 11).
An interesting problem for sure. I wonder if for these larger cases (n>=7) the answer is always 2^(n-3). But... my matrix is getting big, so I'm probably going to stop here.
I'm not sure it's a simple to explain as weaselman's approach, because it doesn't explain why with n=6 the answer is 12 (and not something like 64 / 6 ~= 10 or 11).
An interesting problem for sure. I wonder if for these larger cases (n>=7) the answer is always 2^(n-3). But... my matrix is getting big, so I'm probably going to stop here.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
February 2nd, 2011 at 12:54:33 PM
permalink
Quote: dwheatley00011
00101
00111
01000
10000
11001
11110
Huh. That goes against my intuition somewhat. I expected that the solution would be possible with any first pick and include inversions - much unlike this, where each pattern is unique and no pick is an inversion or a flip of another.
Resist ANFO Boston PRISM Stormfront IRA Freedom CIA Obama
February 2nd, 2011 at 1:59:55 PM
permalink
Fascinating!
February 2nd, 2011 at 5:30:25 PM
permalink
Wow, and thanks everyone for the replies and effort. I think I contacted the guys who run "Chance" at Dartmouth many years ago but I no longer have access to that email account. I'd be surprised if there wasn't already some long standing puzzle similar to this.
I can see applications for this "strategy" in football tipping competitions where you are allowed multiple entries.
For any "n" is there a way to devise the list of guesses without use of a computer program?
Tom
I can see applications for this "strategy" in football tipping competitions where you are allowed multiple entries.
For any "n" is there a way to devise the list of guesses without use of a computer program?
Tom
