Задача при поступлении в мфти

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача при поступлении в мфти

Сообщение Ian » 09 июл 2021, 20:26

Имеется много карточек, на каждой из которых написано одно из чисел 2, 3, 5, 7. Можно ли выложить в ряд 16 карточек так, чтобы ни одно из произведений нескольких подряд идущих чисел не было полным квадратом?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача при поступлении в мфти

Сообщение zykov » 10 июл 2021, 07:18

Можно и про эти четыре простых числа рассуждать, но несколько нагляднее перефразировать в форме 4-мерных векторов над GF2.
Возьмём 4 разных вектора у которых ровно одна единица. Сформируем последовательность длины 16 из таких векторов.
Нужно показать, что невозможно чтобы сумма любых подряд идущих векторов в этой последовательности была ненулевой.
(Тут важна аддитивность - если соединить две последовательности, то сумма по этому соединению равна сумме сумм по каждой из частей.)

Покажем это от противного. Предположим что есть такая последовательность, что все суммы ненулевые.
Рассмотрим 16 сумм начинающихся с первого вектора (индексы {1}, {1,2}, {1,2,3}, ... {1,2, ..., 16}).
Если одна из этих сумм нулевая, то противоречие.
Если нет нулевых, то найдутся две одинаковые суммы, т.к. всего есть 15 ненулевых 4-мерных векторов над GF2.
Тогда сумма начинающаяся за последним вектором короткой суммы и заканчивающаяся последним вектором длинной суммы равна нулю - противоречие.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача при поступлении в мфти

Сообщение Ian » 10 июл 2021, 10:09

Спасибо!
zykov писал(а):Можно и про эти четыре простых числа рассуждать, но несколько нагляднее перефразировать в форме 4-мерных векторов над GF2.

Школьникам: векторов из 4 знаков 0 или 1, причем при сложении 1+1 считать нулем. Или назвать 0="чет", 1="нечет"
----------
Интересно какой процент поступающих школьников справились

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача при поступлении в мфти

Сообщение zykov » 10 июл 2021, 10:14

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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача при поступлении в мфти

Сообщение zykov » 10 июл 2021, 10:17

Тут кстати можно обобщить.
Эти 4 числа не обязаны быть простыми. Могут быть любыми.
Если 4 вектора для этих чисел будут линейно заисимы, то можно доказать для 8 вместо 16 при ранге 3 и для 4 вместо 16 при ранге 2.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача при поступлении в мфти

Сообщение Ian » 10 июл 2021, 11:41

zykov писал(а):Если 4 вектора для этих чисел будут линейно заисимы, то можно доказать для 8 вместо 16 при ранге 3 и для 4 вместо 16 при ранге 2.

Если 4 вектора над GF2 имеют ранг 2 то два из них совпадают, Это не значит такой задачи не дадут, могут дать про числа 2,3,12.24. Но переходом к векторам из нулей и единиц сразу выясняется что 3 и 12 экивалентные карточки


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 12 гостей