wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Superbowl problem
        
(Message started by: BenVitale on Feb 3^rd, 2008, 4:24am)

Title: Superbowl problem
Post by BenVitale on Feb 3^rd, 2008, 4:24am

Here's a problem I sort of just invented, and it was inspired by the fact that I'm participating in a superbowl grid. You've probably heard of these: it's a game where you draw a 10 x 10 square. You then sell all 100 squares to the participants, and all the money goes into a pot. The pot is usually divided into 4 pots, one for each quarter of the football game. Then once the squares are formed, you randomly permute the numbers {0,1,2,...,9}and write them along the top, and then do anther random permuation and write them down the left side.

Then at the end of each quarter of the football game, you use the unit's digit for each teams score to perform a column and row lookup, using the random digits that were written down, and then whoever is at those coordinates wins that quarter's pot.

Now, this game is often administered through the internet, and the administrator takes the job of doing the two random permutations. In my case, the administrator also bought 5 squares, so it makes you wonder about the possibility of cheating. What's do stop him from randomizing, looking and saying to himself "my squares don't look very good", and then he quickly clicks on the excel macro to rerandomize, and then says to himself "that looks better", and then publishes the grid for all to see, and nobody else knows he actually cheated.

Even if the administrator is not buying squares, his 'friends' might be.

In fact, let me say that in the game I'm playing, the adminisrator' s 5 squares he bought all look pretty good, so it makes you wonder if this happened. Fortunately of the two squares I bought, even though one is bad, the other is quite good (7,4), so I'm probably okay, but another guy I know who bought 5 squares, got all 5 of them as bad squares.

Anyway, I was thinking about a possible way to administer the game in a way that guarantees cheating can't happen, but it involves some math. The basic premise of my idea, is that each participant should pick a random number from 1 to x, for some predetermined x. They would email their random number to the administrator. Afer all participants have done so, all these numbers would act as seeds into a randomizing function that produces the two desired permutations of {0,1,2,3,... ,9}. Then he not only publishes the board for all to see, but also publishes the list of all random seeds that all selected, so that everybody now knows everybody else's seeds. Also, the exact nature of the randomizing function would be known to all participants before they sign up to play.

It would be hard to cheat, because if the administrator picks his own permutations to improve his own squares, anybody can independently take the seed list and calculate/verify that the published board is correct. And if the adminstrator lies about the seed list,then whosever's seed is incorrect could pipe in and say that's not his seed. So any lie could be caught.

My question to you all is: What would be a good choice for a function to use the convert these seeds into the two desired permutations? It would also be desirable that the function could be chosen in a way that a subset of the participants could not collude to improve their collected odds of winning.

Here's some thoughts I've had on this so far:

You'd want any board arrangement to be equally as likely as any other board arrangement.

There are 10! ways to permute each set, so there are (10!)² ways to accomplish both permutations. (10!)² = 13168189440000. Call this number P

Maybe we could find some number Q, such that P*Q is very close to 10^x for some integer x. For example, if Q = 75940584281266233, then P*Q = 9999999999999999992 19179520000, which is very close to 10^30.

Assuming you have at least 15 participants, you could have each pick a number from 0 to 99. String all the seeds together to form a long number, and divide it by (10!)² and take the remainder, and call this remainder R. At this point, you could take this remainder, and use it to get your 20 desired digits for the game, by doing repeated division and taking of remainders. That is, divide by 10, getting quotient q, remainder r. r is your first digit. Now divide q by 9, getting quotient q2, and remainder r2. The r2th digit in {0,1,...r-1,r+1,r+2,.. .9} is your next digit. Divide r2 by 8, and take the remainder. Repeat this until your first 10 digits are found, and do the same thing again for the next 10 digits. Assuming that R was a random number from 0 to (10!)²-1, this guarantees two randomly permuted sets of digits.

A problem for this strategy is that the 16th, 17th,... participants numbers have no effect on R, which means the first 15 participants could collude to their advantage.

Also, I'm wondering if somebody could do some sort of analysis whereby by he looks at all the possible board arrangements that could result, given the one seed he himself picks. And then calculates which seed would maximize the chance that his numbers are good numbers. (Remember, in football, certain numbers, especially 0,7,3, and probably 4, come up more often than the other numbers, so there is indeed such a thing as 'good numbers'.) This would introduce an element of strategy into the game, which I don't want. I want it to be all luck.

In other words, I would like it so that no matter which seed person x chooses, the odds that person x's numbers will be 'good numbers' will be independent of which seed he picks.

Is there such a function that would meet my criteria? Mabye one that's not overly complicated for lay people who play the game, and aren't math wizzes, wouldn't have a hard time using to independently verify cheating hasn't happened, while at the same time can't be used in a strategic way to give an advantage? (I haven't mentioned yet that normally, the game is played on first come/first serve, which means the first person to sign up would be the first person to pick a random number, so this means I would hope that person x, know he's the xth person in the list, can't somehow pick a seed that gives himself an advantage over the other players. I want this to be a 0% skill, 100% luck game.)

Title: Re: Superbowl problem
Post by towr on Feb 3^rd, 2008, 9:09am

on 02/03/08 at 04:24:21, BenVitale wrote:

It would be hard to cheat, because if the administrator picks his own permutations to improve his own squares, anybody can independently take the seed list and calculate/verify that the published board is correct. And if the adminstrator lies about the seed list,then whosever's seed is incorrect could pipe in and say that's not his seed. So any lie could be caught.

My question to you all is: What would be a good choice for a function to use the convert these seeds into the two desired permutations? It would also be desirable that the function could be chosen in a way that a subset of the participants could not collude to improve their collected odds of winning.

I think it would be very hard to achieve this. Because the administrator can always pick his seed last, and choose the seed that gives him the best result.

Perhaps you could pick an external seed, like next weeks lottery numbers. It's public and unpredictable; if the pseudo-random number generator is fixed, everyone will know the permutation.

Title: Re: Superbowl problem
Post by Eigenray on Feb 3^rd, 2008, 10:24am

You could have all the participants publish a (salted) hash of their seed (or use any sort of [link=http://en.wikipedia.org/wiki/Commitment_scheme]commitment scheme[/link]). This way the administrator can't pick his seed based on the others. Once they're all in, everybody reveals their seed (which is checked against the hash), and all the seeds are added mod 10!².

Title: Re: Superbowl problem
Post by Grimbal on Feb 3^rd, 2008, 2:57pm

I thought everybody could publish a permutation encrypted with a public key. The permutation should be padded with random data to defeat brute-force search. After everybody has done so, all the private keys are revealed. The permutation used is the combination of participant's permutations in an order decided in advance.

If at least one participant provides a true random permutation then the final permutation is random.

Not very different from what Eigenray proposes.

Title: Re: Superbowl problem
Post by BenVitale on Feb 3^rd, 2008, 11:36pm

Thank you, guys.

Wow, while that avoids most of the math of my problem, your solution seems excellent. I never thought of this. It also eliminates the need for any seeds to be selected by anybody. You could just use thelottery results. Then again, I think the Texas lottery, if I remember correctly, consists of 6 numbers from 1 to 60, so with 60*59*58*57* 56*55 combinations, it leaves out a lot of possible board arrangements, so I guess we do need more inputs that just one lottery. Maybe a few lotteries.

However, in the superbowl grid I participated in, they wanted to give people time to decide whether to enter, so they didn't close off the board until less than one week before game day, so that doesn't leave much time for enough public lotteries to draw on. Maybe nationwide it does though, since many states have lotteries.

Do I just agree on a Random number generator and use the first lottery numbers for the seed. first number, second, sum of the digits etc.?

Or just use the square root, cube root etc of the first none square or prime if it exists of the lottery number.?

I could also play in suspense and use the yards gained in the first play as the seed. This would not work in a bar since 99.9% of the patrons have no idea what a random number generator is. I like the suspense though with a deck of cards 1-10 and shuffled.

I bought a grid for $100 two years ago and won the first quarter prize money of 1200. There was free food and drink during the game. Me, I would prefer the 4th quarter winner takes the 10 Grand buy your own drinks.