Занимательные математические задачи про Алису и не только...

[Алексей Н.]

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

1. а) (3 балла) Алиса записала на доске трехзначное число, не делящееся на 11. Коля, не зная этого числа (но зная, что оно трехзначное), утверждает, что сможет заменить в нем одну цифру или стереть первую цифру так, что полученное число будет делиться на 11. Прав ли Коля?

б) (4 балла) Тот же вопрос, если Алиса записала четырехзначное число.

2. (10 баллов) Одиннадцати чатланам завязывают глаза и надевают каждому на голову колпак одного из 1000 цветов. После этого им глаза развязывают, и каждый видит все колпаки, кроме своего. Затем одновременно каждый показывает остальным одну из двух карточек - белую или черную. После этого все должны одновременно назвать цвета своих колпаков. Удастся ли это? Чатлане могут заранее договориться о своих действиях (до того, как им завязали глаза); чатланам известно, каких 1000 цветов могут быть колпаки.

3. (10 баллов) В галактике с 1001-й звездой некоторые пары звёзд соединены двусторонними космическими маршрутами. Алиса и Громозека играют в "Путешествие по галактике". Алиса выбирает начальную звезду, а затем они по очереди (начиная с Громозеки) решают, на какую звезду им лететь дальше. Звезды не должны повторяться. Проигрывает тот, кто не сможет сделать ход. У кого есть выигрышная стратегия и в чём она заключается? (Каждый перелет возможен только между звездами, соединенными маршрутом.)

[Pinhead]

1.
да
2.
да
3.
удастся
4.
уточните условие задачи.

[Алексей Н.]

Pinhead, в таких задачах просто ответ "да" или "нет" решением не является. Оба варианта надо обосновывать. Например, если в первой задаче ответ "да", то надо доказать, что какое бы число ни написала Алиса, Коле удастся его преобразовать. А если ответ "нет", то надо привести пример такого Алисиного числа, которое преобразовать невозможно. А в задаче про чатлан, если ответ "удастся", то нужно описать метод определения цветов и доказать, что он всегда работает. А если ответ "не удастся" - доказать невозможность построения такого метода. И так во всех задачах.

Правильно ли я понимаю, что в Вашей нумерации 1,2,3,4 - это мои 1а,1б, 2, 3 соответственно? Если так, то касательно Ваших 1 и 2:

В задаче 1 в пунктах а) и б) на самом деле ответы разные.

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

[Pinhead]

1.
Есть известное правило делимости на 11. На 11 делятся те числа, у которых сумма цифр, стоящих на нечетных местах, либо равна сумме цифр, занимающих четные места, либо больше или меньше ее на число, делящееся на 11. Соответственно, любой дурак, воспользовавшись этим правилом, может так изменить одну цифру трех- или четырехзначного числа, чтобы оно стало делиться на одиннадцать.
К примеру, загадано число 4568, которое на 11 не делится. Меняем цифру 6 на 9 и получаем 4598, которое прекрасно делится. С трехзначным еще проще.
2.
Это старая задачка, любимая программистами. Я надеюсь, Вы не будете сейчас требовать подробного ответа. Там надо массив двоичный построить и присвоить его к каждому цвету. Потом Ваши дурошлепы распределят разряды между собой, и дело в шляпе (в смысле, в колпаке).

3.

В галактике с 1001-й звездой некоторые пары звёзд соединены двусторонними космическими маршрутами. Алиса и Громозека играют в "Путешествие по галактике". Алиса выбирает начальную звезду, а затем они по очереди решают, на какую звезду им лететь дальше.

Что это значит "некоторое пары"? Нам неизвестно сколько их? А если это одна пара. Или две? Тогда я Вам хоть щас ответ назову.
И что значит "они по очереди решают"? Так кто всё-таки ПЕРВЫЙ из них решает?
Вообще, мне это несколько напоминает игру ним. Может быть, Вы именно ее зашифровали под видом этой задачки?

[Алексей Н.]

Pinhead:

1.
То, что Вы написали, для одного из пунктов задачи неверно, а для другого это нужно доказывать, а не писать "каждый дурак сможет".

2.
Если Вам известна эта задача, то вопрос снимается (для Вас).

3. Я уже написал, что граф маршрутов может быть ЛЮБЫМ, то есть их может быть сколько угодно и их взаимное расположение тоже может быть каким угодно. Выигрышную стратегию нужно описать так, чтобы она подходила для произвольного графа маршрутов, а не для какого-то конкретного примера.

Алиса выбирает стартовую звезду (любую по своему усмотрению, потом Гр-ка говорит на какую они полетят с неё, потом Алиса говорит куда они полетят с этой следующей звезды и т.д.

Я не вижу здесь сходства с нимом.

[Pinhead]

То, что Вы написали, для одного из пунктов задачи неверно

Докажите. Приведите мне трех- или четырехзначное число, которое я бы не смог заменой одной цифры разделить на 11

Я уже написал, что граф маршрутов может быть ЛЮБЫМ, то есть их может быть сколько угодно и их взаимное расположение тоже может быть каким угодно. Выигрышную стратегию нужно описать так, чтобы она подходила для произвольного графа знакомств, а не для какого-то конкретного примера.

Ну, Вы хотите, чтобы Вам тут алгоритмы писали что ли? Это тогда Вы точно не тот форум выбрали. Обратитесь к г-ну Нгаану, он Вам напишет, если захочет.

[Алексей Н.]

545 - единственное такое трехзначнное число (можете попробовать доказать единственность)

Описать стратегию для произвольного графа - нормальная ситуация для математической игры. Такие задачи на математических олимпиадах не редкость. И да, любая стратегия - это некоторый алгоритм действий, почему Вас это смущает? Это всё тоже математика. Возможно, Вы слишком узко представляете себе её границы. Теория игр и теория алгоритмов - это её разделы.

[Pinhead]

545

Да, действительно. С ним не получается штука с правилом деления и последнюю цифру нельзя так изменить, чтобы подогнать под правильный множитель. Оно оказывается ровно "посередине".
Ваша взяла!

Описать стратегию для произвольного графа - нормальная ситуация для математической игры. Такие задачи на математических олимпиадах не редкость. И да, любая стратегия - это некоторый алгоритм действий, почему Вас это смущает? Это всё тоже математика. Возможно, Вы слишком узко представляете себе её границы. Теория игр и теория алгоритмов - это её разделы.

Ну Вы издеваетесь, что ли? Кто этим будет заниматься? Я понимаю, тут еще была тема с парадоксальными логическими задачками с математическим уклоном. Типа задачи Льва Толстого и прочее. Голову поломать. А всякие алгоритмы Флойда и Дейкстры - кому это надо? Сюда и так-то кроме меня вряд ли кто-то отписался бы, да и я, скорее, ради прикола зашел.
Не обижайтесь, но это точно мимо.
Впрочем, я могу и ошибаться, конечно, но вероятность этого невысока.

Добавлено спустя 1 час 9 минут 6 секунд:
Re: Занимательные математические задачи про Алису и не только...
Вот Вам моя страшная месть.

[Весельчак Ы]

Вот я меньше всего ожидал, что Pinhead займется решением второй задачи, ибо колпак надеть на него проблематично. А мстить нехорошо. Теорема Банаха-Тарского утверждает, что шар можно разбить на пять частей, а затем из них, без наложений и пустот, сложить два точно таких же шара.

[Алексей Н.]

Pinhead, видно, что Вы слабо себе представляете, какие задачи решаются на математических олимпиадах. Задача про игру с путешествием - одна из классических таких задач. И решение у неё красивое, просто Вы неправильно понимаете, в каком виде оно описывается, если начали говорить про алгоритм Флойда и т.п. Тут совсем другое, изящное математическое решение, по мотивам известной теоремы о графах. Но можно решать, ничего об этой теореме не зная. Жаль, что Вы с таким предубеждением к этой задаче отнеслись, любой опытный олимпиадник скажет, что задача очень хороша. Мне кажется, что если бы Вы узнали решение, то согласились бы с этим.

А "месть" Вам надо придумать похитрее, а то задачка с бородой, есть во многих старых сборниках.

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

[Певец Космоса]

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

[Алексей Н.]

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

Это не так, дело в другом.

[Pinhead]

А мстить нехорошо.

Хорошо.

Жаль, что Вы с таким предубеждением к этой задаче отнеслись

Я к любой задаче отношусь к предубеждением, они меня напрягают.

А "месть" Вам надо придумать похитрее, а то задачка с бородой, есть во многих старых сборниках.

Ну да, а то я не догадался. Искал пакона, случайно попалась на глаза. Не буду я специально напрягаться и искать ничего.

[Весельчак Ы]

опытный олимпиадник скажет, что задача очень хороша.

+1

изящное математическое решение, по мотивам известной теоремы о графах. Но можно решать, ничего об этой теореме не зная.

Рассмотрим максимальную дизъюнктную семью ребер...

[Алексей Н.]

Весельчак Ы
"Рассмотрим максимальную дизъюнктную семью ребер... "
Ага. И назовем ее семьей Алисы Графисты обычно говорят паросочетание. Теорема о характеризации наибольших паросочетаний в терминах чередующихся цепей. Уверен, что подробности Вы без труда восстановите.

Добавлено спустя 1 час 44 минуты 22 секунды:
Re: Занимательные математические задачи про Алису и не только...
Продолжим, стремясь подогреть интерес за счет нездорового денежного азарта: :shock:

4. Перед Весельчаком 100 закрытых коробочек, в каждой – либо красный, либо синий кубик. У Весельчака на счету есть рубль. Он подходит к любой закрытой коробочке, объявляет цвет и ставит любую сумму (можно нецелое число копеек, но не больше, чем у него на счету в данный момент). Коробочка открывается, счет Весельчака увеличивается или уменьшается на поставленную сумму в зависимости от того, угадан или не угадан цвет кубика. Игра продолжается, пока не будут открыты все коробочки. Какую наибольшую сумму на счету может гарантировать себе Весельчак, если ему заранее известно, что красных кубиков
а) ровно 1? (4 балла)
б) ровно 10? (10 баллов)
(Весельчак в любой момент может поставить и 0, то есть просто бесплатно открыть коробочку и увидеть цвет кубика.)

[Весельчак Ы]

По прикидкам, при m красных и n синих кубиках мой тезка может гарантированно разбогатеть в
\frac{2^{m+n}}{C^m_{n+m}}раз, а мечты о большем, увы, могут оказаться призрачными. Хотя я хотел бы отметить, что, ввиду необразованности пенителя космических трасс, объяснить ему тонкости требуемой стратегии смог бы лишь Крыс.

[Алексей Н.]

По прикидкам, при m красных и n синих кубиках мой тезка может гарантированно разбогатеть в
\frac{2^{m+n}}{C^m_{n+m}}раз, а мечты о большем, увы, могут оказаться призрачными. Хотя я хотел бы отметить, что, ввиду необразованности пенителя космических трасс, объяснить ему тонкости требуемой стратегии смог бы лишь Крыс.

Именно так. А ставочку как грамотно делать? То бишь поделитесь с незадачливым тезкой рецептом обогащения
Максимальность получилось доказать?

P.S. Для этой задачи я почему-то очень живо представляю себе сцену открытия очередной коробочки Весельчаком в исполнении Невинного. Это должно быть нечто совершенно умопомрачительное, этакий священный ритуал в лучших традициях кефирной церемонии, со всей сопутствующей мимикой, телодвижениями и неподражаемой реакцией на полученный результат.

[Весельчак Ы]

ставочку как грамотно делать? То бишь поделитесь с незадачливым тезкой рецептом обогащения
Максимальность получилось доказать?

Так это набросок, я выкладки даже не проверял. Максимальность должна следовать из рекуррентной формулы. Если коэффициент гарантированного обогащения при $m$ красных и $n$ синих кубиках обозначить через $V(m,n)$, то имеем, что $V(0,n)=2^n$, а также рекуррентную формулу при $m,n\ge 1$:
$$V(m,n)=\max (\max_{0\le x\le 1} \min( (1+x)V(m-1,n),(1-x)V(m,n-1)),$$
$$\max_{0\le x\le 1}\min( (1+x)V(m,n-1),(1-x)V(m-1,n))).$$

Значение $x=|V(m-1,n)-V(m,n-1)|/(V(m-1,n)+V(m,n-1))$, при котором достигается максимум соответствующего минимума линейных функций и определяет размер ставки. При этом получаем, что $V(m,n)$ является средним гармоническим $V(m-1,n)$ и $V(m,n-1)$. После чего, путем несложных преобразований, получаем, что числа $2^{n+m}/V(m,n)$ образуют треугольник Паскаля, откуда и получаем конечную оценку.

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

PS. А теперь можно найти, что $x=|n-m|/(m+n)$. Получилось проще, чем я предполагал (я сначала не находил точного значения $x$, а ограничился вычислением эстремального значения функции).

[Алексей Н.]

Весельчак Ы

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

Добавлено спустя 37 минут 1 секунду:
Re: Занимательные математические задачи про Алису и не только...
Следующие задачи (немного в другом оформлении) я предлагал в разное время на разные турниры школьников.

5. (6 баллов) Для натурального числа n обозначим через R(n) сумму всех остатков от деления n на натуральные числа, меньшие n. Докажите, что существует бесконечно много n таких, что выполняется равенство R(n) = R(n+1).

6. (9 баллов) Планета Шелезяка имеет форму выпуклого железного многогранника, одна грань которого шестиугольная, а все остальные - четырехугольные. В вершинах многогранника расставлены целые числа, причем вдоль границы шестиугольной грани по циклу идут числа 1,2,3,4,5,6. Докажите, что у многогранника есть ребро, разность чисел на концах которого кратна трем.

7. У Алисы на прямоугольном столе лежат прямоугольные конверты от писем, края которых параллельны сторонам стола. Конверты могут перекрываться между собой.

а) (9 баллов) Известно, что из любых трех конвертов какие-то два перекрываются. Докажите, что Алисе удастся тремя кнопками приколоть все конверты к столу. Докажите, что двух кнопок может оказаться недостаточно.
б) (12 баллов) Известно, что каждая точка стола накрыта не более чем двумя конвертами (конверты лежат не более чем в два слоя). Докажите, что Алисе удастся покрасить все конверты в 6 цветов так, чтобы конверты одного цвета не перекрывались.

В обоих пунктах задачи конверты нельзя сдвигать.

[Весельчак Ы]

5. По прикидкам, можно взять n=2^k-1.