Задача про ласточек (Наука и жизнь)

[kthxbye]

Недавно на глаза попалась задачка (7-й номер журнала "Наука и жизнь" за 1973 год, раздел "Психологический практикум"). Вот ее точная формулировка:

Цитата:

На телефонных проводах сидели двадцать пять ласточек. Кто-то вспугнул их, и пять ласточек улетели, в том числе улетела семнадцатая. После этого в каждом горизонтальном и вертикальном ряду осталось по четыре ласточки. Потом еще улетели пять ласточек и среди них восьмая. Тогда в горизонтальных и вертикальных рядах осталось по три ласточки. В третий и четвертый раз улетели еще по пять ласточек и среди них двадцатая и шестая. Теперь в каждом горизонтальном и вертикальном ряду осталось сначала по две и, наконец, по одной ласточке.

$$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{bmatrix}$$

Какие пять ласточек остались сидеть на проводах?

В конце номера приводится также уникальное решение:

Цитата:

1, 22, 18, 14, 10

Разве может быть в данной задаче уникальное решение? Условия слишком размыты и по моим прикидкам тут должно быть как минимум 48 решений, каждое из которых дополнительно имеет по несколько вариантов последовательного удаления определенных птиц.

Необходимо отметить, что мой прогноз относится к случаю, когда на 3-м шаге улетает 20-ая ласточка, а на 4-ом - 6-ая. Так ли это?

[sergey zhukov]

kthxbye
Похоже на задачу, в которой множество разных путей ведет к одному и тому же результату.

Хотя нет. Есть много решений.

[Gevin Magnus]

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

[gris]

а не могут ли ласточки 6 и 20 слететь в третьем слёте?

$$\begin{bmatrix} 4 & 8 & 12 & 16 & 25 \\ 5 &9 & 13 & 17 & 21 \\ 2 & 6 & 14 & 20& 23 \\ 1 & 7 & 15 & 18 & 24 \\ 3 & 10 & 11 & 19 & 22 \end{bmatrix}$$

Каждая строка это слёт. Две последние можно поменять. и будет целых два решения. Я только по пункту размытости условия .
Кто считал определители,тот наверняка делал перебор разбиения первоначального квадрата на пять подмножеств с разными строками и столбцами.

[sergey zhukov]

Задача в разделе "Психологический практикум". Видимо, задача какая-то "психологическая".

[Sender]

sergey zhukov в сообщении #1633903 писал(а):

Видимо, задача какая-то "психологическая".

Наверное, предполагается, что если испугается хоть одна ласточка, улетят все.

[Mihr]

Sender в сообщении #1633907 писал(а):

Наверное, предполагается, что если испугается хоть одна ласточка, улетят все.

Кстати, да. Вспомнилась такая вот загадка:

Цитата:

На дереве сидело пятнадцать ворон. Охотник выстрелил и убил одну ворону. Сколько ворон осталось сидеть на дереве?

Правильный ответ: ни одной. Все вороны, оставшиеся в живых, тут же улетят.

[TOTAL]

Есть у кого сам журнал с ласточками? Посмотреть бы этим ласточкам в глаза.

[svv]

Условие

Ответ

[TOTAL]

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

[svv]

Поскольку рубрика в "Науке и жизни" называется "Психологический практикум", предположу, как автор составлял задачу. В том далёком 1973 году он интересовался латинскими квадратами (ЛК). Их связь с задачей очевидна. Удобно присвоить каждой ласточке одно из чисел $0,1,2,3,4$ (номер группы) и считать, что сначала улетели ласточки группы $4$, потом $3$, ..., а осталась группа $0$. Тогда номер группы показывает, сколько осталось ласточек в каждом столбце и строке после её отлёта.

Рассмотрим ЛК порядка $5$. Их всего $161280$. Будем считать эквивалентными ЛК, которые можно получить друг из друга композицией перестановки строк, столбцов и "перестановки символов" (биекция $M\to M$, где $M=\{0,1,2,3,4\}$). Тогда существует всего $2$ класса эквивалентности. И в одном из них есть представитель, имеющий настолько упорядоченную форму, что каноничнее не бывает:
$\begin{bmatrix}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{bmatrix}$
Мало того, что первая строка и первый столбец содержат числа в порядке возрастания (чего всегда легко добиться), так это ещё и таблица Кэли для циклической группы $5$ порядка. Поэтому такая табличка встречается во многих книгах и статьях — это ключевой пункт моего расследования.

Дальше автор выбрал $4$ ласточки, по одной из каждой "улетевшей" группы:
$\begin{bmatrix}0&1&2&3&4\\{\color{magenta} 1}&2&{\color{magenta} 3}&4&0\\2&3&4&0&1\\3&{\color{magenta} 4}&0&1&{\color{magenta} 2}\\4&0&1&2&3\end{bmatrix}$
Позиции нулей дают решение задачи.

Сознавал ли автор, что при данных условиях решение неединственно? Наверное, да.

[Утундрий]

Может быть стоит учесть направление взгляда ласточек?

[sergey zhukov]

Если попыхтеть над условием задачи и дать немного больше нужной информации, то можно эту задачу сделать интереснее, а решение единственным. Если знать часть ласточек, которые улетели на данном шаге, а так же тех, которые улетели на последующих (и, значит, не могут улететь на данном шаге), то можно будет дать такой минимум информации, чтобы можно было все определить однозначно.

Только не слишком простой такая задача окажется, по моему.

[svv]

sergey zhukov
Можно, например, сделать два таких исправления.
Во-первых, в последней пятёрке улетевших пусть будет 2-я ласточка (а про 6-ю не упоминаем вовсе).
Во-вторых, после каждого отлёта остаётся одно и то же число ласточек на каждой вертикали, горизонтали и диагонали.
* 1 * * *
* * 3 * *
* * * * *
* 4 * * 2
* * * * *
Напомню, что у меня порядок отлёта 4,3,2,1, а 0 — оставшиеся.

Тогда решение будет единственным (но не будет совпадать с авторским).

(Ответ)

2 1 4 0 3
4 0 3 2 1
3 2 1 4 0
1 4 0 3 2
0 3 2 1 4
Ласточки, про которых известно из условия, когда они улетают, выделены цветом.