Математическое и загадочное

[Fireman]

20.08.2020 в 21:55, _Иван сказал:

Вопрос: какое минимальное количество начальных фишек нужно, чтобы закрыть всё поле?

если в лоб, то максимум 24

 

если чуть-чуть подумать, то 12

 

 

подозреваю, что надо еще подумать, но я уже в пижаме

 

 

P.S. а центральный элемент - это так просто раскрашен или это выколотая дырка? я что-то думал, что это отсутствие элемента

Изменено 21 августа, 2020 пользователем Fireman

[Fireman]

11 часов назад, Fireman сказал:

подозреваю, что надо еще подумать, но я уже в пижаме

 

Наступило утро

 

 

Можно обойтись 9, но надо думать дальше

 

 

P.S.

 

на первый взгляд кажется, что это всё, минимальный вариант (в смысле 9 элементов) исходя из следующих предположений:

1) расставленные элементы должны обладать симметрией (хотя бы на каждом слое), причем симметрия эта на 120 градусов

2) заполнить верхний (5ый) слой можно только если на этом слое присутствуют заполненные элементы

 

1) и 2) даёт то, что на 5ом слое должно быть 3 элемента

 

3) для начала заполнения необходимо 3 элемента, а поскольку фигура симметричная - 3 элемента должны находиться в центре

4) для заполнения слоя необходимо, чтобы или на слое или на соседних слоях находились заполненные элементы

 

таким образом необходимо по 3 элемента на слоях 2, 4, 5 или 2, 3, 5 - итого 9 элементов

Изменено 22 августа, 2020 пользователем Fireman

[Vladislav Nikolaev]

В задаче про турнир я придумал решение, которое, как оказалось, полностью совпадает с решением Рогожникова. А что касается решения через матрицы, то, мне кажется, оно имеет отношение к теории неотрицательных матриц. Тема эта сложная (теоремы Перрона, Фробениуса). Неделю назад я вообще ничего этого не знал. Почитать можно, например, в учебнике Гантмахера.

[Vladislav Nikolaev]

Есть простое доказательство того что 9 это минимум. Вот аналогичная задача:

 

Дан куб 6 х 6 х 6, состоящий из 216 маленьких кубиков 1 х 1 х1. Допустим что каждый кубик или синий или красный. Если какой-то синий кубик соприкасается гранями с тремя или более красными то он становится красным. Сколько минимум должно быть вначале красных кубиков чтобы все потом стали красными?

[_Иван]

21.08.2020 в 23:08, Fireman сказал:

P.S. а центральный элемент - это так просто раскрашен или это выколотая дырка? я что-то думал, что это отсутствие элемента

Просто раскрашен. Не очень красивую картинку я нашёл  Девять --- это правильный ответ, зачот!

[Vladislav Nikolaev]

Периметр фигуры, являющейся объединением всех отмеченных шестиугольников, увеличиваться не может. При добавлении очередного шестиугольника он всегда увеличивается не более чем на 3 и одновременно уменьшается не менее чем на 3. Так как периметр всего поля = 54, вначале должно быть не менее 9 шестиугольников. Аналогично, в задаче про кубики, вначале их должно быть не менее 36. Есть очень простой способ, как это сделать.
А это решение, полученное программным перебором. Для того чтобы доказать что это возможно. Проверить можно тоже с помощью программы?.
Кубики имеют координаты от 000 до 555.
Красные кубики вначале:
 100, 020, 420, 130, 240, 550, 011, 521, 041, 102, 402, 312, 022, 132, 052, 352,
 003, 503, 113, 413, 323, 343, 543, 253, 304, 214, 034, 234, 554, 505, 415, 025,
 225, 525, 435, 155.

[Рогожников Евгений]

07.09.2020 в 12:33, Vladislav Nikolaev сказал:

Периметр фигуры, являющейся объединением всех отмеченных шестиугольников, увеличиваться не может. 

 

Да уж. Супер красивое решение. Признаюсь, что долго ломал голову над этой задачей, но и близко не был к решению. Пробовал для начала решать для куба со стороной 3.  Для него удалось доказать, что потребуется не менее 10 кубиков, т.к легко показать,что на каждой грани должно быть не менее 3-х кубиков. Хотя из идеи с периметрами следует что получится не менее 9. Т.е все же это не всегда даст точный ответ

 

 

 

07.09.2020 в 12:33, Vladislav Nikolaev сказал:

Аналогично, в задаче про кубики, вначале их должно быть не менее 36. Есть очень простой способ, как это сделать.

 

Но для куба  сто стороной 6 у меня  не получилось подойти к ответу  36. Хотя, после того как он был озвучен, простое способ пришел на ум сам собой.

 

Расстановку проще описать так:

Разрежем куб на 6 горизонтальных слоев. Каждый слой это это параллелепипед   1x6x6.

Пронумеруем слои цифрами от 1 до 6 снизу вверх. Ну а на каждом слое введем координаты от 1 до 6.Т.е клетка слоя получит координаты (i,j), где эти числа меняются от 1 до 6 ( математическая , а не программисткая нумерация)

 

На i-м слое красные  квадраты поместим на две диагонали:

первая диагональ от клетки (i,1) до клетки (6,6-i).

вторая диагональ от клетки (1,i) до клетки (6-i,6).

На первом слое диагональ одна , т.к эти две диагонали совпадут.

 

Итого число квадратов будет (6+10+8+6+4+2) = 36

Ну а в качестве того что они дадут нужную раскраску использую принятое тут у нас "Смотри".

 

[Vladislav Nikolaev]

 

14 часов назад, Рогожников Евгений сказал:

первая диагональ от клетки (i,1) до клетки (6,6-i).

вторая диагональ от клетки (1,i) до клетки (6-i,6).

 

 

Наверное должно быть 7-i ?

Т.е. вот так?

 

[Рогожников Евгений]

09.09.2020 в 21:45, Vladislav Nikolaev сказал:

Наверное должно быть 7-i ?

Т.е. вот так

Да. С рисунком стало нагляднее

[Vladislav Nikolaev]

Решение неправильное. То что оно неправильное можно просчитать. Но оно очевидно неправильное.

[Рогожников Евгений]

2 часа назад, Vladislav Nikolaev сказал:

Решение неправильное. То что оно неправильное можно просчитать. Но оно очевидно неправильное.

 

Да,действительно. Самый нижний 6-й слой  совсем не заполняется.

 

Но, вроде, простой модификацией получаем правильное решение

[Vladislav Nikolaev]

Да, теперь правильно. Остался вопрос - почему первое решение было очевидно неправильным. И хотелось бы увидеть доказательство почему для для куба 3х3х3 недостаточно 9?.
Вот моё решение:
Делим куб 6х6х6 на 8 кубов 3х3х3, и из них выбираем 4, центры которых образуют правильный тетраэдр. В этих четырёх отмечаем по 9 кубиков, как показано на рисунке.

 

Какое максимальное число ферзей можно расставить на шахматной доске 20х20 так, чтобы ни один ферзь не находился под боем со стороны более чем одного другого ферзя?

[Рогожников Евгений]

5 часов назад, Vladislav Nikolaev сказал:

Остался вопрос - почему первое решение было очевидно неправильным.

Я же написал - это очевидно потому что нижний 6-й слой совсем не заполнится. Если развернуть этот тезис, то это будет следующее рассуждение:

- Даже если предположить, что 5-й слой будет полностью заполнен, то каждому кубику с шестого слоя он даст в соседи только одну красную грань. Так что на 6-м слое, чтобы раскрасить в красный хотя бы один новый кубик, нужно чтобы он изначально имел на этом слое двух красных соседей. Но их, очевидно, нет.

5 часов назад, Vladislav Nikolaev сказал:

И хотелось бы увидеть доказательство почему для для куба 3х3х3 недостаточно 9

 

 

А вот тут я ошибся. решение с 9-ю также есть и оно похоже на решение для 6-ти

 

 

[Vladislav Nikolaev]

Всё очень просто: во втором слое четыре синих кубика имеют по пять красных соседних кубиков. А если хотя бы у одного синего кубика рядом будет больше чем три красных, площадь боковой поверхности будет меньше чем нужно.   

[Рогожников Евгений]

14.09.2020 в 09:25, Vladislav Nikolaev сказал:

Какое максимальное число ферзей можно расставить на шахматной доске 20х20 так, чтобы ни один ферзь не находился под боем со стороны более чем одного другого ферзя?

 

Пока удалось доказать, что более 26 ферзей поставить нельзя. Соображения тут следующие: всех феррзей можно разбить на группы, поместив в одну группу тех, что бьют друг друга. Ясно что в группе будет один или два ферзя. Каждой группе поставим в соответствие строки и столбцы, в которых расположены ферзи этой группы. Для одного ферзя это будет одна строка и один столбец, т.е ровно два "строко-столбца". Для пары ферзей это будет либо 3 либо 4  "строко-столбца". При этом ясно, что "строко-столбцы" разных групп не пересекаются. Таким образом, на одного ферзя в среднем будет приходиться не менее 3/2 "строко-столбца". Всего же их 40. Значит, всего ферзей не может быть более 40 разделить на 3/2, т.е 80/3 = 26 + 2/3.

 

Что же касается максимальной расстановки, то пока вижу только 20. Известно, что для N>3 можно на доске NxN разместить N ферзей которые не бьют друг друга. Расстановок там много, но всегда есть классический случай "лесенкой":

(2, 4) (3, 6)(4,8)(5,10),(6,12)(7,14)(8,16)(9,18)(10,20)

(11,1)(12, 3)(13,5)(14,7)(15,9)(16,11)(17,13)(18,15)(19,17)(20,10)

 

Но для такой расстановки небьющих друг дуга ферзей любого нового ферзя будут бить сразу два ферзя.