Доказательство в HOL

Информатика
1

Студент Дима учится на втором курсе университета. На втором курсе в его университете читается курс математической логики. В этом курсе особое внимание акцентируется на автоматических доказателях – программах, позволяющих с их помощью доказывать различные сложные теоремы.

Курсовая работа по математической логике у Димы такая: необходимо доказать с помощью автоматического доказателя HOL, что шахматную доску размером 2^N x 2^N, из которой вырезана одна клетка, можно покрыть в один слой уголками из трех клеток.

Дима не верит в то, что это правда, и пытается составить контрпример. Ваша задача доказать Диме, что он неправ, и решить задачу для Диминых входных данных.

Входные данные

Входной файл INPUT.TXT содержит три натуральных числа N, X, Y (N ≤ 6; X,Y ≤ 2N). Этими числами задана доска 2^N x 2^N, из которой вырезана клетка с координатами (X, Y). X – координата по горизонтали, Y – по вертикали, (1, 1) – верхний левый угол доски.

Выходные данные

В выходной файл OUTPUT.TXT выведите 2^N строк по 2^N чисел – номера уголков, покрывающих соответствующие клетки. Каждый уголок характеризуется своим уникальным номером. Уголки пронумерованы начиная с единицы, без пропусков. Вырезанную клетку следует обозначить нулем.

2

В чем вопрос?

3

Мне кажется, ему нужна помощь с решением этой задачи.

4

5

Подумай как решить для n = 1, 2, 3 …
В таких задачах довольно часто можно найти патерн решения, в этой задаче ты можешь построить решение кое-чего побольше применив решение кое чего поменьше
Решение:

Решим для n = 1, это просто любой уголок. Для n = 2, это просто решение для n = 1 + решение для уголка где каждая клетка 2^1 * 2^1(подумай как построить). Для n = 3, решение для n = 2 + решение для уголка где каждая клетка 2^2 * 2^2(если ты смог построить уголок где каждая клетка 2^1 * 2^1, то этот строится также только с помощью уголка который ты получил на предыдущем шаге) и так далее

5 лайков