27.11.2020, 02:33 [+3 UTC]
в нашей команде: 4 892 чел. | участники онлайн: 1 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
8.0.2-PB2
26.11.2020

Общие новости:
09.10.2020, 16:55

Форум:
26.11.2020, 17:11

Последний вопрос:
26.11.2020, 22:09
Всего: 153373

Последний ответ:
26.11.2020, 18:38
Всего: 260689

Последняя рассылка:
26.11.2020, 17:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
20.12.2017, 12:15 »
goldssky@yandex.ru
Подробно. Все понятно. Вопросов нет. Спасибо. [вопрос № 192167, ответ № 275879]
21.09.2009, 11:13 »
Хиноцкий Ярослав Владимирович
Обязательно рассмотрю ваши ссылки, низкий Вам поклон. Спасибо! [вопрос № 172400, ответ № 254443]
 

Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)

 
 

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 2038
Алексеев Владимир Николаевич
Статус: Мастер-Эксперт
Рейтинг: 1737
Konstantin Shvetski
Статус: Мастер-Эксперт
Рейтинг: 593
 

Перейти к консультации №:
 

Консультация онлайн # 190315
Раздел: • Математика
Автор вопроса: lukas (1-й класс)
Дата: 19.12.2016, 16:56
Поступило ответов: 1

Добрый день, уважаемые эксперты!

Прошу помочь в решении следующей задачи.

Дано: 64 человека. 8 столов по 8 мест. 9 туров (перемешиваний).
Задача: за 9 туров перемешать людей за столами так, чтобы каждый в итоге встретился с каждым и не встретился ни с кем повторно. То есть, чтобы каждый раз за столом были люди, который до этого не встречались за одним столом.

Спасибо за ответы или советы в поиске решения этой задачи!

Дмитрий.

Состояние: Консультация закрыта

Здравствуйте, lukas!

Благодарю Вас за интересную задачу! Она развеяла мою скуку, вызванную типовыми задачами, которые я решаю на портале за нерадивых студентов.

Я связался с автором этого ресурса и воспользовался её любезным предложением попробовать применить систему ортогональных латинских квадратов восьмого порядка.



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


Консультировал: Гордиенко Андрей Владимирович (Специалист)
Дата отправки: 24.12.2016, 15:10

5
Спасибо огромное!!
-----
Дата оценки: 24.12.2016, 19:07

Рейтинг ответа:

+1

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 190315

Гордиенко Андрей Владимирович

Специалист

ID: 17387

1

= общий = |  19.12.2016, 19:10 |  цитировать |  профиль |  личное сообщение
lukas:

Вы знакомы с таблицами шахматных и шашечных турниров по круговой системе?

=====
Facta loquuntur.

Асмик Гаряка

Советник

ID: 230118

2

= общий = |  19.12.2016, 23:51 |  цитировать |  профиль |  личное сообщение

В матчах встречаются по 2. Недавно у нас был турнир по свояку, где встречаются в игре 3 человека. Организаторы правильно не рассчитали, я делала расчеты на бумажке, подбором делается. Для данной задачи стоит написать программу. Вручную сложно будет.

Гордиенко Андрей Владимирович

Специалист

ID: 17387

3

= общий = |  20.12.2016, 06:48 |  цитировать |  профиль |  личное сообщение
Асмик Гаряка:


Вручную тоже можно, хотя и сложно. А вопрос про таблицы шахматных и шашечных турниров я задал, потому что их можно использовать для отображения расписания.

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

4

= общий = |  20.12.2016, 10:58 |  цитировать |  профиль |  личное сообщение

Цитата: Гордиенко Андрей Владимирович
Вы знакомы с таблицами шахматных и шашечных турниров по круговой системе?

Честно говоря, не знаком...но, подозреваю, что там по принципу 1 на 1.

Цитата: Асмик Гаряка
В матчах встречаются по 2. Недавно у нас был турнир по свояку, где встречаются в игре 3 человека. Организаторы правильно не рассчитали, я делала расчеты на бумажке, подбором делается.

Есть еще одна игра, где за столом встречаются по 4 человека и у них проблема перемешиваний тоже стоит остро. Но там проблема в большом количестве участников и множестве столов. По сути та же задача, только другие условия.

По поводу ручного перебора. Пробовал конечно. Для 16 (4 стола по 4 человека) или 25 (5 столов по 5 человек) это довольно просто, но при переходе на 36 уже понимаешь, что это будет не легко.

Цитата: Асмик Гаряка
Для данной задачи стоит написать программу. Вручную сложно будет.


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

Находил как то упрощение задачи, где предлагалось за каждым столом оставлять двух постоянных людей и, таким образом, менять за столами не по 8 человек а всего по 6. Это упрощает немного ручной перебор и программу, вычисления которой займут, условно говоря, не 10 лет, а полтора года. Негатив этого в том, что теряется суть - "за минимум движений достичь максимального резульата".

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

Буду благодарен за любые советы, которые могут решить или хотя бы упростить задачу.

В любом случае, спасибо большое за внимание!

-----
Прикрепленное изображение (кликните по картинке для увеличения):

Последнее редактирование 20.12.2016, 11:02 lukas (1-й класс)

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

5

= общий = |  20.12.2016, 11:11 |  цитировать |  профиль |  личное сообщение
lukas:

Меня интересовало, знаете ли Вы, как эти таблицы заполняются. В принципе, однако, это несущественно...

Мне интересно, зачем Вам нужно решение этой задачи и откуда она взялась. Хочется знать, на что пойдут умственные и временнЫе ресурсы, потраченные, например, мной на решение этой задачи.

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

6

 +1 
 
= общий = |  20.12.2016, 11:54 |  цитировать |  профиль |  личное сообщение
Гордиенко Андрей Владимирович:

Андрей Владимирович,

Спасибо за внимание к моему вопросу!

Задача возникла из следующего:
Хотелось в такой форме провести "знакомства" людей, которые собираются в лагере (отдыха), празднике, конференции или любом другом мероприятии, где важно чтобы в самом начале все друг с другом познакомились и имели предстваление кто присутствует и имели возможность представить себе всем. Отсюда и возникла такая идея, где в достаточно интересной форме (по сравнению с простым представлением каждого человека по отдельности) и, что очень важно, быстрой, "перезнакомить" всех со всеми. На пример за один час, таким образом по 6-7 минут на тур и у каждого человека будет 30-45 секунд на представление себя присутствующим за столом.
Но можно конечно и развивать эту идею, где за каждым столом будет определенное задание, которе нужно решить, и в такой игровой форме все познакомятся и каждый раз участник будет решать новую задачу за новым столом с новыми людьми.

Делать со столами можно будет все что угодно (на что фантазии хватит). Рассадить бы их....

Еще раз спасибо!

Последнее редактирование 20.12.2016, 12:03 lukas (1-й класс)

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

7

= общий = |  20.12.2016, 14:10 |  цитировать |  профиль |  личное сообщение
lukas:

Наверное, правильно начать рассмотрение Вашей задачи с ответа на вопрос: "Существует ли решение задачи?" и только при положительном ответе на этот вопрос начать поиски этого решения (возможно, одного из многих). Однако, мои знания в комбинаторике и навыки их применения не позволяют сделать это. Поэтому остаётся действовать интуитивно.

Но может быть, удастся осуществить и этот подход, связанный с понятием фактор-множества. Вопрос в том, сколько времени на это уйдёт и не проще ли всё-таки действовать интуитивно.

А интуитивно мне уже не нравится, что столов восемь, а туров девять.

Последнее редактирование 20.12.2016, 14:11 Гордиенко Андрей Владимирович (Специалист)

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

8

= общий = |  20.12.2016, 15:45 |  цитировать |  профиль |  личное сообщение

Цитата: Гордиенко Андрей Владимирович
"Существует ли решение задачи?"

Решение конечно же есть, теоритически оно даже кажется простым...но вот на практике не получется...

Цитата: Гордиенко Андрей Владимирович
А интуитивно мне уже не нравится, что столов восемь, а туров девять.

Восемь столов взято как максимум. Даже восемь столов не в каждое помещение можно поставить удобно. 8 людей тоже как максимум людей за одним столом. 10, на пример, уже многовато, как ме кажетя. 9 туров же как минимальное их количество для того чтобы встретится со всеми 63 людьми (9 раз по 7 человек).

Можно конечно попробовать на 49 человек (7 столов, по 7 человек и 8 туров).
Или не одинаковое количетсво людей за столами, но тогда мне кажется сложнее проследить со всеми ли встрелится.

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

9

= общий = |  20.12.2016, 15:54 |  цитировать |  профиль |  личное сообщение
lukas:

Почему Вы уверены, что решение задачи в данной постановке существует? Я не утверждаю, что его нет, но уверенности в обратном у меня тоже нет (извините за каламбур).

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

10

= общий = |  20.12.2016, 16:00 |  цитировать |  профиль |  личное сообщение

Цитата: Гордиенко Андрей Владимирович
Почему Вы уверены, что решение задачи в данной постановке существует?

Чисто теоретически ведь не сложно представить что можно таким образом людей рассадит. Тем более, что есть решения для меньшего количсетва. На пример для 16 человек. Прикрепляю рисунок.
Да и сам алгоритм не сложный...только вот много времени отнимает, возможно даже вечность :)

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

-----
Прикрепленное изображение (кликните по картинке для увеличения):

Последнее редактирование 20.12.2016, 16:01 lukas (1-й класс)

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

11

 +1 
 
= общий = |  20.12.2016, 16:05 |  цитировать |  профиль |  личное сообщение
lukas:

Как раз (во всяком случае, мне) сложно теоретически обосновать существование решения у этой задачи. Но об этом я уже писал...

В общем, моё подсознание уже подключилось к решению задачи. Если появятся желаемые результаты, то я Вам сообщу.

=====
Facta loquuntur.

Гордиенко Андрей Владимирович

Специалист

ID: 17387

12

= общий = |  23.12.2016, 21:08 |  цитировать |  профиль |  личное сообщение
lukas:

Пока ничего более продуктивного по сравнению с тем, что применили Вы при решении задачи с 16 участниками, я найти не смог. Исписав с десяток листов бумаги и составив шесть больших таблиц, я остановился в итоге на Вашем способе. Если будут силы, то попробую использовать его завтра. Получается, что если эта задача имеет решение (а интуиция подсказывает, что это так), то его нужно искать перебором. Формально нужное для решения задачи время увеличивается не более чем в раз. smile Но это моя верхняя оценка дилетанта...

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

13

= общий = |  23.12.2016, 22:32 |  цитировать |  профиль |  личное сообщение
Гордиенко Андрей Владимирович:

Спасибо еще раз за внимание!

Я тоже все еще думаю над решением, и, возможно, нашел "ключ". Что-то вроде продолжения моей схемы.

1) Делаем произвольно первую рассадку. И в конце каждому участнику за одним столом присваиваем одинаковый цвет.
2) Следующую расскладку делаем так чтобы одинаковые цевета не встречались за столом. И в конце каждому участнику за одним столом присваиваем одинаковый номер.
3) Следующую расскладку делаем так чтобы одинаковые цевета и идинаковые номера не встречались за столом. И в конце каждому участнику за одним столом присваиваем букву.
4) Следующую расскладку делаем так чтобы одинаковые цевета, идинаковые номера и одинаковые бувкы не встречались за столом. И в конце каждому участнику за одним столом присваиваем фигуру.
5) Следующую расскладку делаем так чтобы одинаковые цевета, идинаковые номера, одинаковые бувкы и одинаковык фигуры не встречались за столом...И так далее.

То есть каждый раз присваивать новый критерий каждому столу в новом туре. И, таким образом, на следующий тур, нужно сравнивать ни весь массив уже встречавшихся учатников для каждого нового за столом, а сравнивать по критерию - есть ла за столом желтый, круглый, с буквой "а" и т.п.
Это, как мне кажется упрощает ручной перебор (из-за графического разнообразия критериев) и программы, где критерии могут буть просто a,b,c...(a1,a2,....c1,c2,c3....).

Что скажете?...

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

14

= общий = |  23.12.2016, 22:40 |  цитировать |  профиль |  личное сообщение
lukas:

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

К сожалению, я не интересуюсь информационными технологиями и программированием, поэтому написать код не могу... smile

=====
Facta loquuntur.

Гордиенко Андрей Владимирович

Специалист

ID: 17387

15

= общий = |  24.12.2016, 09:17 |  цитировать |  профиль |  личное сообщение
lukas:

Рекомендую Вам это как информацию к размышлению. В своё время мне довелось читать этот материал, но за давностью лет вспомнилось только теперь.

И ещё: Ортогональные латинские квадраты.

Последнее редактирование 24.12.2016, 10:08 Гордиенко Андрей Владимирович (Специалист)

=====
Facta loquuntur.

Гордиенко Андрей Владимирович

Специалист

ID: 17387

16

= общий = |  24.12.2016, 14:46 |  цитировать |  профиль |  личное сообщение
lukas:


Используя предложенную Вам информацию об ортогональных латинских квадратах, я составил расписание, которое Вы можете увидеть здесь.

=====
Facta loquuntur.

lukas

1-й класс

ID: 400803

17

 +1 
 
= общий = |  24.12.2016, 19:09 |  цитировать |  профиль |  личное сообщение
Гордиенко Андрей Владимирович:

Андрей Владимирович,
Спасибо большое за Ваше время и за помощь!
Наконец-то я могу спасть спокойно :)

Едиственное, там была маленькая опечатка в 4м туре, но я быстро понял что там должно быть (прикрепляю скришот).

smile smile smile

-----
Прикрепленное изображение (кликните по картинке для увеличения):

=====
The more you know
The less you need to show

Гордиенко Андрей Владимирович

Специалист

ID: 17387

18

= общий = |  24.12.2016, 19:12 |  цитировать |  профиль |  личное сообщение
lukas:

Спасибо и Вам за интересную задачу! Извините, пожалуйста, за ошибку. С кем не бывает. smile Надеюсь, Вы поняли, что можно получить ещё несколько расписаний для Вашего случая.

=====
Facta loquuntur.

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.


главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.21012 сек.

2001-2020, Портал RFPRO.RU
Калашников О.А.  |  Гладенюк А.Г.
8.0.2-PB2    26.11.2020
JS 2.0.10 | CSS 4.0.8