В первом случае я решал примерно по тому же принципу. А во втором у меня рассуждение было чисто вычислительное, с составлением графа из 8 вершин (по числу типов строк), и подсчёта количества путей длины 3. Это длинно. А с центральным квадратом -- очень прозрачно и красиво получается!
Что неверно в таком рассуждении (вторая задача)? Берем квадрат 2x2 клетки, например, верхний правый (строки 1,2 и столбцы 1,2), Там можно разместить нули и единицы семью разрешенными способами (тупо перебираем). Берем второй квадрат 2х2, имеющий с ним общую сторону (напр. строки 1,2 и столбцы 2,3). Методом тупого перебора выясняем, что там то же самое. Заметим, что совокупность всех семи разрешенных заполнений первого квадрата позволяет добавить к числу разрешенных заполнений все семь разрешенных заполнений второго квадрата. То же самое и для квадрата 2х2 строкой ниже (строки 2,3, столбцы 1,2), и для диагонального (строки 2,3, столбцы 2,3). Таких 2x2 квадратов в таблице 4х4 всего 9, каждый добавляет семь возможностей. Получается 7*9=63 варианта. (Предполагается, что чтобы большой квадрат 4х4 удовлетворял условию, необходимо и достаточно, чтобы условию удовлетворял каждый малый квадрат 2х2.)
Заметим, что совокупность всех семи разрешенных заполнений первого квадрата позволяет добавить к числу разрешенных заполнений все семь разрешенных заполнений второго квадрата.
То есть у вас получается вариантов заполнений первых шести клеток - 14? Это не так, попробуйте посчитать, получится 17.
Первая задачка из тех, которые страшно решать, когда по пересечённой местности идёшь - пока кубик себе представляешь и пытаешься уже учтённые варинты не забыть, обязательно ногу не туда поставишь ;))) У меня получилось 116, но с бумажкой не проверял, легко мог обсчитаться.
Вторую в уме до численного результата довести не пытался, но существует только 3 (с точностью до симметричных) варианта заполнения центральных 4 клеток, и для каждого задача сводится к заполнению полосок и отдельных клеток.
1. Три грани одного цвета, по одной грани других цветов. 4 варианта. 1.1. Грани одного цвета "уголком". Остальные цвета могут быть по часовой стрелке или против. Итого 8 вариантов. 1.2. Грани одного цвета "скобочкой". В центре скобочки один из трёх других цветов, остальное приводится поворотом. Итого 12 вариантов. 2. Две грани одного цвета, ещё две -- другого. 6 вариантов. 2.1. Одноцветные грани -- напротив. Единственное расположение. Итого 6 вариантов. 2.2. Пара одноцветных граней напротив, ещё пара -- рядом. Эти цвета надо выбрать, остальное определяется. Итого 12 вариантов. 2.3. Каждая пара одноцветных граней -- рядом.. 2.3.1. Эти грани -- "кольцом". 6 вариантов. 2.3.2. (Самое сложное) Берём первый цвет и клетку второго цвета, которая внутри "уголка". Это фиксирует положение куба. У другой клетки второго цвета два варианта расположения. У оставшихся двух цветов -- тоже два. Итого 24 варианта.
Я не уверен, что это будет "упрощение". То есть, я могу упростить, и проверить, что ответ тот же самый. Если да -- запостить упрощенный вариант, если нет -- найти ошибку и запостить правильный упрощенный вариант. Но видится мне здесь некий обман :-)
Во второй, если ее нужно решить именно для размера 4x4, а не для произвольного - я бы не писал программу, а возводил матрицу в степень. А именно - в каждой строчке у нас одна из 8 (число Фибоначчи) строчек из 0 и 1 без "11". И есть правила перехода между строчками - матрица 8x8 из 0 и 1: можно ли одну строчку поставить под другой. Можно мысленно дописать строчку из одних нулей над и под квадратом 4x4 - и получается, что мы ищем пути из 5 переходов. То есть это элемент матрицы, возведенной в пятую степень (ну или сумма всех элементов матрицы в третьей, что то же самое). Наконец, если аккуратно учесть симметрию строчек (две зеркально симметричные, 0000 и 1001, остальные разбиваются на пары), то остается вообще матрица 5x5 из 0, 1 и 2. Если я нигде не ошибся при заполнении, то ответ 1234.
Да, ответ в этой задаче именно такой (поэтому коммент я временно спрячу). Я как раз этим способом и решал, хотя у Вас предложена более удобная модификация.
Comments 21
Reply
В первом случае я решал примерно по тому же принципу. А во втором у меня рассуждение было чисто вычислительное, с составлением графа из 8 вершин (по числу типов строк), и подсчёта количества путей длины 3. Это длинно. А с центральным квадратом -- очень прозрачно и красиво получается!
Ваш коммент пока скрою.
Reply
Берем квадрат 2x2 клетки, например, верхний правый (строки 1,2 и столбцы 1,2), Там можно разместить нули и единицы семью разрешенными способами (тупо перебираем).
Берем второй квадрат 2х2, имеющий с ним общую сторону (напр. строки 1,2 и столбцы 2,3). Методом тупого перебора выясняем, что там то же самое. Заметим, что совокупность всех семи разрешенных заполнений первого квадрата позволяет добавить к числу разрешенных заполнений все семь разрешенных заполнений второго квадрата.
То же самое и для квадрата 2х2 строкой ниже (строки 2,3, столбцы 1,2), и для диагонального (строки 2,3, столбцы 2,3). Таких 2x2 квадратов в таблице 4х4 всего 9, каждый добавляет семь возможностей. Получается 7*9=63 варианта.
(Предполагается, что чтобы большой квадрат 4х4 удовлетворял условию, необходимо и достаточно, чтобы условию удовлетворял каждый малый квадрат 2х2.)
Reply
То есть у вас получается вариантов заполнений первых шести клеток - 14?
Это не так, попробуйте посчитать, получится 17.
Reply
Reply
Reply
Вторую в уме до численного результата довести не пытался, но существует только 3 (с точностью до симметричных) варианта заполнения центральных 4 клеток, и для каждого задача сводится к заполнению полосок и отдельных клеток.
Reply
Во второй задаче -- да, это хорошая идея. Именно таким способом здесь задачу уже решили, причём верно.
Reply
Но записывать начинать всё равно лень ;)))
Reply
Можно и не записывать, так как "случайно" такой ответ вряд ли можно получить.
Коммент с верным ответом "скриню".
Reply
1. Три грани одного цвета, по одной грани других цветов. 4 варианта.
1.1. Грани одного цвета "уголком". Остальные цвета могут быть по часовой стрелке или против. Итого 8 вариантов.
1.2. Грани одного цвета "скобочкой". В центре скобочки один из трёх других цветов, остальное приводится поворотом. Итого 12 вариантов.
2. Две грани одного цвета, ещё две -- другого. 6 вариантов.
2.1. Одноцветные грани -- напротив. Единственное расположение. Итого 6 вариантов.
2.2. Пара одноцветных граней напротив, ещё пара -- рядом. Эти цвета надо выбрать, остальное определяется. Итого 12 вариантов.
2.3. Каждая пара одноцветных граней -- рядом..
2.3.1. Эти грани -- "кольцом". 6 вариантов.
2.3.2. (Самое сложное) Берём первый цвет и клетку второго цвета, которая внутри "уголка". Это фиксирует положение куба. У другой клетки второго цвета два варианта расположения. У оставшихся двух цветов -- тоже два. Итого 24 варианта.
Ответ: 68 вариантов.
Reply
Коммент прячу под "скрин".
Reply
Reply
А именно - в каждой строчке у нас одна из 8 (число Фибоначчи) строчек из 0 и 1 без "11".
И есть правила перехода между строчками - матрица 8x8 из 0 и 1: можно ли одну строчку поставить под другой.
Можно мысленно дописать строчку из одних нулей над и под квадратом 4x4 - и получается, что мы ищем пути из 5 переходов. То есть
это элемент матрицы, возведенной в пятую степень (ну или сумма всех элементов матрицы в третьей, что то же самое).
Наконец, если аккуратно учесть симметрию строчек (две зеркально симметричные, 0000 и 1001, остальные разбиваются на пары), то остается вообще матрица 5x5 из 0, 1 и 2. Если я нигде не ошибся при заполнении, то ответ 1234.
Reply
Reply
Leave a comment