Q9 Matemática  (Balkan MO Shortlist 2015)

Um tabuleiro de xadrez $1000\times 1000$ é coberto por dominós $1\times 10$ que podem ser girados. Não sabemos qual é a capa, mas estamos procurando por ela. Por isso, escolhemos algumas células $N$ do tabuleiro, pelas quais conhecemos a posição dos dominós que as cobrem. Qual é o $N$ mínimo tal que após a escolha de $N$ e conhecendo os dominós que os cobrem, podemos ter certeza e para o resto da cobertura? (Bulgária)