Просмотр сообщений
Страниц: [1] 2 3 ... 66
1  Задачи и головоломки / Математические задачи / Re: Вот лето пролетело и Ага! : Август 22, 2013, 21:58:29
В честь закрытия летнего сельского мото-сезона из двух пунктов А и Б одновременно навстречу друг другу стартуют два мотоциклиста и начинают курсировать между этими пунктами, доезжая до них и сразу же разворачиваясь назад. На их пути находятся 2 поста ДПС – один из них (ближайший к пункту Б) находится на расстоянии 50 км от пункта Б.
Первая встреча мотоциклистов произошла на расстоянии 110 км от пункта А, а вторая состоялась уже на расстоянии 170 км от пункта Б.
Какое расстояние между постами ДПС, если известно, что обоих мотоциклистов в одно и тоже время после их первоначального выезда из своих начальных пунктов остановили на ближайшем посту ДПС, задержав на одинаковое время для проверки документов?

//текст доступен после регистрации//

Без алгебры не получится Sad
Показать скрытый текст
2  Задачи и головоломки / Математические задачи / Re: Вставай на нано лыжи! : Август 17, 2013, 23:30:47
Они стартуют из одной точки?
Обогнать - значит обогнать на круг как минимум?
3  Задачи и головоломки / Математические задачи / Re: Найдите максимальное N : Август 09, 2013, 06:14:15
buka
а васне смущает вот это условие?
Цитировать
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний
Нет, не смущает.
Итак, в общем случае: нам надо найти максимальное N монет, среди которых одна фальшивая, причём весы ломаются после Х взвешиваний где неравенство и за не более чем К взвешиваний.
То есть, нам надо найти N как функцию Х и К (у Вас - Х=3,K=7)
Если Х = 1, то N(X,K) = N(1,K) = 2K+1. С этим, думаю, ясно.
Если Х = 2, то N(X,K) = N(2,K) = 2*(N(1,K-1)+N(1,K-2)+...+N(1,2)+31
Если Х = 3, то N(X,K) = N(3,K) = 2*(N(2,K-1)+N(2,K-2)+...+N(2,3))+32
Рекурсивно:
N(X,K) = 2*(N(X-1,K-1)+N(X-1,K-2)+...+N(X-1,X))+3X-1
4  Задачи и головоломки / Математические задачи / 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 привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).
5  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Август 01, 2013, 01:14:33
Если с этим решением Вам ясно, то давайте продолжим.
Усложним задачу ещё немного - уберём шахиню.
У каждого мудреца - пульт (напр. К кнопок разных цветов), куда он вносит ответ, процесс введения ответа (и сам ответ) никому не виден.
После введения ответа мудрец встаёт и уходит.
Короче, трюк со вставанием здесь не проходит.
Итак у нас пока есть две стратегии:
а) традиционная (как в задаче с мудрецами с неверными жёмами)
б) Питера Пена (когда время для первого цвета удваивается зато затем всё очень быстро) - http://nazva.net/forum/in....msg223918.html#msg223918
Ясно, что в одних случаях быстрее будет с а), а в других - с б)
Вопрос такой: зная К и (естественно, М), могут ли мудрецы:
1) выбрать стратегию с более коротким матожиданием времени полного угадывания;
2) выбрать критерий выбора стратегии "на месте", то есть, когда каждый видит колпаки других?
6  Задачи и головоломки / Математические задачи / Re: Остров хамелеонов : Июль 28, 2013, 19:10:10
Трансакции не изменяют кратность суммы по модулю 3. Это и есть инвариант...
7  Задачи и головоломки / Математические задачи / 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 для двух цветов или вообще - любую стратегию с искусственной сортировкой относительно назначенного в качестве "печки" мудреца.

Уффф... Вот, пожалуй и всё
8  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 17:05:08
Если не будет возражений, завтра выложу решение в общем виде.
9  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 13:44:33
Пусть всего 3 цвета и нет цвета который одет только на одного мудреца.
Делаем так: выходят те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.

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

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

На счет нуля не понял в чем проблема ?
Если у вышедших - колпаки двух цветов, то у них уже нет возможности свести задачу к задаче с двумя цветами. У них нет ещё одной системы отсчёта времени.
Насчёт нуля - нет никакой проблемы. Я думал, что может это Вам как-то поможет. Но можете проигнорировать эту реплику, если это Вам не важно.
10  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 12:08:04
Пусть всего 2 цвета и нет цвета который одет только на одного мудреца.
Делаем так: идут отвечать те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.
Если вышло четное число мудрецов, то на первом мудреце колпак такого цвета, как и на вышедших и он идет отвечать с ними.
Если вышло нечетное число мудрецов, то на первом мудреце колпак такого цвета, как на тех, которые остались.

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

И вот, допустим, я ответственный мудрец (вдвойне смелое допущение) вижу четность вмененного мне цвета, время подошло - мне вставать? Если вставать, то какой цвет говорить?
Это - решение предложенное Питером Пеном и оно мне понравилось.
Итак, есть М мудрецов и К<М цветов. К мудрецам поручено следить каждому за одним из К цветов и встать в первую минуту, если он видит чётное кол-во колпаков порученного ему цвета.
Вас интересует, как этот ответственный  мудрец узнает - а какой же на нём самом цвет.
Отвечаю.
1. Он знает всех К-1 ответственных мудрецов, цвета колпаков на них и цвета, за которые они ответственны.
2. Это значит, что он знает, что если на мудреце М1 колпак цвета Х а он ответственен за цвет У, то если он видит истинное кол-во колпаков цвета У, а если на мудреце М2 колпак цвета Ц и он ответственен за цвет Ц, то вместо чёта он видит нечёт и наоборот.
3. Таким образом наш ответственный мудрец, обозрев положение К-1 ответственного мудреца (встал или сидит) и цвет его колпака знает истинную чётность этих К-1 цветов.
4. Он её сравнивает с чётностью этих цветов, которую он видит. И если найдётся цвет, видимая чётность которого отличается от истинной (а таких цветов может быть не более 1-го) - то это цвет его колпака.
5. Если же ни один из К-1 цветов не имеет видимой чётности, отличной от истинной, это значит, что цвет, за которым наблюдает наш ответственный мудрец - и есть цвет его колпака.
6. Для не ответственных мудрецов - ещё проще - они судят по всем К цветам.
12  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 06:02:47
Что-то не очень устраивает меня пока мое решение. Buka, скажите, а при вашем способе решения возможно ли рассмотреть вариант с 40 М и больше чем 20 цветами - даже, допустим, имеется палитра из 100 разных цветов и на всех 40 М будут какие-либо 40 цветов из 100?
Да, Питер Пен. Если, конечно, я сам не ошибаюсь Smiley
Ведь задачу придумал я сам. И когда излагал условие, то последний вариант у меня в голове ещё не был Smiley
13  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 06:00:09
Господа, простите за скудоумие, объясните подробней решение с использованием "принципа четности" для 7 цветов и 100 мудрецов, а то мне все кажется, что имеет место "жестикуляция" - видимо что-то не дошло  Undecided
Что именно Вы имеете в виду? Просто дайте ссылку на постинг.
14  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 22, 2013, 00:52:21
Всё ОК, но и я тоже должен понять, что Вы имеете в виду.
Если 1000 и 450 - это просто большие числа (трудно себе представить зал, где "кружком" расположились 1000 человек) и пр. рассмотрите вариант с 40 мудрецами и 15 цветами.
15  Задачи и головоломки / Математические задачи / Re: Ещё раз о мудрецах : Июль 21, 2013, 19:40:35
Да, и что?
Возьмите М и К и проверьте для 1000 и 450...
Число цветов - число точное, т.е. мудрецам точно известно сколько цветов.
Страниц: [1] 2 3 ... 66