yourdomain.com

Здравствуйте, помогите решить: Сколькими способами можно расставить во всех клетках таблицы 4х4 числа 1 и 2 так, чтобы суммы чисел во всех строках и столбцах были просты?

Даю небольшую подсказку: в каждой строке или столбце может быть либо 1 двойка и 3 единицы, либо 3 двойки и 1 единица. Исходите из этого.

Ну что, подсказка не помогла? Ладно.
В Вашем квадрате $4\times 4$ выделим, скажем, верхний левый квадрат $3\times 3$ . Этот квадрат мы можем заполнить произвольно, а вот оставшиеся $$7$$

клеток в свете сказанного в предыдущем посте заполняются строго единственным образом. Например, пусть выделенный квадрат $3\times 3$ заполнен одними двойками. Тогда в большом квадрате $4\times 4$ в трёх правых и трёх нижних клетках должны быть единицы, а в правой нижней угловой - двойка.
Из этого следует, что размещение чисел в малом квадрате однозначно определяет искомую расстановку в большом квадрате. А сколько возможно перестановок в квадрате $3\times 3$ ? У нас есть $$9$$

мест, в каждое из которых мы можем вписать либо $$1$$

, либо

(аналог двоичного представления). Значит всего перестановок $$2^9=512.$$

А это и означает, что квадрат $4\times 4$ можно заполнить единицами и двойками $$512$$

способами.
Ну, как-то так.

Спасибо!

А уверены ли Вы, что все комбинации будут удовлетворять условию? Возможно, что не для каждого из 512 квадратов можно подобрать строку и столбец, удовлетворяющие условию или можно легко доказать, что для каждого?

buratino.2016 писал(а):Source of the post А уверены ли Вы, что все комбинации будут удовлетворять условию?

buratino.2016, а в чём Ваши сомнения? Конкретизируйте их. Что смогу, объясню. Доказательство перед Вами. По-моему, всё предельно ясно.

Вот Вам 3 примера (из 512 возможных), как из произвольно заполненного квадрата $3\times 3$ получается единственно возможная расстановка в квадрате $4\times 4$ :
1. $\begin{vmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{vmatrix}\Longrightarrow \begin{vmatrix} 1 & 1 & 1 &\!\!\vline\!\!& 2 \\ 1 & 1 & 1 &\!\!\vline\!\!& 2 \\ 1 & 1 & 1 &\!\!\vline\!\!& 2 \\\hline 2 & 2 & 2 &\!\!\vline\!\!& 1 \end{vmatrix}$
2. $\begin{vmatrix} 1 & 2 & 1 \\ 2 & 1 & 1 \\ 2 & 2 & 2 \end{vmatrix} \Longrightarrow \begin{vmatrix} 1 & 2 & 1 &\!\!\vline\!\!& 1 \\ 2 & 1 & 1 &\!\!\vline\!\!& 1 \\ 2 & 2 & 2 &\!\!\vline\!\!& 1 \\\hline 2 & 2 & 1 &\!\!\vline\!\!& 2 \end{vmatrix}$
3. $\begin{vmatrix} 2 & 2 & 2 \\ 1 & 1 & 1 \\ 2 & 2 & 2 \end{vmatrix} \Longrightarrow \begin{vmatrix} 2 & 2 & 2 &\!\!\vline\!\!& 1 \\ 1 & 1 & 1 &\!\!\vline\!\!& 2 \\ 2 & 2 & 2 &\!\!\vline\!\!& 1 \\\hline 2 & 2 & 2 &\!\!\vline\!\!& 1 \end{vmatrix}$

Попробую потелепатить. Возможно, товарищ имел в виду, что из квадрата 3х3 определяем три числа в нижней строке и три числа в правом столбце. А потом число в правом нижнем углу можно определить как из нижней строки, так и из правого столбца, и эти "определения" должны совпасть. Они конечно, совпадут, по соображениям четности, но в решении это явно не прописано.

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

Не могли бы Вы привести эти "соображения четности"?

yourdomain.com

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел

Способы расстановки чисел