This problem is calling for induction. Verifying the base cases is easy, and we leave that to the reader.

Consider an sieve , and let be some removed cell. The idea is to remove the row and column of , and we will be left with a new sieve, and a partition of it with sticks. Note that some sticks will be unaffected, some will lose one square, and the rest will completely disappear. For the induction to work, we want at least sticks to completely disappear. However, this is not immediately clear that there exists some removed cell with this property. The idea is to pick randomly.

For any given stick, there is exactly one removed square, that would remove the stick if its row and column was deleted. Thus, for any given stick, the probability it gets removed is , so the expected number of removed sticks is , where is the number of sticks. Now, if , there exists a removed cell with the desired property of killing two sticks when its row and column are deleted.

Now, all that remains to check is that , or . However, note that the maximum length of a stick is , so the total number of sticks is at least . Equality can hold only if all the sticks have length , which one can easily see is not possible. Thus , so by picking a removed cell randomly, and deleting its row and column completes the induction.