Как доказать?

[zgemm]

Имеется задачка, и не могу до конца ее правильно решить:

Для натуральных чисел $p$, $q$ и $r$ задано $pqr$ единичных кубов, в которых по смой длинной диагонали просверлено отверстие, и все эти кубы через эти отверстия нанизаны на нитку длины $pqr\sqrt{3}$.

Пробуем сложить всю эту конструкцию так, чтобы получился параллелепипед $p \times q \times r$ не разрывая при этом нить.
а) Для каких чисел $p$, $q$ и $r$ это возможно?
б) Для каких чисел $p$, $q$ и $r$ возможно, чтобы начало и конец нити совпадали?

Для а) как я понимаю, надо, чтобы хотя бы одно значение было нечетным. Для б) как я понимаю, одно значение должно быть нечетным, и одно должно быть четным. По крайней мере так можно построить. Но вот как доказать, что более общего варианта нет?

[ИСН]

Зачем нечётным-то?

[mihiv]

Да, нечетность необязательна. Например, для куба $2\times 2\times 2$ имеет решение задача б).

[EUgeneUS]

Для варианта б) необходимым условием является, чтобы все три числа были четными.
Почти очевидно при рассмотрении проекции нитки на три оси.

[ИСН]

Зачем все чётными-то?

Вложение:

4diag.png [ 11.17 Кб | Просмотров: 838 ]

[EUgeneUS]

ИСН
Да, Вы правы, конечно.

Необходимое условие: четными должны быть все три произведения $pq, qr, rp$.
Это возможно, когда из чисел $p, q, r$ не более чем одно нечетное, остальные - четные.

Это же условие является достаточным, так как блоками $2 \times 2 \times 1$ можно заполнить любой такой параллелепипед, не разрывая нитку.

UPD: пока зачеркну. Похоже, опять излишне жесткое условие.

[EUgeneUS]

Итак:
1. Два или три четных - можно уложить замкнутой ниткой.
2. Два или три нечетных - можно уложить разомкнутой ниткой. Легко укладывается змейкой по слоям с нечетными сторонами.
Ответ на вопрос а) - для любых.
3. Если все три числа нечетные - уложить замкнутой ниткой нельзя.

Осталось доказать, что в случае два нечетных и одно четное нельзя уложить замкнутой ниткой, или найти способ такой укладки.

-- 11.03.2024, 10:02 --

Ещё наблюдение: задав направление диагонали в одном малом кубике, мы задаем направление диагоналей во всех кубиках!
При этом в угловых кубиках есть запрещенные направления - диагональ торчит в угол параллелепипеда. Если
А) "плохих углов" нет - можно сложить с замкнутой ниткой
Б) "плохих углов" два - можно сложить разомкнутой ниткой.
В) "плохих углов" четыре - нельзя сложить (но так не бывает).
Г) нечетного количества "плохих углов" - не бывает.

[EUgeneUS]

EUgeneUS в сообщении #1632454 писал(а):

Осталось доказать, что в случае два нечетных и одно четное нельзя уложить замкнутой ниткой, или найти способ такой укладки.

Этот вариант проверил перебором. Замкнутой ниткой уложить нельзя.

Если кому-то интересны детали решения - могу подробнее написать позже, нормальной клавиатуры.

[EUgeneUS]

Вариант в)

В условиях задачи известно, что как минимум одна верека заканчивается в углу большого параллелепипеда. При этом $p, q, r$ - четные.
Вопрос: каково минимальное количество веревок?

[EUgeneUS]

Общее решение интуитивно понятно. Но формализация будет многословной Может кто придумает лучшую.

0. Предположим, что удалось протянуть веревку через все кубики в параллелепипеде.
1. Поместим параллелепипед в декартову систему координат, с началом в одном его углу. Ребро кубика считаем за единицу, а $p, q ,r$ - положительными числами.
2. Тогда большая диагональ в любом кубике $(i, j, k)$ уменьшает или увеличивает каждую координату на единицу. $\vec{d_{(i, j, k)}} = (a_i, b_j, c_k)$. Где $a_i, b_j, c_k$ равны единице или минус единице
3. Назовем большие диагонали в кубике эквивалентными, если они проходят через те же вершины, но могут отличаться направлением: $\vec{d_{(i, j, k)}} = (a_i, b_j, c_k) \sim \vec{d_{(i, j, k)}^{*}} = -1 \cdot (a_i, b_j, c_k)$. Обозначим такую ненаправленную диагональ, как: $\tilde{d_{(i, j, k)}} = \pm1 \cdot (a_i, b_j, c_k)$

Отметим, что в каждом кубике может быть 4-ре различных ненаправленных диагонали.

4. Далее заметим, что при переходе на соседний кубик ненаправленная диагональ определена однозначно (при условии неразрывности веревки), а именно:
$\tilde{d_{(i+1, j, k)}} = \tilde{d_{(i, j, k)}} \times (-1, 1 ,1)$, где операция $\times$ означает покомпонентное умножение.

5. Тогда для каждого кубика $(i, j, k)$ можно записать: $\tilde{d_{(i, j, k)}} = \tilde{d_{(1, 1, 1)}} \times ((-1)^i, (-1)^j , (-1)^k)$
Откуда следует, что расположение главной диагонали в любом кубике однозначно определяется расположением главной диагонали в кубике $(1,1,1)$.

6. Отметим все диагонали в кубиках, соответствующие какой-то ненаправленной диагонали кубика $(1,1,1)$.
а) всего таких диагоналей будет $pqr$ - по количеству кубиков.
б) а значит веревка должна пройти пройти через их все!
в) множество этих диагоналей (вместе с множеством вершин кубиков, через которые проходят диагонали) будет составлять некий граф.
7. Степень вершины этого графа могут быть:
$8$ - для вершины "внутри большого куба"
$4$ - для вершины "на поверхности грани"
$2$ - для вершины "на ребре"
$1$ - если диагональ углового кубика проходит через угол параллелепипеда. Такие диагонали будем называть плохими ребрами.

-- 11.03.2024, 18:11 --

8.
а) Есть четыре варианта параллелепипедов:
чет-чет-чет
чет-чет-нечет
чет-нечет-нечет
нечет-нечет-нечет

б) и есть четыре варианта диагоналей в кубике $(1,1,1)$:
$\pm1 \cdot (1,1,1)$
$\pm1 \cdot (1,-1,1)$
$\pm1 \cdot (-1,1,1)$
$\pm1 \cdot (-1,-1,1)$

Итого, 16 вариантов для перебора.

-- 11.03.2024, 18:16 --

Перебор показывает, что
1. для параллелепипедов "чет-чет-чет" и "чет-чет-нечет" есть такие диагонали в первом кубике, что граф получается без плохих ребер. Известно, что если в графе все вершины имеют четную степень, то его можно обойти ручкой, "не отрываясь от листа", при этом вернёмся в точку, с которой начали.

2. для параллелепипедов "чет-нечет-нечет" и "нечет-нечет-нечет" нет таких диагоналей в первом кубике, что граф получается без плохих ребер. Но есть такие диагонали в первом кубике, что граф получается с ровно двумя плохими ребрами. Известно, что такой граф можно обойти ручкой, "не отрываясь от листа". При этом начало должно быть в одной вершине с нечетной степенью, а окончание - в другой вершине с нечетной степенью.

ЧТД.

[EUgeneUS]

Кстати:

EUgeneUS в сообщении #1632490 писал(а):

для параллелепипедов "чет-нечет-нечет" и "нечет-нечет-нечет" нет таких диагоналей в первом кубике, что граф получается без плохих ребер. Но есть такие диагонали в первом кубике, что граф получается с ровно двумя плохими ребрами.

Для этих параллелепипедов граф получается всегда с ровно двумя плохими ребрами.
При этом:
а) для "нечет-нечет-нечет" плохие ребра всегда оказываются на большой диагонали параллелепипеда.
б) для "чет-нечет-нечет" плохие ребра всегда оказываются на одном ребре параллелепипеда.

EUgeneUS в сообщении #1632490 писал(а):

для параллелепипедов "чет-чет-чет"

реализуются два варианта:
а) либо плохих ребер нет (веревка замкнута).
б) либо плохих ребер ровно четыре. Тогда нужно минимум две веревки - ответ на вопрос в).

[EUgeneUS]

EUgeneUS в сообщении #1632499 писал(а):

реализуются два варианта:
а) либо плохих ребер нет (веревка замкнута).
б) либо плохих ребер ровно четыре. Тогда нужно минимум две веревки - ответ на вопрос в).

Вчера писал по памяти, ну и подвела в очередной раз.
Для параллелепипеда "чет-чет-чет" реализуются два варианта:
а) либо плохих ребер нет (веревка замкнута).
б) либо плохих ребер ровно восемь. Во всех углах. Это легко видеть на кубике $2 \times 2 \times 2$

Для варианта в), казалось бы нужно $8/2=4$ веревки... Но это неверно. Двух всё равно хватит.