knop: (qr)
Я тут подумал и сделал ссылочную страничку. Пользуйтесь на здоровье.
(Учтите, что условия задач приведены в кратком виде, для чтения полных условий нужно перейти по ссылке на "Элементы")
По просьбе читателей убрано под кат )
knop: (qr)
Очередное моё творчество для "Элементов".
http://elementy.ru/problems/1093
На сей раз в качестве задачи выбран сюжет 10.8 из Всероса этого года (авторы - Илья Богданов и Сергей Берлов), хотя доказательство оптимальности я написал по-другому. В "Послесловии" показаны еще две задачки, в которых оптимальность алгоритма доказывается тем же методом - рассмотрением Соперника, который играет против произвольного алгоритма.

Если вы знаете еще какие-нибудь нетривиальные задачи, в решении которых появляется Adversary/Соперник, - напишите, пожалуйста.
knop: (qr)
Три игрока - A, B и C - играют в такую игру: каждый из них независимо от остальных выбирает натуральное число от 1 до 6. Затем все числа оглашаются, и выигрывает в раунде назвавший наименьшее уникальное число. (Например, если двое назвали 1, а третий назвал 4, то он и выиграет).

Игра проводится 1000 раундов, и победителем объявляется тот, кто выиграл больше всего раундов.

Какова оптимальная стратегия для А (ну, и для B), если C перед началом игры объявил, что в каждом раунде будет бросать кубик для определения собственного числа (и на самом деле ровно так и играл)?

Комменты в ЖЖ скрыты на несколько дней. Те, кто увидят эту задачу в ВК, FB или Twi, приглашаются в ЖЖ ;-)
knop: (qr)
Я задумал трёхзначное число, являющееся точным квадратом.
Наименьшую его цифру я сказал на ухо Андрею, наибольшую - на ухо Боре, а третью сказал им обоим вслух.
После этого Андрей сказал, что все равно не знает, какую цифру я сообщил Боре, а Боря - что не знает цифру Андрея.
Какое число я задумал? (В математических способностях Андрея и Бори сомневаться не нужно).

Комменты скрыты
knop: (qr)
Рано утром из сёл Галкино и Воронино одновременно друг навстречу другу вышли две старушки. Они встретились ровно в полдень, но не остановились, а продолжили движение каждая со своей прежней скоростью. Первая старушка пришла в Воронино в 16:00, а вторая старушка в Галкино — в 21:00. Во сколько старушки отправились в путь?

(Это из сегодняшней "Контрольной" на Яндексе. Контрольная уже закончилась, так что я думаю, что ничего не нарушаю, рассекретив условие)

"Яндекс" приводит алгебраическое решение - в несколько уравнений и несколько абзацев.
Я знаю намного более простое, так сказать, "идейное". Хотя по существу, несомненно, то же самое.
Подумайте, может быть, и вы его придумаете. Оно интересное.

Комменты скрыты, как обычно в задачах. Раскрою через 2-3 дня
P.S. 17.03 - раскрыл, читайте. Я имел в виду геометрическое решение, с графиком движения и подобием треугольников.
knop: (qr)
Я пишу сейчас нечто по ТЧ. Там есть цикл задач про фи-функцию Эйлера, и в нем - такая вот задачка: докажите, что равенство phi(n)=n/2 равносильно тому, что n - степень двойки.

К ней я знаю два разных решения. Первое - на основе того, что phi(n)=n * П (1-1/p),
где произведение берется по всем простым делителям n. Второе - на основе тождества Гаусса
n = SUM phi(d), где сумма берется по всем делителям n. (Это тождество нужно записать дважды - для n и для n/2, потом учесть условие phi(n)=n/2 и сравнить результаты.)

Какое решение оставить? Только первое? Только второе? Привести оба?
А может, вы знаете еще какое-то решение этой задачи?
knop: (qr)
...то при любом собеседовании на должности, требующие математических способностей хотя бы в минимальной степени, соискатели получали бы у меня следующую задачку.

Придумайте, как можно организовать такой фокус.
Помощник фокусника просит одного из зрителей написать на доске в ряд N цифр. Затем помощник фокусника стирает одну из них и покидает помещение. После этого появляется фокусник. Глядя на оставшиеся цифры, фокусник безошибочно отгадывает, какая цифра была стёрта.
(Фокусник и его помощник заранее выбирают число N так, как им удобно; фокусник видит, на каком месте стояла стёртая цифра. Любые способы скрытой коммуникации, кроме явно оговоренных в задаче, запрещены.)

Ну что, хотите рискнуть? Комменты скрыты.

8.12. Раскрываю все комменты.
knop: (qr)
Есть два тонкостенных цилиндрических стакана разного диаметра, оба вмещают 300 граммов. Один имеет высоту 27 см, другой - 12 см. Как с помощью этих стаканов отмерить ровно 200 г воды (вода есть из-под крана в неограниченном количестве)?

[Тонкостенность означает, что объемом стенок и дна стаканов можно пренебречь]
Комменты скрыты.

1.12. Раскрыл все комменты.
Моё исходное решение - с вставкой узкого сосуда в широкий и процессом переливаний, сводящимся к 5/9 + 5/9 - 1 + 5/9 = 6/9 = 2/3. В этом решении доливание происходит всегда до краёв.

Тем не менее, если разрешить доливать до уровня другого стакана и наклонять стаканы (делить содержимое пополам), то существуют и другие варианты. Например:
4/9 + (4/9 * 1/2) = 2/3

Впрочем, использование 4/9 позволяет получить нужное количество воды даже без деления пополам, хотя и существенно дольше:
4/9 + 4/9 + 4/9 - 1 = 3/9
3/9 + 4/9 + 4/9 - 1 = 2/9
2/9 + 4/9 = 6/9
knop: (qr)
Среди делителей четырёхзначного числа ABBA (черта над числом подразумевается; A<B) есть двузначные числа AA, BA и BB. Найти наибольшее такое возможное ABBA. PS. Решив задачу, вы легко сможете догадаться, какой постскриптум я поначалу собирался написать. условие исправлено уже два раза. Что-то туплю я с этим условием
knop: (qr)
См. в "Элементах".
http://elementy.ru/problems/861
Спасибо Тане Ховановой за сюжет и участие в содержательных обсуждениях.
knop: (qr)
Шестнадцать лет назад я написал для "Компьютерры" статью "Дети бармена", которая целиком была посвящена вариантам известной задачки http://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle
Поскольку давеча "Наука и жизнь" проехалась по той же задаче еще раз (http://www.nkj.ru/archive/articles/13630/), да еще и приписала ее изобретение Льву Ландау (что не может быть правдой, см. хронологию и библиографию в статье Википедии по ссылке выше), я хочу рассказать еще о двух версиях. Надеюсь, что оригинальных.

Итак, условие.

1. Посетитель зашел в бар, заказал выпивку и начал беседовать с барменом. Узнав, что у того четверо детей, он спросил:
- А сколько им лет?
(*) - Произведение их возрастов равно 180, - ответил бармен.
- Но этого недостаточно, чтобы определить их возраст! - немедленно воскликнул посетитель.
- Конечно, - с этими словами бармен наклонился к уху посетителя и добавил:
(*) - Сумма их возрастов равна числу стоек в моем баре.
Гость пересчитал глазами стойки, подумал минуту и объявил:
- Все равно информации недостаточно!
Улыбнувшись, бармен добавил:
- Мой cтарший младший сын очень любит клубничное мороженое.
- И этого еще недостаточно.
- У младшего старшего сегодня день рождения.
- Спасибо, теперь я все знаю, - поблагодарил посетитель.

Сколько лет каждому из детей?

2. Все то же самое, но вместо первой (*) бармен говорит:
- Сумма их возрастов равна 20 17. (Прим. КК с 20 - нет единственности решения)
а вместо второй
- Произведение их возрастов равно стоимости коктейля, который Вы сейчас заказали

P.S. Это разные задачи, и ответы у них тоже разные.
knop: (qr)


Комменты, наверное, скрывать не буду.

(1+x+x^2)^n

Jul. 9th, 2014 02:34 pm
knop: (qr)
Перебирал старые записи. Обнаружил задачку, которую решал на втором году службы в армии. Прикольная задача, между прочим.

Докажите, что при любом натуральном n коэффициент при x^{n-1} многочлена (1+x+x^2)^n делится (нацело) на n.

Комменты скрыты.
Любителям подсматривать в OEIS сразу могу кинуть ссылку: http://oeis.org/A005717 и попросить туда не подглядывать, пока не решите задачу сами.

a+b+c+d=239

Jul. 7th, 2014 10:45 am
knop: (qr)
Рассмотрим все четверки натуральных чисел (a,b,c,d) с суммой 239.
Докажите, что \Sum {abcd}, взятая по всем таким четверкам, кратна 239.

Комменты в ЖЖ скрываются
knop: (qr)
Прекрасная задачка, раньше не встречал.

Существует ли такое подмножество натуральных неотрицательных целых чисел Q, что любое целое неотрицательное число представимо единственным образом в виде a+2b, где a,b \in Q ?

Комменты в ЖЖ скрываются.

PS. Комменты открыты. Верных решений очень много, да никто и не говорил, что задача трудная.
knop: (qr)
Один из стандартных способов записи даты - "Д.М", то бишь дни и месяцы без ведущих нулей.
Например, "1.4" - первое апреля, "31.3" - тридцать первое марта.

Найдите такие a, b, c, что дата ab.c - это abc-й день невисокосного года (здесь abc - трехзначное число, а не произведение).

Задачка несложная, но комментарии несколько дней скрываются, чтобы желающие могли порешать
knop: (qr)
В корзине лежат 120 шариков трех цветов. Из корзины вытаскивают наугад три шарика. Известно, что вероятность появления трех шариков одинакового цвета равна вероятности появления трех разноцветных шариков. Сколько шариков каждого цвета лежит в корзине?

Комменты скрыты. Постарайтесь решить без использования выч.средств

17.04.2015 Раскрыл комментарии. К сожалению, полных решений так и нет.
knop: (qr)
Из картона вырезан трафарет в форме правильного 2014-угольника со стороной 1 см. Будем называть его 2014-трафаретом. Разрешены следующие геометрические построения:
а) приложить трафарет к листу бумаги так, чтобы несколько вершин трафарета совпали с ранее отмеченными на бумаге точками;
б) полностью или частично обвести приложенный к листу трафарет, отметив все полученные при этом вершины.
Докажите, что с помощью этих операций можно построить центр правильного 2014-угольника со стороной 1 см.

Комменты скрывать не буду. Задача не очень простая (10 и 11 кл. олимпиады ЮМШ этого года)
knop: (qr)
Игра в "метаграммы" или "цепочки слов" ("из МУХИ сделать СЛОНА, меняя несколько раз по одной букве") широко известна и, строго говоря, в наш компьютерный век уже давно неинтересна.

Я попытался придумать версию цепочек, для которой нужно использовать не компьютер, а мозги.
Два существительных могут быть соседними в цепочке, если существует прилагательное, образующее устойчивое словосочетание с каждым из них (род прилагательного при этом может измениться).
Например, "зуб" и "москвичка" могут быть соседними, так как существует прилагательное "коренной/коренная".

Необходимые пояснения.
1) Имена собственные разрешены.
2) Обратите внимание, что прилагательные в цепочку не входят, они как бы "между строк"!
3) Понятно, что "устойчивое словосочетание" - трудноформализуемое понятие, ибо устойчивость сродни "крылатости фразы" и "известности цитаты". Но тем не менее - старайтесь использовать такие словосочетания, в устойчивости которых никаких сомнений у носителей языка не будет.

Задачка 1. Постройте цепочку: книга - ? - коммунист

Задачка 2. Постройте цепочку: компания - ? - неделя

Задачка 3. Придумайте свои цепочки и загадайте их мне. Спасибо!

Один вопросительный знак означает одно пропущенное слово в цепочке (а не 0 и не 2). Комменты пока будут скрываться.
knop: (qr)
Среди 49 одинаковых на вид монет - 25 настоящих и 24 фальшивых. Для определения фальшивых монет имеется тестер. В него можно положить любое количество монет, и если среди этих монет больше половины фальшивых, то тестер подаёт сигнал. Как за пять тестов найти две фальшивых монеты?
(автор - К.Кноп)

Комменты скрыты на несколько дней.

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 25th, 2017 06:28 am
Powered by Dreamwidth Studios