PR 4 # 22

[Wacky]

A drawer contains an odd number of plain brown socks and an even number of plain black socks. What is the least number of brown and black socks such that the probability of obtaining two brown socks is 1/2 when two socks are chosen at random from the complete collection?

[wblipp]

1 if we permit zero as the even number of black socks and we pick the brown socks with replacement.

3 if we permit zero as the even number of black socks but require distinct selections.

9 (7 & 2) if we require a positive number of black socks

[Wacky]

The first two answers cannot be correct. If there are no black socks, then the probability of getting a brown sock is 1. In order to have a lesser probability (the puzzle calls for 1/2), there must be some chance of getting a black sock.

I also believe that your final answer is incorrect.

[wblipp]

Originally Posted by Wacky

The first two answers cannot be correct. If there are no black socks, then the probability of getting a brown sock is 1. In order to have a lesser probability (the puzzle calls for 1/2), there must be some chance of getting a black sock.

I also believe that your final answer is incorrect.

I interpreted "1/2" to mean "At least 1/2", and would argue that 1>1/2, so the answers are valid. If "1/2" does not mean "at least 1/2", then the only other reasonable interpretation is "exactly 1/2". That was probably the original intention - it makes a more interesting puzzle. Then the answer would be

15 brown socks and 6 black socks

[Wacky]

I cannot say that I would agree with your "at least" interpretation.

Now, here is a "followup" question that I will add.

Assuming that the drawer contains the collection of socks specified, what is the minimum number of socks that must be chosen, at random, to assure that, with certainty, you will have chosen at least one pair?

[drew]

Assume B is 'brown' and T is 'total':

B/T * (B-1)/(T-1) = 1/2

let's go through the integers:

1*2 = 2
2*3 = 6
3*4 = 12

6/12 is 1/2, but this requires 3 brown and 4 total socks, which requires 1 black sock...an odd number. Keep going (I went to a spreadsheet at this point)

The solution is 15 brown and 21 total socks, which results in 6 black socks.

Now, here is a "followup" question that I will add.

Assuming that the drawer contains the collection of socks specified, what is the minimum number of socks that must be chosen, at random, to assure that, with certainty, you will have chosen at least one pair?

This may be interpreted a number of different ways. If you mean a pair of socks, and they need not match, then the answer is trivial (2 socks). If you mean any pair of matching socks, the answer is 3. If you mean a matching pair of brown socks, then the answer is 8. Nothing prevents the worst case scnario in which you select every black sock before finding a second brown one.

Drew

[wblipp]

There are infinite number of larger solutions that also give probability of exactly one half, but they grow larger by a factor of almost 34 asymptotically. The fourth solution is 568345 brown socks and 235416 black socks. The 10th is 873430010034205 black socks and 361786555939836 brown socks.

[drew]

Originally Posted by wblipp

There are infinite number of larger solutions that also give probability of exactly one half, but they grow larger by a factor of almost 34 asymptotically.

I'd be interested to know how you derived this.

Drew

[wblipp]

Originally Posted by drew

I'd be interested to know how you derived this.Drew

Let the number of brown socks be 2x+1 and the number of black socks be 2y. You get a quadratic equation in x and y. Dario Alpern's Quadratic Integer Equation Solver at

http://www.alpertron.com.ar/QUAD.HTM

gives all the solutions as an iterative process. Express that iterative process in matrix form - if the column vector x is a solution, then so is Ax+B.

The eigenvalues of A are a small number and 33.9. Except for the exceptional case where the vector B and the initial solution x are both eigenvectors corresponding to the smaller eigenvalue, the iteration will eventually grow at the rate of the larger eigenvalue.

[drew]

Originally Posted by wblipp

Let the number of brown socks be 2x+1 and the number of black socks be 2y. You get a quadratic equation in x and y. Dario Alpern's Quadratic Integer Equation Solver at

http://www.alpertron.com.ar/QUAD.HTM

gives all the solutions as an iterative process. Express that iterative process in matrix form - if the column vector x is a solution, then so is Ax+B.

The eigenvalues of A are a small number and 33.9. Except for the exceptional case where the vector B and the initial solution x are both eigenvectors corresponding to the smaller eigenvalue, the iteration will eventually grow at the rate of the larger eigenvalue.

Very nicely done!

[drew]

Originally Posted by wblipp

Let the number of brown socks be 2x+1 and the number of black socks be 2y. You get a quadratic equation in x and y. Dario Alpern's Quadratic Integer Equation Solver at

http://www.alpertron.com.ar/QUAD.HTM

gives all the solutions as an iterative process. Express that iterative process in matrix form - if the column vector x is a solution, then so is Ax+B.

The eigenvalues of A are a small number and 33.9. Except for the exceptional case where the vector B and the initial solution x are both eigenvectors corresponding to the smaller eigenvalue, the iteration will eventually grow at the rate of the larger eigenvalue.

Hey Wblipp,

Is there a mathematical method to determine the stability of an eigenvector? In other words, it's clear in this case that the series converges to the eigenvector associated with the eigenvalue 33.97056..., but not the other eigenvector, making the 'small number' an unstable vector (we see this same behavior with the middle magnitude of the 3 principal inertial axes of a rigid body in rotation). Without actually stepping through the series, how would one determine the stability of an eigenvector?

Thanks,
Drew