Районная олимпиада, 2003-2004 учебный год, 10 класс

Квадратная доска $6 \times 6$ заполнена костяшками домино $1 \times 2$. Докажите, что можно провести вертикальный или горизонтальный разрез этой доски, не пересекающий ни одной из костяшек домино.