1. Квадратная карта звёздного неба разделена на одинаковые квадраты. Четыре звезды оказались единственными в своём квадрате. Ещё 16 имеют по одной соседке, 6 - по две, 12 по три. Найдите наименьшее возможное количество пустых квадратов на этой карте.

Ответ: 11

Решение:

• Всего квадратов с звездами: 4 (с одной звездой) + 16 (с одной соседкой) + 6 (с двумя) + 12 (с тремя) = 38
• Минимальное количество квадратов с одной соседкой достигается, если все квадраты с более чем одной звездой являются соседями для квадратов с одной звездой.
• 16 квадратов имеют по одной соседке, но квадраты с двумя и тремя звездами могут быть их соседями.
• Сначала разместим 12 квадратов с тремя звездами. Каждый из них может быть соседом для трех квадратов с одной звездой. Это займет 12 * 3 = 36 мест соседей. Т.к. у нас всего 16 квадратов, то некоторые квадраты будут соседствовать с несколькими квадратами с 3 звездами.
• Далее разместим 6 квадратов с двумя звездами. Каждый из них может быть соседом для двух квадратов с одной звездой. Это займет 6 * 2 = 12 мест соседей.
• Общее количество соседних мест для квадратов с одной звездой, занятых квадратами с двумя и тремя звездами: 36 + 12 = 48. Т.к. у нас всего 16 квадратов, то некоторые квадраты будут соседствовать с несколькими квадратами с 3 звездами.
• Чтобы минимизировать количество пустых квадратов, разместим квадраты с тремя звездами вокруг квадратов с одной звездой. Каждый квадрат с тремя звездами может окружать три квадрата с одной звездой. Таким образом, 12 квадратов с тремя звездами будут окружать 12 * 3 / 1 = 36 квадратов с одной звездой.
• Затем разместим квадраты с двумя звездами. Каждый квадрат с двумя звездами может окружать два квадрата с одной звездой. Таким образом, 6 квадратов с двумя звездами будут окружать 6 * 2 / 1 = 12 квадратов с одной звездой.
• Теперь у нас 4 квадрата с одной звездой + 16 квадратов с одной соседкой + 6 квадратов с двумя соседками + 12 квадратов с тремя соседками = 38 квадратов.
• Общее количество квадратов = 4 + 16 + 6 + 12 = 38.
• Теперь найдем минимальное количество пустых квадратов. Допустим, все квадраты расположены так, что нет перекрытий. Тогда для каждого из 16 квадратов с одной соседкой нужно хотя бы по одному пустому квадрату рядом. Однако, квадраты с 2 и 3 звездами уже являются соседями для квадратов с 1 звездой.
• Каждый квадрат с 3 звездами занимает 3 соседних позиции, а каждый квадрат с 2 звездами занимает 2 соседние позиции.
• 12 квадратов с 3 звездами могут занять до 12 * 3 = 36 соседних позиций.
• 6 квадратов с 2 звездами могут занять до 6 * 2 = 12 соседних позиций.
• Общее количество соседних позиций = 36 + 12 = 48. Так как у нас только 16 квадратов с одной соседкой, то эти квадраты с 2 и 3 звездами покроют все соседние позиции для этих 16 квадратов.
• Но у нас есть 4 квадрата с одной звездой, у которых нет соседей. Значит, им нужны 4 пустых квадрата.
• Кроме того, квадраты с 3 звездами могут окружать не только квадраты с одной звездой, но и другие квадраты с 3 звездами. И квадраты с 2 звездами могут окружать не только квадраты с одной звездой, но и другие квадраты с 2 звездами.
• Тогда у нас остается 16 - (12 * 3 + 6 * 2) = 16 - (36 + 12) = 16 - 48 = -32. Это означает, что все 16 квадратов с одной соседкой могут быть полностью окружены квадратами с 2 и 3 звездами.
• Минимальное количество пустых квадратов = Общее количество квадратов - Количество квадратов с звездами = 38 - 27 = 11.

Ответ: 11