Есть N мышей, которые группами по K ходят на склад. Нужно определить, возможна ли для указанных N и K ситуация, когда все мыши посетили склад и при этом каждая виделась с каждой на складе строго по одному разу.

А это важно?

ТС нечем заняться, изобретает велосипеды)

(1) Учет мышей видимо складских требуют, это еще понять можно, вот зачем среди них выявлять социальные связи мне не понятно...

+(3) Спорю автор на фиксе сидит?

(4) В типе, времени свободного докуя?

(4) да ты психолог ))
задачки просто интересные нравятся

n = 3 k = 2

(6)Отдай ребенку учебник по математике, а сам возвращайся к работе!

Комбинаторика и теория вероятностей. Читайте-с =)

(7) при K=2 вообще то N любое может быть
(8) я же Ненавижу 1С

при К>=3 уже не может такого быть

(11) ваши доказательства?

(3) предполагается мышей заразить Т-вирусом. В результате, они все передохнут, просто встретившись друг с другом

мЫши на склад не ходют, они там живут;-)

(11) при K=3, N=7

n = 3 k = 2
N = 7 K = 3
Можно ли сделать вывод, что N = 2^K - 1?

(16) нет конечно, очевидно уже неверно при K=4

на самом деле мне известны только необходимые критерии, но они не являются достаточными

Если мыши-крысы посещают склад, то такой склад явно нуждается в доработке.
P.S. кто знает, как поймать крысу, которая в мышеловки не попадает ?

Всего посмотрят друг на друга k(k-1)/2 пар мышей в каждом походе.
В итоге должны посмотреть друг на друга n(n-1)/2 пар.
Из чего следует что k(k-1) должно быть делителем n(n-1)
Это необходимое условие, остается доказать что достаточное.

(20) верно, кроме того необходимо: (k-1) делитель (n-1).
Но вот этого увы недостаточно.

(21) А это из чего вытекает?

(22) выделим некоторую мышь, в каждом походе она встречается c (k-1) мышью причем разными всегда, всего ей надо встретиться с (n-1) мышью.

Да, точно.

Случайно нашел сайт в котором онлайн можно решать олимпиадные задачи. Странно что я раньше о нем не знал.
codeforces.ru Условия на русском.
Проводят около шести чемпионатов в месяц в каждой из двух лиг.

(21) А этих двух условий достаточно?

в том то и дело, что нет
только что вывел еще одно 2*(n-k) делится на (k-1)
но все равно не отсеиваются контрпример, а именно:
n=36, k=6
n=43, k=7

Разве n=36 k=6 - нет решения?

(27) если (n-1) делится на (k-1) то  учтя что n-k = (n-1)-(k-1), n-k тоже делится на k-1. Следовательно (27) лишнее

(28) сам теперь сомневаюсь
(29) так и знал, что ничего не даст, увы

(31) "Собрали 100 смертников. Сказали - мы по одному человеку будем выводить во двор на прогулку, вы будете в одиночных камерах и кого выводят вы не увидите. Выводить будут в произвольном порядке, т.е. одного могут вывести 10 раз, другого 1 раз. И так будет продолжаться до бесконечности. Но выводить будут всех. Во дворе есть выключатель, его можно только включить или выключить. Если кто-то из вас скажет в этом дворе выходили на прогулку все 100 смертников, и это будет правда - вас всех отпустят, иначе вас всех казнят. И оставили их посовещатся. Вопрос - о чем должны договориться смертники чтобы выйти на свободу?"

Если изобразить нарисовать матрицу встреч (аля турнир на N мышей c играми по K мышей), то каждая встреча заполняет k(k-1) квадратиков из n(n-1). В принципе, заполнять их мы можем в произвольном порядке не нарушая условий. Так что вышеуказанных условий достаточно.

(34) Хотя не, туплю.. ) не достаточно.

(33) Зачётная задачка! Уже ломаю голову)

(36) >>одного могут вывести 10 раз, другого 1 раз. И так будет продолжаться до бесконечности
надо понимать что процесс не прервётся, когда нибудь там каждый человек побывает и по 500 раз. задача в том чтобы один из узников сказал точно, что были все. Но за 10 лет его могут вывести 500 раз, а кого-то не выведут вобще.
От старости никто не умрёт считаем, время неважно

(31) о побеге?

(38) нет, сбежать нельзя, умереть от старости нельзя, 1000 лет подождать и сказать чо были все надеясь на то что они там были тоже нельзя, одного могут вывести первый раз только в 1001 году

Если положение выключателя видно из камеры (например что свет загорается) - то это не математическая задача.

(39) не выходить более одного раза и считать 100 дней

(40) ничего не видно. Это не совсем математика, это логика

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

логика (математическая логика) - раздел математики.

(39) Задача имеет решение?

(45) Задача имеет кучу решений, разных по среднему количеству дней до выхода. Есть научные работы по этой задаче :)

(45) имеет

В качетве подсказки - Выключатель во дворе не просто так, и вопрос в задаче - о чем должны договорится заключенные. Т.е. до начала процесса они вместе тусят и думают что делать

Мы целой группой в универе решали эту задачу 1,5 часа примерно...

(48) Решение этой задачи можно оптимизировать годами.
Только в условии не написано главное - выводят их в случайном порядке.

(49) "Выводить будут в произвольном порядке" - в (33) написано.

(50) В произвольном, и в случайном - это не одно и то же.

ТС решил математическим методом извести мышей?

(51) в данном контексте разницы не вижу. Считай что в случайном, если принципиально

решение завтра напишу, если не решат и тему не прикроют

решения может не быть, если некоторого выведут первым и притом единственный раз

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

(55) написано же - выведут обязательно всех. И процесс не прервётся никогда, в итоге каждый там побывает по многу многу раз

(56) уже горячо)

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

(57) не сказано этого было, что каждый потенциально будет выведен бесконечное число раз, но принимается

(59) разницу понял, но написано в произвольном и выведут ВСЕХ = случайно

(60) > (37), пояснил свой поток сознания

(61) В произвольном - для любого решения есть алгоритм вывода при котором не выйдут они (не просигнализируют) даже если были выведены все.

(63) ну вот тебе произвольный алгоритм, считай по нему выводят. всех пронумеровали и четных выводят по 5 раз, нечетных по 10 раз в течении года, а 99-го и 13-го выводят раз в 5 лет. Но они сами не знают этот алгоритм и должны договорится о том, как сказать точно что все были

(64) Не существует у этой задачи решения, которое позволит просигнализировать сразу, в тот-же момент когда всех вывели как минимум по одному разу. Поэтому чтоб решение существовало - должны выводить в случайном порядке.
Не существует решения этой задачи, которое позволит просигнализировать при любом алгоритме вывода заключенных.
Уж поверь мне, я эту задачу знаю.
Существует решение в котором среднее время до выхода конечно ПРИ СЛУЧАЙНОМ порядке вывода заключенных (и естественно которое никогда не сигнализирует ошибочно)

(65) есть решение, по которому один из заключенных будет знать, что как все 99 других были как минимум 1 раз там, это и надо доказать

(66) Нет такого решения. Могу спорить на деньги.

(67) ты меня немного запутал случайными и произвольными.
Если ты согласен с (60), что каждый потенциально будет во дворе бесконечное число раз, то решение есть

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

Если ты знаешь решение, то сам подумай. Чтоб был сигнал - каждый должен побывать в строго определенные дни. В эти дни его просто выводить не будут, а будут выводить в другие.

Ну самый простой вариант это назначают ответственного он считает. остальные когда их выводят первый раз и если переключатель выключен включают его. ответственный в свой выход выключает переключатель и записывает+1 в тетрадочку. как будет 100 значит всех выводили.

(69) вот, как раз для этого решение есть.
Т.е. я могу гарантировать, что 1 из них будет знать что во дворе были все 99 других заключенных.
выключатель не забыл во дворе? на нём основано решение. Я чот думаю может ты спутал с другой задачей немного, без выключателя? тогда да, решения нет

(71) Молодец, возьми с полки пирожок и денег у NS
:)
Надо назначить главного, который будет считать состояние выключателя. без этой договорённости задачку не решить

(72) Нет решения.

выбрали 1 человека, остальные должны хотя бы 1 раз зайти по двор при выключеном выключателе и включить его, если выключатель включен они его не трогают, только тот которого выбрали может выключать, как тока он 99 раз выключит...WIN

вот решение

(74) опровергни (71), правильно

(75) опоздал)

(73) как можно считать состояния? ведь их всего же 2. пока главный сидел другие могли выйди тыщу раз

(72) Хм. Если бесконечно - то действительно есть решение.

(79) эх затупил

(79) > (71)(75).
Только один избранный выключает, остальные только включают и только 1 раз. Так мы точно узнаем сколько Разных человек там было

Если есть слово случайно в формулировке - то просто есть другое решение. Нумеруем узников с нуля по 99. Нумеруем дни по-порядку, если кто-либо заходит в день когда остаток от деления номера дня на 100 равен его номеру, то включает, иначе выключает. Каждый записывает в какие дни по модулю 100 при его выходе выключатель бы включен, и как только наберется 99 разных дней, то сигнализирует.

Но при таком алгоритме - есть алгоритм вывода когда сигнала не будет.

(83) вариантов задачи много, тут ключевое видимо - каждый там будет потенциально бесконечное число раз, при любом алгоритме их вывода решение есть 100%, так что неважно случайно или произвольно.
Задачу решал 5 лет назад, так что по памяти вспоминал условия, но вроде через 20 постов после оглашения задачи все условия были восстановлены точно, по уточняющим вопросам

(85) Оптимальное решение в разных случаях разное.
Если случайное, то близко к оптимальному (83), а при (71) выйдут в среднем заметно позже.
Если не случайное, но каждого выведут бесконечно - то (83) в отличии от (71) не гарантирует выход вообще.

(86) ну если от старости не умрёшь - я лучше подожду лишнюю тысячу лет, чем меня с другими подельниками казнят :)

(87) Ошибочного сигнала не будет в любом случае. В обоих алгоритмах. Так что не казнят.

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

(89) решение в (71)(75), правильное. была бы уборщица - сказано бы было, выходят во двор, выключатель во дворе. Логично что они могут его юзать)

а еще мыши на складе гадят, поэтому если склад удалённый то лучше посчитать вес экскрементов вне склада иначе склад откопать рвом с водой.

(33) Можно рычаг выключателя не полностью перевести. Скажем, на 1%?
И как вообще выключатель действует на заключенных (свет виден, сирена раздается....)

(33) Что означает условие "Но выводить будут всех"? Что каждого выведут минимум один раз? Или же что при времени, стремящемся к бесконечности, количество прогулок у каждого заключенного будет стремиться к бесконечности?
Если верный первый вариант, то решение в (71) не гарантирует того, что "главный" сможет когда-либо сказать, что все уже прогуливались, - даже на бесконечном временном промежутке (так как его могут вывести ВСЕГО один раз, - ДО того, как все успеют прогуляться по разу). Если верно второе - то свобода гарантируется, хотя бы на бесконечном временном интервале.

(90) Из чего следует что они могут его юзать и не получают при этом дулом под лопатку, а отказаться от прогулки не могут?

А ответьте на 92 пожалуйста

(92) Нет конечно.

(0) - всё промотал))))))))
По теме - знал я одну "мышь" которая в "Магнит" работала. Эта вполне "human like mouse" п..ла вещи типа "кассеты для бритв Mach 5" - и я их покупал, и я у этой "мыши" на квартире видел огроменные коробки с этими кассетами)))))))))
До сих пор запасами 5 летней давности пользуюсь, веришь?

(0) N = K(K-1)+1 = K^2-K+1 = (K^3+1)/(K+1)
для любого K >= 3.
N меньшее невозможно из-за делимости N(N-1) на K(K-1)
Готов привести пример построения для не слишком большого K (обобщать построение слишком муторно).
Невозможность большего тоже могу показать на конкретном примере

(98) Меньше? Например N=K

Невозможность большего?
N=2^1000000000000, К=2.

(99) вырожденные варианты не рассматриваю
(100) при K=2 N-любое, согласен

(101) Что может помешать при K>2?
Например любому значению удовлетворяющему (20)и(21)?

Допустим n=t*k*(k-1)+1, при сколько угодно большом t

(102) Пример K=3 N=13  
всего пар - N(N-1)/2=78
групп по 3 должно быть 78/3=26
Берем первую мышь - она входит в (N-1)/(K-1) = 6 групп при этом любая другая мышь поучаствовала в них по разу.
Возьмем вторую и третью мышь(выбираем их так, что они попали одну из групп с первой - т.е. одна из групп 1-2-3). На каждую из них добавляется по 5 групп, при этом остальные мыши (4-7) поучаствуют еще по 2 раза каждая.
Имеем 16 выбранных групп, мыши 1-3 в дальнейших выборах не участвуют. Необходимо набрать еще 10 групп из оставшихся 4 мышей, причем каждая должна попасть в 3 группы, да так, каждая пара из них может попасть только в одну группу - невозможно

+ (104) Общий смысл, что число возможных выборов(с учетом ограничения на единственное вхождение каждой пары в группу) растет медленнее чем число необходимых групп с ростом N. А при N=K(K-1) эти числа совпадают

(105) Да, не выходит.

Похоже это правильное решение.

нарики...

Фиксеров много.

+(98)для K>2 есть похоже ещё вторая серия N=K^2, есть примеры для K=3 и K=4, и схема построения. Если будет время завтра попробую нарисовать пример для 6 36.
в (104) накосячил с цифрами, но вывод для данного примера все равно правильный

при n=k