Question 46
A chessboard of size $1000 \times 1000$ is tiled with tiles of size $1 \times 10$. You do not know the tiling but wish to uncover it. In order to do so, you can choose some $N$ cells on the board, following which you will learn what the positions of the tiles that cover those cells are. What is the least $N$ such that you can make your choice so as to always be able to reconstruct the complete tiling?