A friend of yours, Eithen Quinn, is fascinated by the following problem: placing m rooks on an nxn chessboard, so that they are in peaceful harmony (i.e. no two threaten each other). Each rook is a chess piece, and two rooks threaten each other if and only if they are in the same row or column. You remind your friend that this is so simple that a baby can accomplish the task. You forget however that babies cannot understand instructions, so when you give the m rooks to your baby niece, she simply puts them on random places on the chessboard. She however, never puts two rooks at the same place on the board. (a) Assuming your niece picks the places uniformly at random, what is the chance that she places the (i+1)st rook such that it doesn't threaten any of the first i rooks, given that the first i rooks don't threaten each other? (b) What is the chance that your niece actually accomplishes the task and does not prove you wrong? (c) Now imagine that the rooks can be stacked on top of each other, then what would be the probability that your nieces placements result in peace? Assume that two rooks threaten each other if they are in the same row or column. Also two pieces stacked on top of each other are obviously in the same row and column, therefore they threaten each other. (d) Explain the relationship between your answer to the previous part and the birthday paradox. In particular if we assume that 23 people have a 50% chance of having a repeated birthday (in a 365-day calendar), what is the probability that your niece places 23 stackable pieces in a peaceful position on a 365 x 365 board? A friend of yours, Eithen Quinn, is fascinated by the following problem: placing m rooks on an nxn chessboard, so that they are in peaceful harmony (i.e. no two threaten each other). Each rook is a chess piece, and two rooks threaten each other if and only if they are in the same row or column. You remind your friend that this is so simple that a baby can accomplish the task. You forget however that babies cannot understand instructions, so when you give the m rooks to your baby niece, she simply puts them on random places on the chessboard. She however, never puts two rooks at the same place on the board. (a) Assuming your niece picks the places uniformly at random, what is the chance that she places the (i+1)st rook such that it doesn't threaten any of the first i rooks, given that the first i rooks don't threaten each other? (b) What is the chance that your niece actually accomplishes the task and does not prove you wrong? (c) Now imagine that the rooks can be stacked on top of each other, then what would be the probability that your nieces placements result in peace? Assume that two rooks threaten each other if they are in the same row or column. Also two pieces stacked on top of each other are obviously in the same row and column, therefore they threaten each other. (d) Explain the relationship between your answer to the previous part and the birthday paradox. In particular if we assume that 23 people have a 50% chance of having a repeated birthday (in a 365-day calendar), what is the probability that your niece places 23 stackable pieces in a peaceful position on a 365 x 365 board