29.04.2017, 10:34 [+3 UTC]
в нашей команде: 1 926 чел. | участники онлайн: 6 (рекорд: 21)

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

:: консультации

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

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
28.04.2017, 08:08

Последний вопрос:
28.04.2017, 19:28

Последний ответ:
29.04.2017, 08:51

Последняя рассылка:
28.04.2017, 22:45

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

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

Наша кнопка:

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

Отзывы о нас:
26.07.2011, 08:11 »
PsySex
Спасибо, в следующий раз буду обязательно читать спецификацию, а не верить консультантам. [вопрос № 183809, ответ № 267955]
27.12.2010, 01:03 »
Дмитрий Олегович
И вновь качественный ответ! Большое спасибо! Очень рад что на форуме есть такие люди как вы! [вопрос № 181620, ответ № 265113]
30.11.2009, 15:29 »
Cimus
Действительно опечатался в адресах, благо Вы это подметили! Спасибо! [вопрос № 174703, ответ № 257113]

РАЗДЕЛ • Математика

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

[администратор рассылки: Лысков Игорь Витальевич (Старший модератор)]

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

Гордиенко Андрей Владимирович
Статус: Модератор
Рейтинг: 4203
Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 642
Megaloman
Статус: Академик
Рейтинг: 393

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

Консультация онлайн # 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 лет, а полтора года. Негатив этого в том, что теряется суть - "за минимум движений достичь максимального резульата".

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

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

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

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

-----
 Прикрепленный файл (кликните по картинке для увеличения):

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

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

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 секунд на представление себя присутствующим за столом.
Но можно конечно и развивать эту идею, где за каждым столом будет определенное задание, которе нужно решить, и в такой игровой форме все познакомятся и каждый раз участник будет решать новую задачу за новым столом с новыми людьми.

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

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

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

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

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

ID: 17387

# 7

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

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

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

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

=====
Facta loquuntur.

• Отредактировал: Гордиенко Андрей Владимирович (Модератор)
• Дата редактирования: 20.12.2016, 14:11

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 человек. Прикрепляю рисунок.
Да и сам алгоритм не сложный...только вот много времени отнимает, возможно даже вечность :)

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

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

-----
 Прикрепленный файл (кликните по картинке для увеличения):

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

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

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:

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

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

=====
Facta loquuntur.

• Отредактировал: Гордиенко Андрей Владимирович (Модератор)
• Дата редактирования: 24.12.2016, 10:08

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

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.

 

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

Яндекс Rambler's Top100

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

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

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн