Prisoners, Boxes and Pieces of Paper

“A Sunday school is a prison in which children do penance for the evil conscience of their parents.” H. L. Mencken There are n prisoners stuck in jail. Things are fairly quiet, so the prison guard gets bored and decides to play a game. The game is between the prison guard and the prisoners and consists of many rounds, one round per day. If the prisoners win a round, they all get freed. If the prison guard wins, then the prisoners stay in jail until the next day, when they play again. During each round of the game, the prison guard takes n pieces of paper and writes on them the names of the prisoners, one name per piece of paper. He then takes n identical black boxes and puts each piece of paper with a name on it into a separate box. He then shuffles the boxes and arranges them in a row on a long table in room A. During this time, in room B, the prisoners get together and decide on a strategy that they will follow. None of them know which box contains which name. After the boxes are set up, the prison guard decides on the order in which he will call the prisoners, one by one, into room A. He calls the first prisoner of his choice and asks him to open n/2 boxes (n is even). The prisoner opens n/2 boxes of his choice, one by one. If the prisoner’s name does not appear in any of the open boxes, then the prisoners lose this round, and all n of them go back to their cells until the next day. If, on the other hand, the prisoner manages to find his name, that prisoner goes to room C, where he is unable to communicate with any of the prisoners in room B. Then, the prison guard closes all of the open boxes and calls another prisoner from room B to room A and lets him open any n/2 boxes. If the second prisoner cannot find his name, the prisoners lose this round. Otherwise, the second prisoner is moved to room C, the guard closes all open boxes and calls another prisoner from room B to room A. This continues until all prisoners are in room C, at which point, the prisoners win, and everyone gets freed. Given n, find the probability that the prisoners will win one round of the game and the expected number of rounds the prisoners will need to play until they win. You may assume that the prisoners play according to an optimal strategy that they have agreed upon. Input The first line of input gives the number of cases, N. N test cases follow. Each one is an even number b (1 < n < 1001) on a line by itself. Output For each test case, output one line containing ‘Case #x:’ followed by the probability and the expected value. Your answers must be precise up to an absolute or relative error of 10−6. Sample Input 2 2 2

2/2 Sample Output Case #1: 0.50000000 2.00000000 Case #2: 0.50000000 2.00000000