Разрежем квадрат на четыре квадрата n×n. Если Вася закрашивает две клетки в разных четвертинках n×n, то Петя сможет разрезать нужным образом большой квадрат либо по горизонтали, либо по вертикали.

  Рассмотрим случай, когда Вася закрасил две клетки в одной четвертинке n×n. Эти клетки лежат либо в разных столбцах, либо в разных строках (иначе бы эти клетки совпали). Пусть для определённости закрашенные клетки лежат в разных строках (для столбцов рассуждение аналогично). Разрежем четвертинку n×n по горизонтали так, чтобы закрашенные клетки оказались в разных её частях. После этого продолжим разрез по границе четвертинок до центра квадрата 2n×2n и отразим получившийся разрез относительно этого центра (см. рисунок).

Всегда.