Wednesday, October 22, 2014

A Diophantine problem

Here was this week's challenge on the Sunday Edition puzzle from NPR:


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?

After giving this week’s puzzle a little thought, I realized that it was a problem involving the distribution of pairs of objects.

It is clear that n(n-1)/2 pairs can be selected from n objects.

Therefore, if there are x blue-eyed students in a class of y students,
then the probability of picking at random a pair of blue-eyed students
is

p(x,y) = (x(x-1)/2) / (y(y-1)/2) = (x(x-1))/(y(y-1))

And the puzzle problem reduces to finding the integer solutions to the equation
        
p(x,y) = (x(x-1))/(y(y-1)) = 1/2

Such an equation - requiring integer solutions - is called a Diophantine equation. It was surprisingly easy to solve this in Mathematica. I’ve attached a couple of screen shots.
The surprisingly simple form of the general solutions to the puzzle problem.
List of the first ten solutions