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

Samorezishe · Сообщение **Samorezishe** » 26 апр 2015, 17:45

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

ARRY · Сообщение **ARRY** » 27 апр 2015, 04:19

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

ARRY · Сообщение **ARRY** » 27 апр 2015, 13:09

Ну что, подсказка не помогла? Ладно.
В Вашем квадрате $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$$

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

Samorezishe · Сообщение **Samorezishe** » 28 апр 2015, 20:31

Спасибо!

buratino.2016

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

ARRY · Сообщение **ARRY** » 29 сен 2015, 20:02

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

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

ARRY · Сообщение **ARRY** » 29 сен 2015, 22:02

Вот Вам 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}$

12d3 · Сообщение **12d3** » 30 сен 2015, 06:31

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

buratino.2016

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

buratino.2016

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

yourdomain.com