Клетки квадрата $%n\times n$% частично покрыты доминошками $%1\times 2$% так, что больше доминошек выложить нельзя. Какое минимальное количество доминошек для этого потребуется?

задан 9 Апр 10:32

10|600 символов нужно символов осталось
2

Можно получить нижнюю границу для минимального числа $% N_n $% доминошек $% N_n \ge (n^2-2)/3, $% которая при $% n=3k $% принимает вид $% N_n \ge n^2/3 $% и является точной. Для этого пронумеруем клетки произвольным образом и для каждого элементарного $% (i,j) $%-отрезка (т. е. перегородки между клетками квадрата с номерами $% i, j $%) определим число $% c_{i,j} $%:

  • внутренней перегородки (не примыкающей своим концом к стенкам nxn-квадрата) равное 1;

  • внешней перегородки (примыкающей...) равное 1,5.

Определим матрицу $% M $% инциденций доминошек и пустых клеток, $% H $% строк которой соответствуют пустым клеткам, а $% N $% столбцов – доминошкам, причем инциденции в $% M $% будем определять по значению числа $% c_{i,j} $% для $% (i,j)$%-отрезка, по которому доминошка инцидентна пустой клетке.

В соответствии с условием задачи суммарное число инциденций:

  • для каждой доминошки не более 4;

  • для каждой неугловой пустой клетки равно 4;

  • для угловой пустой клетки равно 3.

Далее, подсчитав суммарное число инциденций в матрице $% M $% по строкам и столбцам, получим:

$% 4N \ge 4H – H’, $% где $% H’ $% – число угловых пустых клеток и $% 2N+H= n^2. $%

Отсюда $% 3H \le n^2+ H’/2, H \le (n^2+ 2)/3, N\ge (n^2-2)/3. $% Для $% n=3k $% нетрудно покрыть нужным образом квадрат $% n^2/3 $% доминошками, поэтому $% N_{3k}= 3k^2. $%

ссылка

отвечен 15 Май 15:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×13

задан
9 Апр 10:32

показан
409 раз

обновлен
15 Май 15:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru