Sleepwalking students on a 9x9 checkerboard [duplicate]

$\begingroup$

Each square of a 9x9 checkerboard is initially slept on by one of 81 students. At noon, each student will wake up and randomly sleepwalk to a valid adjacent square horizontally or vertically (but not diagonally). What is the probability that two or more students end up on the same square?

$\endgroup$ 2

1 Answer

$\begingroup$

The probability is 1. It's a checkerboard, so imagine it colored with white and black tiles. Initially, there are 40 students on white tiles and 41 on black tiles (or the other way around, doesn't matter). Each student on a black tile will sleepwalk to a white tile (because they're not allowed to walk diagonally). There are 41 such students and only 40 white tiles, so by the Pigeonhole principle there must be at least one tile with two or more students.

$\endgroup$