Socks in a box

Stump your fellow simians.
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Socks in a box

Post by DanishDynamite »

A box contains a number of socks, the number not exceeding 1993. Some socks are Red, some are Blue. The probability of randomly picking two socks of the same color is known to be 1/2.

What is the maximum number of Red socks that the box can contain?
Beleth
Posts: 2868
Joined: Tue Jun 08, 2004 8:55 pm
Location: That Good Night

Post by Beleth »

Say there are R red socks and B blue socks.

The odds of first picking a red sock is R / R+B,
and likewise, the odds of the first sock being blue is B / R+B.

The odds of the first two socks being red is (R/(R+B)) ((R-1)/(R+B-1))
and (B/(R+B)) ((B-1)/(R+B-1)) for the two socks being blue.

Since they are mutually exclusive, we can just add them and get a probablility of 0.5.

((R/(R+B)) ((R-1)/(R+B-1))) + ((B/(R+B)) ((B-1)/(R+B-1))) = 0.5
Manipulating and dropping the obvious parentheses for clarity:

(R/R+B)(R-1) + (B/R+B)(B-1) = 0.5(R+B-1)
R(R-1) + B(B-1) = 0.5 (R+B-1)(R+B)
2(R^2 - R + B^2 - B) = R^2 + BR - R + BR + B^2 - B
2R^2 - 2R + 2B^2 - 2B = R^2 + 2BR + B^2 - R - B
R^2 - R + B^2 -B = 2BR
R^2 - 2BR + B^2 - R - B = 0

Help Me Mister Diophant!
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

Beleth's equation can be rewritten:

(R - B) (R - B) = R + B

This says that the difference in numbers between the colours, squared, is the total number of socks, so the total number must be a square, and the largest square less than 1993 is 1936.

The square root of 1936 is 44, so there must be (1936 + 44) / 2 = 990 socks of one colour and (1936 - 44) / 2 = 946 of the other.

So the maximum number of red socks is 990.
Cecil
Posts: 131
Joined: Thu Jun 10, 2004 9:14 pm
Location: Vancouver

Post by Cecil »

Beleth wrote:R^2 - 2BR + B^2 - R - B = 0
Taking this one step farther...

R^2 - 2BR + B^2 = R + B
R-B = sqrt(R+B)

Since the difference between red and blue socks is an integer, the total number of socks must be a perfect square. The largest square less that 1993 is 44^2 = 1936.

R-B = 44 and R+B = 1936, so R=990 and B=946.

I believe that an equal number of socks of each colour doesn't work because once you have withdrawn a sock (say), you are now more less likely to draw a matching sock, so the odds are slightly less that 50%.

That's gotta be a damn big box of sox though. ;)

EDIT: Really, ceptimus's solution wasn't there when I wrote this post. Honest! :P
DanishDynamite
Posts: 2608
Joined: Mon Jun 07, 2004 4:58 pm
Location: Copenhagen

Post by DanishDynamite »

Well done, folks.