Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 4 |
[ Сообщений: 34 ] | На страницу 1, 2, 3, 4 След. |
|
Автор | Сообщение | |
---|---|---|
Andy |
|
|
Здравствуйте! Если Вам это не очень трудно, сообщите, пожалуйста, можно ли использовать латинские квадраты для решения такой задачи: "Дано: 64 человека. 8 столов по 8 мест. 9 туров (перемешиваний). Задача: за 9 туров перемешать людей за столами так, чтобы каждый в итоге встретился с каждым и не встретился ни с кем повторно. То есть, чтобы каждый раз за столом были люди, который до этого не встречались за одним столом"? Эта задача встретилась в одном из вопросов на форуме, в котором я участвую. В своё время, когда я судил соревнования по шахматам, я читал про математические основы составления расписаний соревнований. Насколько я помню, при изучении расписаний турниров по схевенингенской системе встретился с упоминанием латинских квадратов. Если я правильно понимаю, то предложенную задачу можно рассматривать как обобщение задачи о составлении расписания турнира по схевенингенской системе на случай, когда в турнире участвует больше двух команд. Условие, что участники не должны оказаться за одним столом повторно, как я понимаю, сильно усложняет эту задачу. Можно ли утверждать, что задача имеет решение? P. S. Нашёл интересный материал о латинских квадратах здесь. |
||
Вернуться к началу | ||
За это сообщение пользователю Andy "Спасибо" сказали: Nataly-Mak |
||
Nataly-Mak |
|
|
Andy
спасибо большое за интересные задачи, связанные с латинскими квадратами. Наверное, первая задача решается с помощью латинских квадратов 8-го порядка. Но сильно не думала. А вот про расписание шахматных турниров - так тут однозначно используются латинские квадраты и даже ортогональные латинские квадраты. По данной вами ссылке видим на рис. 73 латинский квадрат 6-го порядка, а на рис. 74 - ортогональные латинские квадраты 4-го порядка и соответствующее им расписание. Весьма интересное применение ортогональных латинских квадратов! |
||
Вернуться к началу | ||
За это сообщение пользователю Nataly-Mak "Спасибо" сказали: Andy |
||
Andy |
|
|
Nataly-Mak
А можете ли Вы с Вашим знанием латинских квадратов однозначно утверждать, что сформулированная задача имеет решение или наоборот? |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Andy
вы про рассаживание 8 человек за 8 столами? А это аналогично расписанию шахматного турнира? Вот как приведено на рис.74 по данной вами ссылке. Если аналогично, тогда задача однозначно имеет решение. |
||
Вернуться к началу | ||
Andy |
|
|
Nataly-Mak
Это не совсем аналогично, как я понимаю. Впрочем, я попробую сам поэкспериментировать с латинскими квадратами восьмого порядка. |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Andy
А почему не совсем аналогично? Я вот как-то не совсем понимаю эту задачу с рассаживанием 8 человек за 8 столами. Если рассаживать их так, как шахматистов рассаживают играть партии (см. рис 74), тогда и здесь так же точно рассадим. По ортогональной паре латинских квадратов 8-го порядка. А таких пар известно множество, выбирайте любую. Могу дать ссылку на мою статью с такими ортогональными ЛК. Если же эти задачи не совсем аналогичные, тогда я не совсем понимаю суть первой задачи. |
||
Вернуться к началу | ||
Andy |
|
|
Nataly-Mak
Давайте абстрагируемся от шахмат. Пронумеруем всех участников числами от 1 до 64 и разделим их на "восьмёрки" - группы по восемь человек в каждой. Нужно выполнить девять перемешиваний (туров). Пусть в первом туре за одним столом встретились участники одной восьмёрки, то есть за первым столом встретились участники с номерами 1-8, за вторым столом - участники с номерами 9-16, ..., за восьмым столом - участники с номерами 57-64. Теперь рассмотрим остальные восемь туров (со второго по девятый). В каждом из восьми туров нужно свести за одним столом восемь участников так, чтобы никто из них не встретился дважды (учитывая и первый тур). Я понимаю так, что можно использовать греко-латинский квадрат. Перенумеруем участников, присвоив им двузначные номера по следующей схеме: старый номер - новый номер 1 - 11 2 - 12 ... 8 - 18 9 - 21 10 - 22 ... 16 - 28 ... 64 - 88. Как по-Вашему? |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
Andy писал(а): Я понимаю так, что можно использовать греко-латинский квадрат. Перенумеруем участников, присвоив им двузначные номера по следующей схеме: старый номер - новый номер 1 - 11 2 - 12 ... 8 - 18 9 - 21 10 - 22 ... 16 - 28 ... 64 - 88. Ну так и я то же самое написала в предыдущем посте. Греко-латинский квадрат - это и есть эквивалент ортогональной пары ЛК. От меня ускользает смысл "9 туров перемешивания" |
||
Вернуться к началу | ||
Andy |
|
|
Nataly-Mak
Туры - это рассадки участников за восемью столами. За каждым столом располагаются восемь участников. За девять туров каждый из 64 участников встретится с каждым из остальных 63 участников. Как я понимаю, нужно восемь различных ортогональных латинских квадратов порядка 8 для туров №№ 2-9. Восемь - потому что в туре № 1 встречаются участники, принадлежащие к одной "восьмёрке" |
||
Вернуться к началу | ||
Nataly-Mak |
|
|
8 разных греко-латинских квадратов + первый (из номеров в естественном порядке)???
|
||
Вернуться к началу | ||
На страницу 1, 2, 3, 4 След. | [ Сообщений: 34 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Сколькими способами можно составить расписание
в форуме Теория вероятностей |
3 |
256 |
22 янв 2021, 20:41 |
|
Сколькими способами можно составить расписание
в форуме Теория вероятностей |
2 |
209 |
22 окт 2022, 12:43 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |