Sunday, October 19, 2014

Probability puzzle

This has nothing to do with poker directly, but this week's Sunday Puzzle on NPR is an interesting exercise of your probability-thinking muscles.

Next week's challenge: The following challenge is based on a puzzle from a Martin Gardner book, that may not be well-known. Out of a regular grade school classroom, two students are chosen at random. Both happen to have blue eyes. If the odds are exactly 50-50 that two randomly chosen students in the class will have blue eyes: How many students are in the class?
I got the answer, but it was really difficult. I ended up having to set up a spreadsheet to automatically calculate the number of ways to select two children from a classroom of n students. This allowed me to play with both the number of students and the number of those that have blue eyes, until I found the combination that worked. 

Maybe there's a simpler, more intuitive way of getting at the answer, instead of using brute force the way I did--but if so, it escaped me. I predict that they will have very, very few correct answers submitted. 

12 comments:

Memphis MOJO said...

This is just a guess: .7 times .7 is .49, so I'm guessing that 70% (and a small fraction) of the class has blue eyes. Hope you'll post the answer after everyone has a chance to contribute.

Anonymous said...

Well, if we have n students of which k have blue eyes, the chance of two of them picked at random both having blue eyes is just k/n times (k-1)/(n-1). You then end up with a Diophantine equation in n and k, which you pretty much do have to brute-force. (Luckily it takes around 3 lines of code to produce the answer)

Rakewell said...

That is correct, though it's a completely different way of thinking about the problem than I used. If I'm right about my answer, it's 71.4% of the class that is blue-eyed.

If I forget to post the answer by Thursday afternoon, do another comment to remind me.

Mr Subliminal said...

I made a mistake in the formula for the quadratic in my previous comment - the denominator should be 4, not 2.

Also the small class size (4) irks me, seeing as he mentions a "regular grade school classroom".

So once again with Excel I set up columns n, n-1, n*(n-1) and sqrt(n*(n-1)) and found that for n = 21 we get an integer value for sqrt(n*(n-1)), as we do for n = 120. 21 is more like a regular classroom though.

So for a class of 21, with 15 blue-eyed kids, we get Grump's 71.4%. Meanwhile, 4 and 120 satisfy everything but the regular classroom size criterion.

Mr Subliminal said...

(This was my first comment which apparently got swallowed by Blogger)

I thought we were asked how many students are in the class.

I get a class of 4 students, 3 of whom have blue eyes.

If we let n = total number of students, and b = total number of students with blue eyes, then by definition

C(b,2) / C(n,2) = 1/2

or

2b^2 - 2*b - X = 0, where X = n*(n-1)

Solving for the quadratic, we get b = (2 ± sqrt(4 + 8*X)) / 2

Because it is stated that "the odds are exactly 50-50", sqrt(4 + 8*X) must be an integer. Using an Excel spreadsheet, with integer X starting from 6, we produce a second column of sqrt(4 + 8*X), looking for integer values only where X can be made up of a n*(n-1) combination.

The first value is 10 for X = 12, and 4*3 fits the bill. n is therefore 4 and b is 3.

I didn't find the problem difficult and spent about 10 minutes on it. I therefore am wondering what I may have missed.

Rakewell said...

The problem with that answer, I think, is that 4 students does not constitute the ordinary classroom that the problem specifies.

I see your second attempt at an answer, and it's the same thing I arrived at, but I'm not publishing it until after the deadline for submitting answers, which is Thursday noon.

Mr Subliminal said...

(To be published on Thursday)

Another typo, sqrt(n*(n-1)) should be sqrt(4 + 8*(n*(n-1))).

nottom said...

The hint from Memphis MOJO is pretty much the key to getting this pretty quickly as it allows you to put in a reasonable guess for the number of blue-eyed kids in a given classroom size which simplifies the problem immensely.

Unknown said...

probability that both have blue eyes = C(n,2)/C(m,2)
where n = number of students with blue eyes and m = number of students in class

So n(n-1) / m(m-1) = 1/2 or 2n(n-1) = m(m-1)

A simple way to get one of the solutions is to assume n = m-1 and 2(n-1) = m. this gives us the solution m=4,n=3

The more general way to solve is to continue what Mr Subliminal suggested and that is to generate the value of b in terms of n and restrict b to be an integer.

The first four solutions for this are (3,4), (15,21), (85,120) and (493,697). The fraction of blue students : 0.75, 0.7143, 0.7083 and 0.7073. As we can see the fraction indeed moves towards 0.7 (which would be the case at infinity)

Anonymous said...

The answer is easily brute-forced, and you don't need code to do it. Just make an Excel table.

I found three solutions between (0,0) and (495,670).

Anonymous said...

Interestingly, I just missed the fourth solution with my range of (495,670) and I believe there are more solutions up to n = 50,000 for a total of 6.

At large n, Excel has a problem discriminating between real answers and some pairs which just happen to be really, really close. For example, 30,591 blue-eyed people in a "class" of 43,262 gives a probability of 49.9999999% - but not 50%.

The only way I've been able to check that the answers are exact is to factor the numbers, e.g., 9*11*13*13 in a class of 9*11*239. I suspect coding the solution will also yield superior results to my Excel brute force method should you ever need to pick two blue-eyed people from a stadium.

Memphis MOJO said...

I hope it's okay to go ahead and post what we think the answer is? The class has 21 students and 15 have blue eyes. (15/21 times 14/20 = .50)