Price is Right Race Game - Page 2

Mr. P-1 · 2013-03-26, 01:37

Quote:

Originally Posted by c10ck3r

I mean I've found a method that will use somewhere between 4-10 attempts, dependent on the answer.
This algorithm, however, cannot give the correct answer in 1 attempt (by reason of the methodology).

Of course it can. Whatever you try on your first attempt has a non-zero chance of being the correct answer.

science_man_88 · 2013-03-26, 01:54

Quote:

Originally Posted by Mr. P-1

c10ck3r is specifying the problem he wants us to solve, which is different from the one faced by the contestant.

I was just pointing out a technicality about winning, also I know brute force can solve it in 9 or less ( less than his maximum 10) using brute force

proof:

600,1299,2399,3790 - lets say 0 are correct.
1299,600,2399,3790 - 1 switched, first 0 guaranteed
2399,600,1299,3790 - 2 switched, first 0 guaranteed
3790,600,1299,2399 - 3 switched, first 1 guaranteed
3790,1299,600,2399 - 4 switched, first 1 guaranteed
3790,2399,600,1299 - 5 switched, first 2 guaranteed
3790,2399,1299,600 - 6 switched, first 4 guaranteed

because each of the four positions a few logic things should be thrown in and it can be sped up ( for example if 1299 wasn't correct in the first one the fourth switch isn't needed cutting it down to 5 switches plus an initial layout for 6 steps , the ones you work on have to eventually pass through the correct one so it may be even less)

Mr. P-1 · 2013-03-26, 10:39

Quote:

Originally Posted by Mr. P-1

By the pigeon-hole principle, it is impossible for you to know for certain the correct arrangement for certain after i plays, unless (k-1)ⁱ >= k!-i. For k=4. the smallest i satisfying this inequality is 3, and your best hope is for an algorithm which allows you to get the right answer on the 4th play. This argument does not demonstrate that such an algorithm exists, only that no algorithm can solve the problem in fewer tries.

Let's chase this. Let a(k) be maximum number of turns the best possible algorithm will take if there are k prizes. From the above, $a(k) \ge i+1$ where i is the least integer satisfying $(k-1)^i \ge k!-i$ . Rearranging as $i=\lceil{ln(k!-i) \over ln(k-1)}\rceil \ge \lfloor {ln(k!) \over ln(k-1)} \rfloor$ for sufficiently large k. ("Sufficiently large" is very quickly reached because k! dominates -i for even modest values of k. Usually, i will be one greater than the minimum implied by the inequality.)

Therefore $a(k) \ge i+1 \ge \lfloor {ln(k!) \over ln(k-1)} \rfloor +1 = \lceil {ln(k!) \over ln(k-1)} \rceil$ , for sufficiently large k.

Let's test small k by hand

$\hspace{20 mm} k \hspace{20 mm} a(k) \hspace{20 mm} i+1 \hspace{20 mm} \lceil {ln(k!) \over ln(k-1)} \rceil$

Code:

1    1     1*   Undefined
2    2     2    Undefined
3    3     3        3
4    ?     4        3
5    ?     5        4
6    ?     6        5

*Defining 0⁰ as 1.

Thus we have two lower bounds for a(k): An open form one which works for all k: $a(k) \ge i+1$ where i is the least integer satisfying $(k-1)^i \ge k!-i$ and the closed form derived from it, $a(i) \ge \lceil {ln(k!) \over ln(k-1)} \rceil$ , which is clearly going to work for all $k\ge3$ .

We can also find an upper bound for a(k). Consider the following "dumb" algorithm. Choose the first permutation at random. Then make a list of all permutations compatible with the answer you are given, and test them, one at a time, ignoring any new information you receive. This process will clearly find the correct solution in no more tries than the maximum possible number of permutations consistent with any first answer.

How many is that? Answer: It's the highest figure on the kth row of this table, which is always the first or second value in the row. Moreover, the second value is always one less than, or one greater than, the first depending upon whether k is even or odd. (This can be proven using the formulas given.) In other words, $a(k) \le D(k,0)+{1-(-1)^k \over 2}+1 = k! \sum_{i=0}^k{(-1)^i \over i!} + {1-(-1)^k \over 2}+1$

Can anyone improve on these bounds?

Mr. P-1 · 2013-03-26, 10:58

[QUOTE=science_man_88;334969600,1299,2399,3790 - lets say 0 are correct.
1299,600,2399,3790 - 1 switched, first 0 guaranteed
2399,600,1299,3790 - 2 switched, first 0 guaranteed
3790,600,1299,2399 - 3 switched, first 1 guaranteed
3790,1299,600,2399 - 4 switched, first 1 guaranteed
3790,2399,600,1299 - 5 switched, first 2 guaranteed
3790,2399,1299,600 - 6 switched, first 4 guaranteed[/QUOTE]

I have no idea what any of this means.

Brute force can certainly solve it in ten. After your first choice there are nine possible permutations where there are no matches (derangements), eight possible with a single match, and six with two matches. Just try each of the permutations for a total of ten tries in the worst case.

ckdo · 2013-03-26, 11:29

Well, I must be missing something.

To me this looks like a dumbed down variant of Master Mind (4 slots, 4 colours, no duplicates).

Why on earth would this need more than the 5 guesses required for the original game?

science_man_88 · 2013-03-26, 11:54

Quote:

Originally Posted by Mr. P-1

I have no idea what any of this means.

in the video these are the prices involved and how I'd rearrange them to be able to get the correct answer in 6 guesses. basically all this is, is basically brute force with the stipulations that you don't change them once they are found, and you don't place them in the place they were to start ( the 0000 state in this estimate).

4 rounds to guess the first one, the next one only has 2 choices left one of which was there at the start ( at least in this example) so it takes 1 to place that one, and then it takes 1 to place the last 2.

LaurV · 2013-03-27, 07:08

Quote:

Originally Posted by ckdo

Well, I must be missing something.

To me this looks like a dumbed down variant of Master Mind (4 slots, 4 colours, no duplicates).

Why on earth would this need more than the 5 guesses required for the original game?

6 guesses. We use to play mentally, during classes, in high school and later, with numbers of 4 digits, from 1023 to 9876, no repetition of the digit, first digit can't be 0. For this you need 6 guesses in the worst case. Or are you talking about the game for kids, with colored pegs? The one I know had only 6 colors and it was much easier.

Also, you have to think about the fact that the info you get with the pegs game (how many right, how many in the right position, how many right but not in the right position, etc) you don't get it here, therefore it may require a longer guessing process. I don't know the show you are talking about, this information is what I understand by solely reading the current topic.

Mr. P-1 · 2013-03-27, 13:53

Quote:

Originally Posted by science_man_88

in the video these are the prices involved.

The prices are irrelevant. The problem is the same whatever the prices (so long as they're all different.

The first thing any mathematician does when considering a new problem is throw away everthing which isn't relevent, reducing it to its bare essentials. If you want to communicate with mathematicians, you will need to learn to do the same thing.

science_man_88 · 2013-03-27, 14:00

Quote:

Originally Posted by Mr. P-1

The prices are irrelevant. The problem is the same whatever the prices (so long as they're all different.

The first thing any mathematician does when considering a new problem is throw away everthing which isn't relevent, reducing it to its bare essentials. If you want to communicate with mathematicians, you will need to learn to do the same thing.

I get that I was just using them as placeholders to show a solve in as little as possible because I knew even a nearly brute force algorithm shouldn't take more than 9.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Engine-assisted game vs Stockfish, move 36 discussion. Drawn game?	MooMoo2	Other Chess Games	10	2017-04-29 17:39
Prime95 potential race on WORKER_THREADS_ACTIVE and WORKER_THREADS_STOPPING	Explorer09	Software	2	2017-03-09 08:17
The human race, magnifier of the improbable	jasong	jasong	0	2015-08-24 06:11
Boat race	davieddy	Puzzles	13	2011-11-03 15:49
Horse Race	Gary Edstrom	Puzzles	10	2003-08-31 14:25

2013-03-26, 10:58	#15
Mr. P-1 Jun 2003 7×167 Posts	[QUOTE=science_man_88;334969600,1299,2399,3790 - lets say 0 are correct. 1299,600,2399,3790 - 1 switched, first 0 guaranteed 2399,600,1299,3790 - 2 switched, first 0 guaranteed 3790,600,1299,2399 - 3 switched, first 1 guaranteed 3790,1299,600,2399 - 4 switched, first 1 guaranteed 3790,2399,600,1299 - 5 switched, first 2 guaranteed 3790,2399,1299,600 - 6 switched, first 4 guaranteed[/QUOTE] I have no idea what any of this means. Brute force can certainly solve it in ten. After your first choice there are nine possible permutations where there are no matches (derangements), eight possible with a single match, and six with two matches. Just try each of the permutations for a total of ten tries in the worst case.

2013-03-26, 11:29	#16
ckdo Dec 2007 Cleves, Germany 1000010010₂ Posts	Well, I must be missing something. To me this looks like a dumbed down variant of Master Mind (4 slots, 4 colours, no duplicates). Why on earth would this need more than the 5 guesses required for the original game?