|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
| Хайдук: Юрик, почему называем сумму двоек ПОЛУинвариантом? |
Я вроде бы объяснил. Инвариант преобразований - это величина, которая при этих преобразованиях не меняется. Мы же ищем величину, которая меняется, но контролируемо - в данном случае возрастает. Такие величины называются полуинвариантами. |
|
|
| номер сообщения: 49-2-3597 |
|
|
|
|
Thanks  |
|
|
| номер сообщения: 49-2-3598 |
|
|
|
|
| номер сообщения: 49-2-3599 |
|
|
|
|
Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал.
Еще немного подумал про задачу Игоря - там оценка, кажется, может быть улучшена до n^{1/2} ln n, но как-то сложно получается. |
|
|
| номер сообщения: 49-2-3617 |
|
|
|
|
| iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал. |
Я честно думал о задаче некоторое время, но в голову лезли только глупые мысли. Потом уехал на конференцию и совсем забыл о бедных заключенных. |
|
|
| номер сообщения: 49-2-3618 |
|
|
|
|
| iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал. |
У Кванта смешную задачку эту как-будто давно решили на ветке Математика для чайников  |
|
|
| номер сообщения: 49-2-3620 |
|
|
|
|
iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал.
Еще немного подумал про задачу Игоря - там оценка, кажется, может быть улучшена до n^{1/2} ln n, но как-то сложно получается. |
Ну, это серьезное улучшение, просто оно и не могло получится. А как, если не секрет?
П.С. извиняюсь, что не принимаю участие. Просто не хватает ни времени, ни сил.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3626 |
|
|
|
|
Игорь: iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал.
Еще немного подумал про задачу Игоря - там оценка, кажется, может быть улучшена до n^{1/2} ln n, но как-то сложно получается. |
Ну, это серьезное улучшение, просто оно и не могло получится. А как, если не секрет? |
Я не до конца продумал, но как-то так. Ваша оценка дает Х log N, где Х - размер меньшей кучки, N - общее количество монет. Теперь смотрим на алгоритм внимательно - мы начинаем с тройки (X, kX-s, mX-p), которая переходит в тройку (Х-s, 2^q X, Z).
Наблюдение 1: k мало по сравнению с Х, иначе kX имеет порядок Х^2, а значит Х = N^{1/2}, читд.
Наблюдение 2: s должно быть мало по сравнению с Х, иначе мы очень быстро спускаемся.
Наблюдение 3: 2^q приблизительно равно k, так что 2^q X = 2^q (X - s) + 2^q s = 2^q(Х - s) + ks. Опять же, ks должно давать большой остаток по модулю X-s, иначе мы быстро опускаемся на следующем шаге, а значит ks сравнимо с Х.
Таким образом, общее число монет имеет порядок kX, спуск осуществляется не за Х, а за Х/s шагов и общая скорость алгоритма Х/s log N = N/(ks) log N = N/X log N. Меньшее из чисел X log N и N/X log N имеет порядок N^{1/2} log N.
Я проехал пару деталей, как минимум. Например, на втором шаге Z может оказаться меньше, чем 2^q X, и нам надо будет интересоваться остатком Z при делении на X-s. Но это вроде бы нестрашно, так как монетки из третьей кучки можно поперекидывать во вторую, пока они примерно не сравняются, а тогда видно, что оба остатка должны быть большие.
Довольно расплывчато, но сил доводить до конца нет. |
|
|
| номер сообщения: 49-2-3631 |
|
|
|
|
MikhailK: | iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал. |
Я честно думал о задаче некоторое время, но в голову лезли только глупые мысли. Потом уехал на конференцию и совсем забыл о бедных заключенных. |
Давайте я ответ подскажу, что ли - может, заинтригую. Итак: вероятность спастись - 1. |
|
|
| номер сообщения: 49-2-3632 |
|
|
|
|
| Игорь: Просто не хватает ни времени, ни сил. |
Чем тусуемсо, если не секрет? |
|
|
| номер сообщения: 49-2-3633 |
|
|
|
|
iourique: MikhailK: | iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал. |
Я честно думал о задаче некоторое время, но в голову лезли только глупые мысли. Потом уехал на конференцию и совсем забыл о бедных заключенных. |
Давайте я ответ подскажу, что ли - может, заинтригую. Итак: вероятность спастись - 1. |
Если Вы -1 имели в виду, то я намек понял 
На самом деле как раз вспоминал о свойствах перестановок, я думаю есть не одно подходяшее, но Вами подсказанное не оставляет сомнений.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3634 |
|
|
|
|
Хайдук: | Игорь: Просто не хватает ни времени, ни сил. |
Чем тусуемсо, если не секрет? |
Работаем. Время иногда бывает, а сил совсем нет.
__________________________
ИМХО |
|
|
| номер сообщения: 49-2-3635 |
|
|
|
|
Возненавидел думать и потому намерен спросить у Дорона Зейлбергера не найдётся ли у него решения задачки про библиотекаря в общем случае, когда можно ставить на место любую книгу  |
|
|
| номер сообщения: 49-2-3636 |
|
|
|
|
| Не подскажет ли кто-нибудь формулу для объёма сегмента шара, вырезанного двумя перпендикулярными плоскостями? А то у меня что-то интегралы с ходу не берутся... |
|
|
| номер сообщения: 49-2-3637 |
|
|
|
|
| Roger: Не подскажет ли кто-нибудь формулу для объёма сегмента шара, вырезанного двумя перпендикулярными плоскостями? А то у меня что-то интегралы с ходу не берутся... |
В Бронштейне-Семендяеве есть только сектор, сегмент и слой, они там высекают параллельными плоскостями... А как проходит вторая плоскость? Скажем, первая отсекает от шара шляпку, а вторая делит эту шлапку на два куска перпендикулярно основанию? |
|
|
| номер сообщения: 49-2-3638 |
|
|
|
|
| Ну да, типа плоскости взаимно-перпендикулярны. |
|
|
| номер сообщения: 49-2-3639 |
|
|
|
|
| номер сообщения: 49-2-3640 |
|
|
|
|
Thanks 
Сегодня сравню с численным интегралом. |
|
|
| номер сообщения: 49-2-3641 |
|
|
|
|
jenya:
В Бронштейне-Семендяеве .... |
У меня сохранился Бронштейн-Семендяев моего деда напечатанный на тончайшей бумаге (издание 53 года). Любопытно было его в школе листать. Многое было непонятно, но жутко интересно.
Несколько лет назад видел на полках в магазине новое издание, так оно раза в два больше моего из-за разной толщины бумаги. |
|
|
| номер сообщения: 49-2-3642 |
|
|
|
|
iourique: MikhailK: | iourique: Чего-то народ совсем перестал обсуждать - я тут такую смешную задачу подкидывал и хоть бы слово кто сказал. |
Я честно думал о задаче некоторое время, но в голову лезли только глупые мысли. Потом уехал на конференцию и совсем забыл о бедных заключенных. |
Давайте я ответ подскажу, что ли - может, заинтригую. Итак: вероятность спастись - 1. |
Ура, я свободен! Я решил эту задачу наконец.
| iourique: В тюрьме сидит 100 заключенных. В один прекрасный день им объявляют, что сегодня вечером, после того, как их разведут по их одиночным камерам, им выдадут по два колпака, белый и черный, а завтра с утра они должны будут надеть один из колпаков, после чего их выведут на плац и расставят в шеренгу в уже определенном начальником тюрьмы порядке. Если окажется, что цвета колпаков строго чередуются (б-ч-б-ч-.. или ч-б-ч-б...), их всех отпустят. Одновременно с раздачей колпаков каждому из них расскажут, в каком порядке будут расставлены все остальные, но не сообщат его место в шеренге. До заката у заключенных есть время посовещаться и выработать общую стратегию. Какой она должна быть? |
Думаю, что можно уже озвучить решение. Мудрецам следует выбрать какую-нибудь расстановку на плацу. Обозначим её через P. Когда мудрец узнаёт расстановку остальных, то ему следует поставить себя в самое начало этой расстановки и посчитать четность перестановки по отношению к расстановке P. В зависимости от четности и следует выбирать колпак.
Самое обидное, что до фиксирования некоторой произвольной расстановки и о том, что цвет колпака должен зависень от четности какой-то перестановки я сразу догадался, но никак не мог придумать применение этому. |
|
|
| номер сообщения: 49-2-3643 |
|
|
|
|
Михаил, а проверили решения у Кванта? Я не в курсе, но там вроде давно разобрались  |
|
|
| номер сообщения: 49-2-3644 |
|
|
|
|
А чего их проверять? Сами разберутся - не маленькие, чай.
Меня в задачке очень порадовал контраст между ощущением безнадежности, возникающим с первого взгляда, и простотой решения. |
|
|
| номер сообщения: 49-2-3645 |
|
|
|
|
| Хайдук: Михаил, а проверили решения у Кванта? Я не в курсе, но там вроде давно разобрались |
Про тамошнее решение я слышал, но ссылку-то ведь никто не дал.
Мне подкинули школьных олимпиадных задачек. Меня заинтересовала одна. Условие опубликую тут после 10 октября, когда истечёт срок подачи решений. |
|
|
| номер сообщения: 49-2-3646 |
|
|
|
|
iourique: А чего их проверять? Сами разберутся - не маленькие, чай.
Меня в задачке очень порадовал контраст между ощущением безнадежности, возникающим с первого взгляда, и простотой решения. |
Ага, будь я тем мудрецом, не выжил бы.
| iourique:В один прекрасный день им объявляют, что сегодня вечером, после того, как их разведут по их одиночным камерам, им выдадут по два колпака, белый и черный, а завтра с утра |
Мне понадобилось больше месяца, а мудрецы должны были управиться за несколько часов. |
|
|
| номер сообщения: 49-2-3647 |
|
|
|
|
| А я ещё даже и не начинал. |
|
|
| номер сообщения: 49-2-3648 |
|
|
|
|
| Roger: А я ещё даже и не начинал. |
Ой, тогда очень извиняюсь, что раскрыл решение. |
|
|
| номер сообщения: 49-2-3649 |
|
|
|
|
Еще задачка с того же сайта. Эта выглядит чистым безумием, у меня никаких идей, как ее решать. Вкратце:
А и В получают по подмножеству чисел от 1 до n. Им надо установить, пересекаются ли их подмножества. Они могут обменяться конечным (не зависящим от n) количеством информации, плюс у них есть доступ к компьютеру. Компьютер умеет делать одну единственную вещь - получив некоторую перестановку чисел от 1 до n от А и от В, он вычисляет их композицию и возвращает 1, если она состоит из одного цикла, и 0 в обратном случае. Причем делает это компьютер один-единственный раз, после чего выключается. Смогут ли А и В составить протокол, гарантирующий им успех? |
|
|
| номер сообщения: 49-2-3650 |
|
|
|
|
MikhailK: jenya:
В Бронштейне-Семендяеве .... |
У меня сохранился Бронштейн-Семендяев моего деда напечатанный на тончайшей бумаге (издание 53 года). Любопытно было его в школе листать. Многое было непонятно, но жутко интересно.
Несколько лет назад видел на полках в магазине новое издание, так оно раза в два больше моего из-за разной толщины бумаги. |
Собственно, теща моего тестя была замужем за Семендяевым, они прожили вместе последние лет сорок. |
|
|
| номер сообщения: 49-2-3651 |
|
|
|
|
iourique: Еще задачка с того же сайта. Эта выглядит чистым безумием, у меня никаких идей, как ее решать. Вкратце:
А и В получают по подмножеству чисел от 1 до n. Им надо установить, пересекаются ли их подмножества. Они могут обменяться конечным (не зависящим от n) количеством информации, плюс у них есть доступ к компьютеру. Компьютер умеет делать одну единственную вещь - получив некоторую перестановку чисел от 1 до n от А и от В, он вычисляет их композицию и возвращает 1, если она состоит из одного цикла, и 0 в обратном случае. Причем делает это компьютер один-единственный раз, после чего выключается. Смогут ли А и В составить протокол, гарантирующий им успех? |
Выглядит замечательно интересно. Может даже попробую порешать(я давно уже не в форме:-( ) |
|
|
| номер сообщения: 49-2-3652 |
|
|
|
|
Интересная, но трудная, задача!
Из теории чисел!
Выпишем значения sigma(n) (= сумма всех делителей n, включая 1 и n)
для неск. первых значений n
n:........1,2,3,4,5,.6,7,.8,.9,10,11,12,13,14,15,16,17,18,19,20,...
sigma(n):.1,3,4,7,6,12,8,15,13,18,12,28,14,24,24,31,18,39,20,42,...
(строгие) локальные минимумы sigma(n)
(то-есть sigma(n) < min(sigma(n-1),sigma(n+1)):
n:........5,7,.9,11,13,17,19,...
sigma(n): 6,8,13,12,14,18,20,...
Теперь, внимание, вопрос:
чему равно минимальное n, кратное 10,
такое, что sigma(n) < min(sigma(n-1),sigma(n+1))?
Подсказки:
1. Придумал задачу я сам (хотя кто знает, может, она известна?)!
2. Решение задачи я не знаю!
3. Простой перебор (brute force) ничего не даст!
4. Потом.........
Good luck & thanks,
Zak06
Ashkelon, Israel
__________________________
I love chess |
|
|
| номер сообщения: 49-2-3653 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2025 гг. |
|
|
|
