Поблагодарили
Страниц: [1] 2 3 ... 7
1  Задачи и головоломки / Математические задачи / Re: Найдите максимальное N : Август 06, 2013, 20:33:28
Прочтите ещё раз решение iPhonograph и вникните в него.
Даю подсказки.
Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д.
Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая.
Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать.
1-е взвешивание:
2К-1 монета на одной чашке и столько же на другой.
В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты.
В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д.
То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто.
По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д.
iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).

Эти пользователи сказали вам СПАСИБО :

☭-Изделие 20Д

За это сообщение 1 пользователь сказал спасибо!
2  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 24, 2013, 11:32:31
Итак приступим.
Сначала рассмотрим общий случай, когда цветов > 2, а затем отдельно случай с двумя цветами. Как ни странно, но он - сложнее Smiley
1. Введём некоторые термины:
а) ИЧЦ - Истинный/е Чётный/е Цвет/а - цвет/а тех колпаков, которых чётное кол-во. Напр. 6 синих, 8 жёлтых, 4 красных - это ичц
б) ИНЧ - истинный/е нечёт. цвет/а - понятно, думаю
в) ВЧЦ, ВНЧ - видимые чётные/нечётные цвета - цвета, видимые как чётные/нечётные в глазах мудрецов;
г) ИЧЧ - истинная чётность чётных цветов - общее число различных чётных цветов может быть чётным (ИЧЧ =0) и нечётным(ИЧЧ=1)
д) ВЧЧ - видимая Чётность чётных цветов - аналогично
е) ИКЧ(х) - истинная кратность чётных цветов по модулю х. ИКЧ(2) - это и есть ИЧЧ
ж) ВКЧ(х) - видимая кратность чётных цветов.

2. Начнём рассуждать.
Допустим у шаха 271 мудрец одетых в 38 цветов из которых 17 - чётные, а остальные 21 - нечётные, т.е. ИЧЧ = 1.
Что видят мудрецы, одетые в истинно чётные цвета? Они видят 16 чётных цветов, а свой и все нечётные они видят как нечётные и их (в их глазах - 22). То есть ВЧЧ(для чётных)=0.
Что видят мудрецы, одетые в истинно нечётные цвета? 18 чётных и 20 нечётных (надеюсь - ясно). То есть ВЧЧ(для нечётных)=0.
Аналогично, если бы шах использовал не 17 чётных цветов, а 18, то ИЧЧ=0, a ВЧЧ(для чётных)=ВЧЧ(для нечётных)=1
Надеюсь, пока понятно - мудрецы видят как бы консистентно наоборот Smiley
3. Казалось бы - тупик, ведь пока всё для них как бы одинаково.
4. Но у этого тупика есть выход Smiley - использовать кратность > 2, в нашем случае - 4.
Естественно для ВКЧ(4) у нас будут 4 значения - 0,1,2 и 3 (остатки по модулю 4 попросту говоря)
Рассмотрим случай с 38 цветами, из которых 17 - чётных.
ВКЧ(4)(для чётных) равно 0 (они видят 16 чётных, 16 на 4 делится без остатка)
А ВКЧ(4)(для нечётных) равно 2 (они видят 18 чётных, 18%4 даёт 2)
Аналогично, если бы шах использовал не 17 чётных цветов, а 18, 
то ВКЧ(4)(для чётных) = 1, а ВКЧ(4)(для нечётных) = 3 (в чём легко убедиться)
И вот на этом можно сыграть.
Сначала рассмотрим "тупую" стратегию, а потом поймём, что её можно даже улучшить. Хоть и тупая тоже неплохая.
5. Тупая стратегия.
5.1 В первую минуту встают те мудрецы, для которых ВКЧ(4)=0. В случае с 17 чётными встанут те, кто видит 16 чётных, в случае с 18 чётными - никто не встанет, в случае с 19 чётными - встанут те, кто видит 20, в случае с 20 чётными - никто не встанет. Во вторую минуту (ели в первую никто не встал) - с ВКЧ(4)=1 и т.д.
5.2. Сконцентрируемся сначала на случае 17, т.е. в первую минуту встанут те, кто видят 16.
Что они увидят среди вставших?
Каждый увидит 16 групп "чётных" мудрецов и ещё откуда-то затесавшуюся группу "нечётных" Smiley Вот на них и будут колпаки его цвета. Надеюсь, объяснять почему - не надо.
5.3. Рассмотрим случай с 19 чётными. В этом случае на первой минуте втанут те, кто видят 20 чётных.
И что они увидят? Каждый увидит, что из этих 20 чётных остался лишь одна группа. И вот цвет этой группы - и есть его цвет.
5.4. Я не буду объяснять, что остальные (не вставшие тоже без труда определят свой цвет.

6. Теперь давайте "причешем" нашу "тупую" стратегию.
Поскольку все мудрецы видят либо чёт, либо нечёт, то на первой минуте могут вставать мудрецы с ВКЧ(4)=0 и 1 - путаницы не будет. А на второй - ВКЧ(4)=2 и 3.
На первый взгляд напрашивается  более радикальный вывод - вообще вставание всегда произойдёт на первой минуте - встанут либо чётные, либо нечётные. И в подавляющем б-ве случаев это действительно так.
Но вернёмся к случаю с 19 чётными. Как я говорил, в этом случае встанут нечётные (те, кто видит 20). Это - верно.
Но если всего 19 цветов и все - чётные? То есть в первую минуту таки должны встать нечётные - но их по-просту не будет Smiley Это надо учесть Smiley Но ничего кардинально это не меняет.

7. У нас остался случай с двумя цветами. Надеюсь вы сами догадаетесь почему в некоторых ситуациях этот случай не впишется в нашу стратегию. Поэтому для этого случая следует применить стратегию BIVES для двух цветов или вообще - любую стратегию с искусственной сортировкой относительно назначенного в качестве "печки" мудреца.

Уффф... Вот, пожалуй и всё

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
3  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 11:57:18
Как я понимаю, часы в условии задачи остаются.
Если М>К, то на каждого из М-(M-K) распределяется "ответственность" за один из цветов (К). Из этих М через небольшой промежуток времени (допустим, 1 мин.) встают те, кто видит четное число колпаков с "вмененным" ему цветом. При этом за это время каждый из всех М подсчитывает цвета колпаков его коллег. Поэтому, когда встают "ответственные" М (если соблюдается условие, чтобы встать) каждый понимает, какого цвета на нем колпак. Если по истечении этого времени никто из "ответственных" М не встал, значит нет четности наблюдаемых им цветов. И в этом случае тоже каждый М понимает какого цвета на нем колпак.
Вот этот пост. Ответственные мудрецы и временные цвета меня запутали вконец Smiley
Я так понимаю, вставать не уходя нельзя - это жестикуляция.
К тому же, при предварительном сговоре мудрецы еще без колпаков.

И вот, допустим, я ответственный мудрец (вдвойне смелое допущение) вижу четность вмененного мне цвета, время подошло - мне вставать? Если вставать, то какой цвет говорить?
Это - решение предложенное Питером Пеном и оно мне понравилось.
Итак, есть М мудрецов и К<М цветов. К мудрецам поручено следить каждому за одним из К цветов и встать в первую минуту, если он видит чётное кол-во колпаков порученного ему цвета.
Вас интересует, как этот ответственный  мудрец узнает - а какой же на нём самом цвет.
Отвечаю.
1. Он знает всех К-1 ответственных мудрецов, цвета колпаков на них и цвета, за которые они ответственны.
2. Это значит, что он знает, что если на мудреце М1 колпак цвета Х а он ответственен за цвет У, то если он видит истинное кол-во колпаков цвета У, а если на мудреце М2 колпак цвета Ц и он ответственен за цвет Ц, то вместо чёта он видит нечёт и наоборот.
3. Таким образом наш ответственный мудрец, обозрев положение К-1 ответственного мудреца (встал или сидит) и цвет его колпака знает истинную чётность этих К-1 цветов.
4. Он её сравнивает с чётностью этих цветов, которую он видит. И если найдётся цвет, видимая чётность которого отличается от истинной (а таких цветов может быть не более 1-го) - то это цвет его колпака.
5. Если же ни один из К-1 цветов не имеет видимой чётности, отличной от истинной, это значит, что цвет, за которым наблюдает наш ответственный мудрец - и есть цвет его колпака.
6. Для не ответственных мудрецов - ещё проще - они судят по всем К цветам.

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
4  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 21, 2013, 06:40:38
Неужели никому не интересно решить
Как я понимаю, часы в условии задачи остаются.
Если М>К, то на каждого из М-(M-K) распределяется "ответственность" за один из цветов (К). Из этих М через небольшой промежуток времени (допустим, 1 мин.) встают те, кто видит четное число колпаков с "вмененным" ему цветом. При этом за это время каждый из всех М подсчитывает цвета колпаков его коллег. Поэтому, когда встают "ответственные" М (если соблюдается условие, чтобы встать) каждый понимает, какого цвета на нем колпак. Если по истечении этого времени никто из "ответственных" М не встал, значит нет четности наблюдаемых им цветов. И в этом случае тоже каждый М понимает какого цвета на нем колпак.
Гм... Пропустил этот ответ. За полемикой о сальфеджио - не заметил. Пардон.
Да, это сработает. Поздравляю.
Теперь позвольте усложнить условие задачи.
Шах пригласил 1000 мудрецов и сказал, что на них наденут колпаки 450 цветов. Но сами цвета им пока неизвестны. Как быть в этом случае?

Эти пользователи сказали вам СПАСИБО :

Питер Пен

За это сообщение 1 пользователь сказал спасибо!
5  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 19, 2013, 04:23:50
Итак, приступим.
Сначала, возвращаясь к варианту Питера Пена, хочу заметить - что насчёт начала минуты и конца минуты - я пошутил (там смайлик). И не потому, что это невозможно, а потому, что если это возможно (а это безусловно возможно), то и обычный подход можно разбить на полуминутные интервалы. Короче - это всего лишь масштабирование времени - не более того.
Теперь, наконец, об альтернативном варианте.
Он построен на трюке Smiley
Допустим, у нас 1000 мудрецов и всего два цвета - синий и красный.
Мудрецы договариваются: те, кто видят чётное число синих - идут отвечать.
Обратите внимание - идут отвечать - это не значит, что они знают свой цвет Smiley
Тем не менее, если шах действительно надел на мудрецов чётное кол-во синих колпаков, то это будут видеть только красные - они пойдут, и увидя на выходящих коллегах красные колпаки - поймут, какой на них (т.е. красный)
Если же шах надел нечётное кол-во синих колпаков - выйдут синие и поймут, что они синие.
Эту идею можно расширить на любое кол-во цветов. Это - нетривиально, но даёт сумасшедший эффект по скорости!
Даю ещё некоторое время на идеи Smiley
------------------------------------
Питеру Пену - Мудрецы конечно - люди умные, но Вы не задумывались, почему у симфонического оркестра есть дирижёр?

Эти пользователи сказали вам СПАСИБО :

Питер Пен, Лев

За это сообщение 2 пользователи сказал спасибо!
6  Задачи и головоломки / Математические задачи / Re: Перевязанная накрепко коробка с биекциями, изоморфизмами и т.п. : Июль 15, 2013, 13:08:28
Какой может быть максимальный объем у коробки в форме прямоугольного параллелепипеда, которая перевязана веревкой 648 см (без учета сгибов и узлов): один раз - вдоль, и два раза – поперек?  
По любому не более 71794.13 куб.см - Показать скрытый текст
Но шар ведь будет трижды перевязываться по большой окружности Smiley
А это - далеко не то же самое...

Эти пользователи сказали вам СПАСИБО :

slaydev

За это сообщение 1 пользователь сказал спасибо!
7  Задачи и головоломки / Математические задачи / Ещё раз о мудрецах : Июль 14, 2013, 23:11:49
Задачу придумал сам - навеяло. Является по сути компиляцией нескольких задач Smiley
У Шаха М мудрецов и он решил узнать насколько они умны.
Он собрал их и показал им образцы колпаков К разных цветов (К<М).
Он сказал что каждому мудрецу будет надет колпак с одним из этих К цветов, каждый мудрец будет видеть колпаки других.
Будут использованы все цвета.
Все мудрецы будут сидеть в одном зале и смотреть друг на друга. Ни говорить, ни жестикулировать нельзя.
Те, из мудрецов, которые готовы назвать свой цвет, могут молча выйти из Зала и назвать свои цвета Шахине, которая зафиксирует ответ. А Шах будет сидеть в зале и засечёт время по Главным часам шахства, которые тоже в зале и видны всем.
Часы - обычные цифровые часы с часами и минутами.
Мудрецам предлагается посовещаться между собой некоторое время, после чего процедура начнётся и пойдёт отсчёт времени.
Смогут ли мудрецы определить цвет своего колпака?
Соображают они очень и очень быстро.

Эти пользователи сказали вам СПАСИБО :

Лев, Робинзон

За это сообщение 2 пользователи сказал спасибо!
8  Задачи и головоломки / Математические задачи / Re: Вход только для умных! : Июль 13, 2013, 05:12:18
2 - Полицейский(П) и Гангстер (Г).
Решение нудное - получается система 3 уравнений.
Опишу только подход.
Пусть Х отношение скоростей П:Г
Сначала П отходит от центра на максимальное расстояние У такое, что если с этой точки он будет бегать по окружности, то сделает круг быстрее, чем Г обежит квадрат. Это значит, что он может добиться того,что Г будет в углу, а П приблизится к нему по диагонали на У.
Это даёт 1-е уравнение: 2Пи*У*Х = 4
Далее - ещё нуднее. Этот отрезок (от У до угла) надо разбить на 2 части - Т, где П будет идти по диагонали и К, где параллельно стороне.
Чтобы не мурыжиться, надо рассмореть проекцию отрезка диагонали от У до угла на сторону квадрата и вместо Т оперировать Т' которую П проходит со скоростью Х/корень(2)
Получим ещё два нудных уравнения из которых в конце концов получим Х - то минимальное отношение, когда П достигнет Г.

Эти пользователи сказали вам СПАСИБО :

artem123, Smith

За это сообщение 2 пользователи сказал спасибо!
9  Задачи и головоломки / Математические задачи / Re: Теннис : Июль 12, 2013, 21:22:22
Продолжение.
1. Начнём с простейшего - турнир 2-х. Требуется один результат по любому.
2. Турнир из 3-х. Будем считать, что у всех - разное кол-во очков, т.е. 0,1,2 (случай когда одинаковое рассм. отдельно):
    3! = 6, log26 > 2, т.е. требуется 3 результата (т.е. все), как ни крути. Тоже никакой экономии.
2а. Если у всех одинаковое число очков, то требуется 1 рез-т, любой и по нему восстановятся остальные. Это частный случай, конечно, но можно догадаться, что максимум рез-тов требуется, когда у всех - разные очки - от 0 до К-1.
3. Турнир 4-х. Все рез-ты разные - 0,1,2,3. Всего таблица (треугольная) будет иметь (К-1)*К/2 = 6 клеток.
4!=24>4, т.е. требуется 5 бит/рез-тов из 6. Экономия - всего 1 бит. Итак, какой рез-т можно не спрашивать?
Пусть участники - А,Б,В,Г
Я бы запросил: А-Б, А-В, Б-В, Б-Г, В-Г, оставив за бортом рез-т А-Г.
Если мы получили 00000, то порядок ГВБА и рез-т А-Г - 0 (А проиграл). Иначе можно убедится, что не все набрали разные очки.
Если же рез-т 11111, то порядок АБВГ и А выиграл у Г.
Аналогично можно высказаться о каждой комбинации 5 бит. Кстати, не все 32 комбинации релевантны при условии, что у всех разное кол-во очков.
Перебирать все 32 комбинации, выделять из них 24 и определять рез-т А-Г я не буду - муторно
Как видите, уже для 4-х участников выбрать 5 из 6 рез-тов - это работа более чем нудная.
Например, запросить рез-ты А-Б,А-В,А-Г, Б-В,Б-Г и опустить - В-Г было бы неверным (если у всех разное кол-во очков), поскольку результат В-Г - существенен.
Другими словами уже для 4-х участников редакции нужен комп и программа, чтоб отбросила 1 из 6 рез-тов.
А я описал лишь случай, когда все набрали разное кол-во очков...
Для 5: всего - 5*4/2=10, 5!=120>64, т.е. нужно 7 рез-тов из 10.
Для 6: 6*5/2=15, 6!=720>512-> 9.
Ну, для 16 - 16*15/2=120, 16!>244 -> 45.
Но чтоб выбрать 45 из 120 я думаю требуется неслабая программа и нехилый комп...

Эти пользователи сказали вам СПАСИБО :

Питер Пен, Tim

За это сообщение 2 пользователи сказал спасибо!
10  Задачи и головоломки / Математические задачи / Re: Теннис : Июль 12, 2013, 02:41:31
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Чтож, давайте попробуем.
1. Итак, у редакции есть итоговая таблица по которой можно понять, сколько побед у первого места, сколько у второго и т.д.
2. У журналиста - вся инфа, но он хочет её как-то сжать, зная, чем располагает редакция.
3. Естественно, редакция умная и догадается об алгоритме сжатия Smiley
4. Теперь - сама стратегия.
4.1 Сначала журналист перечислит все победы последнего игрока (назовём его - Вася)  в порядке снизу вверх. Побед будет немного, раз он последний. Остальные - будут поражения и их редакция сразу пометит. Назовём это число побед - Х.
4.2 Затем перейдём предпоследнему игроку. Надо учесть, что если он выиграл у последнего, эта победа уже будет фигурировать и для него потребуется перечислить на одну победу меньше. И так далее.
Это - в целом стратегия. Обратите внимание, что у меня таблица получается задом наперёд.
Если же передавать не победы, а поражения, то таблица бы была бы в привычном порядке.

4.4. Давайте оценим максимальное Х. Это тогда, когда у всех примерно очков/побед поровну и фиг их знает, почему наш Вася - последний.
Итак, всего имеется 16*15/2 = 120 встреч, т.е. 120 побед т.е. 7.5 побед на брата. Т.е. для Васи - это 7 побед где-то. При этом 8 побед он как бы "отдаёт" бесплатно - их передавать не надо.
То есть из общего числа побед 8 можно вычесть.
Обратите внимание - мы заполнили не более половины строки, но это эквивалентно всей строке.
4.5 Перейдём к следующей строке (предпоследнему игроку). Её длина на один меньше (мы помним что таблица представляет собой треугольник и она у нас задом наперёд). Очевидно и для неё потребуется заполнить только где-то меньше половины - и то, в худшем случае)
Короче, для каждой строки требуется где-то К/2 -1, что и даёт 45... Первого игрока вообще перечислять не надо.
Конечно, это не претендует на строгость, но подход имхо вырисовался.

Эти пользователи сказали вам СПАСИБО :

Питер Пен, Tim

За это сообщение 2 пользователи сказал спасибо!
11  Задачи и головоломки / Математические задачи / Re: Иван и Кащей - сдвиг : Июль 11, 2013, 23:56:15
Сдвиг всех чисел на одну позицию изменяет всю сумму на 101, на две - 202 и т.д.
Совершенно очевидно, что какая бы не была сумма, можно числа сдвинуть так, что новая сумма будет положительна и меньше 101. Назовём её С1. Если С1 <= 50 то задача - решена.
Если же С1 > 50, сделаем сдвиг влево ещё на 1. Получится сумма С2 = С1 - 101, которая будет отрицательной, но её абсолютная в-на будет 101 - С1. Поскольку С1 > 50, то 101 - С1 не будет уже больше 50 Smiley

Эти пользователи сказали вам СПАСИБО :

fortpost

За это сообщение 1 пользователь сказал спасибо!
12  Задачи и головоломки / Математические задачи / Re: Двое сильнейших : Октябрь 28, 2012, 22:49:40
Это - для одного мало, нужно 24.
Для двух - 27
Не, побольше.
Ну, значит, 28...
Для определения сильнейшего из К требуется К-1 встреча.
Для 2-го - log2K - 1
Естественно, с округлением в сторону ближайшего не меньшего целого...

Эти пользователи сказали вам СПАСИБО :

fortpost

За это сообщение 1 пользователь сказал спасибо!
13  Задачи и головоломки / Математические задачи / Re: Бесплатный сыр... : Февраль 20, 2012, 08:08:02
Лучше имхо последовательность: 145897632

Эти пользователи сказали вам СПАСИБО :

fortpost

За это сообщение 1 пользователь сказал спасибо!
14  Задачи и головоломки / Математические задачи / Re: Ёлкино-Палкино дубль два : Февраль 02, 2012, 01:56:43
Показать скрытый текст

Эти пользователи сказали вам СПАСИБО :

Seamew

За это сообщение 1 пользователь сказал спасибо!
15  Задачи и головоломки / Математические задачи / Re: Минимальная длина дорог : Декабрь 21, 2011, 14:35:30
Ребята, если бы было бы так просто, разве я задал бы эту задачу?
Есть более компактный вариант... Smiley

Эти пользователи сказали вам СПАСИБО :

bazarsen

За это сообщение 1 пользователь сказал спасибо!
Страниц: [1] 2 3 ... 7