Puzzle?

[quantopian]

There are 30 strings and 2 parallel rows of 30 holes. Each string goes from one hole in 1st row to 2nd row. There cannot be more than one string in a hole. Find the total no. of expected crossovers.

 

[nfernand]

Let E(n,m) denote the expected number of crosses when there are n holes in each row and m strings connecting the holes. We will calculate E(30,30) by finding a recursive formula relating E(n,n) to E(n-1,n-1).

Condition on which 2nd-row hole the left-most 1st-row hole connects to. (label these 1,...,30). If it is hole 1, then the remaining 29 strings will connect the remaining 29 holes, and none of these strings will cross the first string. So in that case, we just have E(29,29).

If it is hole 2, then we have E(29,29) again, PLUS the fact that there will be ONE string (the string connected to hole 1, in the bottom row) that crosses the first string (connecting top row hole 1 with bottom row hole 2). So we have E(29,29) +1.

This pattern continues all the way up to E(29,29) + 29 (when hole 1 of top row is connected to hole 30 of bottom row, all remaining 29 strings must cross the string touching hole 1 of the top row).

So we are left with:

E(n,n) = SUM(from i=0 to i=n-1) { (1/30) * (E(29,29) + i) }
= E(n-1,n-1) + (0 + 1 + 2 + 3 + ... + n-1) / n
= E(n-1,n-1) + n-1(n/2) / n
= E(n-1,n-1) + (n-1)/2

Since we know E(1,1) to be 0, this gives us E(2,2) = 0 + 1/2, E(3,3) = 0 + 1/2 + 2/2 = 3/2,

and so on, until

E(n,n) = (1/2) * SUM( i = 0 to i = n-1) i
= (1/2) * (n-1)*n/2
= n*(n-1)/4.

Please correct me if my arithmetic is off, but I'm fairly sure that this is the right approach.

 

[quantopian]

Let E(n,m) denote the expected number of crosses when there are n holes in each row and m strings connecting the holes. We will calculate E(30,30) by finding a recursive formula relating E(n,n) to E(n-1,n-1).

Condition on which 2nd-row hole the left-most 1st-row hole connects to. (label these 1,...,30). If it is hole 1, then the remaining 29 strings will connect the remaining 29 holes, and none of these strings will cross the first string. So in that case, we just have E(29,29).

If it is hole 2, then we have E(29,29) again, PLUS the fact that there will be ONE string (the string connected to hole 1, in the bottom row) that crosses the first string (connecting top row hole 1 with bottom row hole 2). So we have E(29,29) +1.

This pattern continues all the way up to E(29,29) + 29 (when hole 1 of top row is connected to hole 30 of bottom row, all remaining 29 strings must cross the string touching hole 1 of the top row).

So we are left with:

E(n,n) = SUM(from i=0 to i=n-1) { (1/30) * (E(29,29) + i) }
= E(n-1,n-1) + (0 + 1 + 2 + 3 + ... + n-1) / n
= E(n-1,n-1) + n-1(n/2) / n
= E(n-1,n-1) + (n-1)/2

Since we know E(1,1) to be 0, this gives us E(2,2) = 0 + 1/2, E(3,3) = 0 + 1/2 + 2/2 = 3/2,

and so on, until

E(n,n) = (1/2) * SUM( i = 0 to i = n-1) i
= (1/2) * (n-1)*n/2
= n*(n-1)/4.

Please correct me if my arithmetic is off, but I'm fairly sure that this is the right approach.

For N=2 (i.e 2 holes and 2 strings), the answer should be 1 crossover, but acc. to your formula its (1/2)

 

[throll]

for n=2 there can be either one or zero crossover, so yes the expectation is 1/2

 

[quantopian]

for n=2 there can be either one or zero crossover, so yes the expectation is 1/2

Hi Throll,

We have to find the total number of crossovers possible, not the expectation.

 

[throll]

Find the total no. of expected crossovers.

thought the above meant expectation..

 

[quantopian]

thought the above meant expectation..

Sorry, if that has confused anyone, "expected" here means the "possible" no. of crossovers

 

[throll]

i might be wrong but in this case the brainteaser needs another rule to lead to one and only one setting so we can count the number of crossovers, otherwise we have many possibilities of connecting the holes in both rows, this means randomness and hence we can only speak of expectation

 

[aaronhotchner]

Sorry, if that has confused anyone, "expected" here means the "possible" no. of crossovers

Then it's not even a probability question anymore. It's a discrete math question. And I'm not entirely sure why it's a "puzzle" anymore since the answer to maximize the number of crosses is to put the strings in holes 1/30, 2/29, 3/28, etc., which is true for any N.