Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: ЛК и расписание
СообщениеДобавлено: 24 дек 2016, 09:20 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Здравствуйте! Если Вам это не очень трудно, сообщите, пожалуйста, можно ли использовать латинские квадраты для решения такой задачи: "Дано: 64 человека. 8 столов по 8 мест. 9 туров (перемешиваний). Задача: за 9 туров перемешать людей за столами так, чтобы каждый в итоге встретился с каждым и не встретился ни с кем повторно. То есть, чтобы каждый раз за столом были люди, который до этого не встречались за одним столом"? Эта задача встретилась в одном из вопросов на форуме, в котором я участвую.

В своё время, когда я судил соревнования по шахматам, я читал про математические основы составления расписаний соревнований. Насколько я помню, при изучении расписаний турниров по схевенингенской системе встретился с упоминанием латинских квадратов. Если я правильно понимаю, то предложенную задачу можно рассматривать как обобщение задачи о составлении расписания турнира по схевенингенской системе на случай, когда в турнире участвует больше двух команд. Условие, что участники не должны оказаться за одним столом повторно, как я понимаю, сильно усложняет эту задачу. Можно ли утверждать, что задача имеет решение?

P. S. Нашёл интересный материал о латинских квадратах здесь.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Andy "Спасибо" сказали:
Nataly-Mak
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 09:40 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Andy
спасибо большое за интересные задачи, связанные с латинскими квадратами.
Наверное, первая задача решается с помощью латинских квадратов 8-го порядка. Но сильно не думала.

А вот про расписание шахматных турниров - так тут однозначно используются латинские квадраты и даже ортогональные латинские квадраты.
По данной вами ссылке видим на рис. 73 латинский квадрат 6-го порядка, а на рис. 74 - ортогональные латинские квадраты 4-го порядка и соответствующее им расписание.
Весьма интересное применение ортогональных латинских квадратов!

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Nataly-Mak "Спасибо" сказали:
Andy
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 09:47 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
А можете ли Вы с Вашим знанием латинских квадратов однозначно утверждать, что сформулированная задача имеет решение или наоборот?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:01 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Andy
вы про рассаживание 8 человек за 8 столами?
А это аналогично расписанию шахматного турнира? Вот как приведено на рис.74 по данной вами ссылке.
Если аналогично, тогда задача однозначно имеет решение.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:03 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Это не совсем аналогично, как я понимаю. Впрочем, я попробую сам поэкспериментировать с латинскими квадратами восьмого порядка.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:09 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Andy
А почему не совсем аналогично?
Я вот как-то не совсем понимаю эту задачу с рассаживанием 8 человек за 8 столами.
Если рассаживать их так, как шахматистов рассаживают играть партии (см. рис 74), тогда и здесь так же точно рассадим. По ортогональной паре латинских квадратов 8-го порядка.
А таких пар известно множество, выбирайте любую. Могу дать ссылку на мою статью с такими ортогональными ЛК.

Если же эти задачи не совсем аналогичные, тогда я не совсем понимаю суть первой задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:28 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Давайте абстрагируемся от шахмат.

Пронумеруем всех участников числами от 1 до 64 и разделим их на "восьмёрки" - группы по восемь человек в каждой. Нужно выполнить девять перемешиваний (туров). Пусть в первом туре за одним столом встретились участники одной восьмёрки, то есть за первым столом встретились участники с номерами 1-8, за вторым столом - участники с номерами 9-16, ..., за восьмым столом - участники с номерами 57-64.

Теперь рассмотрим остальные восемь туров (со второго по девятый). В каждом из восьми туров нужно свести за одним столом восемь участников так, чтобы никто из них не встретился дважды (учитывая и первый тур).

Я понимаю так, что можно использовать греко-латинский квадрат. Перенумеруем участников, присвоив им двузначные номера по следующей схеме:
старый номер - новый номер
1 - 11
2 - 12
...
8 - 18
9 - 21
10 - 22
...
16 - 28
...
64 - 88.

Как по-Вашему?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:38 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
Andy писал(а):
Я понимаю так, что можно использовать греко-латинский квадрат. Перенумеруем участников, присвоив им двузначные номера по следующей схеме:
старый номер - новый номер
1 - 11
2 - 12
...
8 - 18
9 - 21
10 - 22
...
16 - 28
...
64 - 88.

Ну так и я то же самое написала в предыдущем посте.
Греко-латинский квадрат - это и есть эквивалент ортогональной пары ЛК.

От меня ускользает смысл "9 туров перемешивания" :blush:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:43 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Туры - это рассадки участников за восемью столами. За каждым столом располагаются восемь участников. За девять туров каждый из 64 участников встретится с каждым из остальных 63 участников.

Как я понимаю, нужно восемь различных ортогональных латинских квадратов порядка 8 для туров №№ 2-9. Восемь - потому что в туре № 1 встречаются участники, принадлежащие к одной "восьмёрке"

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 24 дек 2016, 10:45 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7006
Откуда: Саратов
Cпасибо сказано: 783
Спасибо получено:
583 раз в 507 сообщениях
Очков репутации: -237

Добавить очки репутацииУменьшить очки репутации
8 разных греко-латинских квадратов + первый (из номеров в естественном порядке)???

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3, 4  След.  Страница 1 из 4 [ Сообщений: 34 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Сколькими способами можно составить расписание

в форуме Теория вероятностей

k1n5

3

256

22 янв 2021, 20:41

Сколькими способами можно составить расписание

в форуме Теория вероятностей

_svrvsvrv

2

209

22 окт 2022, 12:43


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved