|
Let adjacent payphones have the distance 1. We now look at the situation with p payphones and the first person choosing the payphone at the left end. Then let b(p,k) be the number of people who choose a payphone with distance k and let d(p,k) be the number of different sets of two adjacent payphones which both have at one time the distance k.
1) Calculation of b(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
For p < k + 1: 0.
For p = k + 1: 1.
For k + 1 < p < 1 + 2k: 0.
For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): 2^m.
For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
For 1 + 2^m*(2k+2) < p <= 1 + 2^m*(4k-2): 0.
For 1 + 2^m*(4k-2) < p < 1 + 2^(m+1)*2k: p - 1 - 2^m*(4k-2).
2) Calculation of b(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
For p = 1: 0.
For p = 2 or p = 3: 1.
For 1 + 2^m*3 <= p <= 1 + 2^m*4: 2^(m+1).
For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^(m+1).
3) Calculation of d(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
For p < 1 + 2k: 0.
For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): p - 1 - 2^m*2k.
For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
For 1 + 2^m*(2k+2) < p < 1 + 2^(m+1)*2k: 0.
4) Calculation of d(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
For p < 4: 0.
For 1 + 2^m*3 <= p <= 1 + 2^m*4: 1 + 2^m*4 - p.
For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^m*4.
Now you can give a formula for a(n):
a(n) = Sum_{i=1..n} Product_{j=1..n-1} 2^(d(i,j) + d(n+1-i,j)) * (d(i,j) + d(n+1-i,j))! * (b(i,j) + b(n+1-i,j) - d(i,j) - d(n+1-i,j))!. (End)
| 