В комментариях к вчерашним задачкам про непрерывные функции несколько человек рассказали, что решили, но никто не описал подробно свое решение. Вот мои доказательства, для тех, кто сам не решил, но интересно. Дальше следуют спойлеры:


1. а) Действительная функция f выполняет заключение теоремы о промежуточном значении. Дано также, что она принимает каждое возможное значение ровно один раз. Доказать, что она непрерывна. б) Обобщить на случай, когда f принимает каждое возможное значение только конечное число раз.

Решение сразу для 1б). Рассмотрим произвольную точку x0, в которой f(x0)=y0, и выберем интервал (y0-ε,y0+ε) вокруг ее значения. У двух точек y0-ε и y0+ε вместе есть только конечное число прообразов, поэтому мы можем найти такой достаточно маленький интервал (x0-δ,x0+δ) вокруг x0, в котором не лежит ни один из этих прообразов этих двух конкретных точек. Тогда для любой точки x в этом интервале ее значение f(x) не может выходить за пределы (y0-ε,y0+ε): например, если f(x) > y0+ε, то согласно заключению теоремы о промежуточном значении, которому подчиняется f, между x и x0 найдется x' с f(x') = y0+ε, т.е. прообраз, которого, мы знаем, там нет. Мы показали, что образ интервала (x0-δ,x0+δ) целиком заключен в интервале (y0-ε,y0+ε), и тем самым доказали непрерывность f в точке x0.


2. Пусть n - четное число. Доказать, что не существует непрерывной действительной функции f, принимающей каждое возможное значение ровно n раз.

Сначала докажем для случая, когда "каждое возможное значение" относится ко всему R, а не только к области значений f. Рассмотрим n прообразов значения 0 (т.е. n нулей функции f), обозначим их x1...xn слева направо. Они делят ось x на n+1 областей: от минус бесконечности до x1, между соседними иксами, и от xn до плюс бесконечности. В каждой отдельной области функция f может быть либо только положительной, либо только отрицательной: если бы она внутри области принимала и положительное и отрицательное значения, это бы создало согласно теореме о промежуточном значении еще один ноль там, где его быть не может. Поэтому мы можем классифицировать каждую область как "отрицательную" или "положительную". При этом две крайние области должны быть разных знаков: если бы скажем они обе были отрицательными, то у функции был бы глобальный максимум, т.к. на интервале [x1,xn] она ограничена, и тогда ее областью значения не может быть все R. Скажем для примера, что крайняя левая область отрицательная, а крайняя правая положительная.

Выберем в каждой из n+1 областей какую-то репрезентативную точку y, и возьмем ε так, чтобы он был меньше, чем абсолютные значения функции на всех репрезентативных точках f(y0)...f(yn). Тогда теорема о промежуточном значении в применении к репрезентативным точкам и границам областей гарантирует нам следующее. В крайней левой области как минимум один прообраз -ε, в крайней правой области как минимум один прообраз +ε, а в каждой внутренней области как минимум два прообраза либо -ε, либо +ε, в зависимости от того, отрицательная это область или положительная. Суммируя все эти гарантии, мы видим, что на два значения -ε,+ε вместе у нас гарантировано как минимум 1+1+2(n-1)=2n прообразов. Но согласно условию, эти две точки обязаны вместе иметь ровно столько прообразов. Значит, все "как минимум" в гарантиях на самом деле "в точности".

Но теперь мы приходим к противоречию, пытаясь подсчитать, скажем, прообразы +ε. Один прообраз от крайней правой области, и по два от каждой внутренней положительной области вместе дают точное число прообразов +ε. Но эта сумма не может быть четным числом n.



Теперь предположим, что условие позволяет, чтобы областью значения f было не все R, т.е. кол-во прообразов каждого значения либо n, либо 0. Тогда уже необязательно, чтобы крайние области были разных знаков, и именно в случае, когда они одного знака, скажем, обе отрицательные, доказательство выше не работает. Но в этом случае у функции есть глобальный максимум M. Ту же классификацию на области, что мы делали с помощью нулей функции, проведем теперь относительно n прообразов значения M. Тогда выйдет, что все области отрицательные, и же выбор ε по той же системе, что и раньше, показывает, что M-ε гарантированно имеет 2n прообразов, а никак не n - противоречие.
Это две задачки из учебника анализа Спивака, которые кто-то привел в качестве примеров в дискуссии о хороших и плохих учебниках. Они могут понравиться тем, кто помнит точное определение непрерывной функции, и что такое теорема о промежуточном значении, но не занимаются математикой профессионально. Для математиков они слишком тривиальны, думаю. У меня заняло некоторое время расшевелить мозги и их решить, и процесс понравился, поэтому решил поделиться с вами.

1. а) Действительная функция f выполняет заключение теоремы о промежуточном значении. Дано также, что она принимает каждое возможное значение ровно один раз. Доказать, что она непрерывна.

б) Обобщить на случай, когда f принимает каждое возможное значение только конечное число раз.

2. Пусть n - четное число. Доказать, что не существует непрерывной действительной функции f, принимающей каждое возможное значение ровно n раз.
Очень милая задачка от Джона Конвея (изобретателя игры "Жизнь").

Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.

На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.

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

(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).

Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
Аня, Боря и Вася сидят за круглым столом. На лбу у каждого написано целое положительное число. Как водится, каждый из них видит числа остальных, но не знает, что написано у него самого. Известно также, что сумма двух написанных чисел равна третьему.

Они договорились играть так: по кругу каждый либо называет свое число, если уверен в ответе, либо говорит, что не знает. Как обычно в таких задачах, мы предполагаем, что у них идеальное логическое мышление.

Аня: "я не знаю свое число".
Боря: "я не знаю свое число".
Вася: "я не знаю свое число".
Аня: "у меня написано 25".

Какие числа написаны на лбах Бори и Васи? Если можете, докажите также единственность этого решения.

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

Update: много правильных ответов! Первой правильно ответила [livejournal.com profile] sthinks, кроме того, правильные ответы у [livejournal.com profile] mudasobwa, [livejournal.com profile] object, [livejournal.com profile] e2pii1, [livejournal.com profile] type_o_graph, [livejournal.com profile] alexa_uk, [livejournal.com profile] butbka, [livejournal.com profile] gul_kiev, [livejournal.com profile] kray_zemli, [livejournal.com profile] emirr, [livejournal.com profile] ger04ka, [livejournal.com profile] utnapishti, [livejournal.com profile] ropher, [livejournal.com profile] gleb_a, [livejournal.com profile] hsft1mb0, [livejournal.com profile] sergeirash и [livejournal.com profile] huzhepidarasa на данный момент (18:00 по Москве). Где-то треть из этих также правильно мотивирует, почему это единственный ответ. Вы все молодцы :) Я дам шанс тем, кто сегодня прочитает задачу, еще решить самим, а ночью по Москве открою все комментарии.

Update: Еще правильные решения дали [livejournal.com profile] falcao, [livejournal.com profile] oblomov_jerusal, [livejournal.com profile] ztatyan, [livejournal.com profile] artem_sulzhenko, [livejournal.com profile] iordane, [livejournal.com profile] buddypis, [livejournal.com profile] mochalkina, [livejournal.com profile] zsd_rd, [livejournal.com profile] ext_2087110, [livejournal.com profile] veefore, [livejournal.com profile] alex_levit, [livejournal.com profile] neuraum, [livejournal.com profile] leonid_a, [livejournal.com profile] igmor, [livejournal.com profile] aerffadf, [livejournal.com profile] lazy_coconut, [livejournal.com profile] lnvp, [livejournal.com profile] assaron, [livejournal.com profile] aragaer и [livejournal.com profile] krolik_ya. Всем спасибо!

Раскрываю все комментарии. Если вы еще не решили и не хотите спойлеров, не заглядывайте в комментарии теперь.
Отличная задачка от IBM.

Перевод условия: Алиса и Боб играют против казино следующую игру: в каждом раунде Алиса выбирает бит 0/1, потом Боб, потом казино; все выборы публичные. Алиса и Боб выиграли раунд, если все три выбора одинаковые, и проиграли в обратном случае. При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному.

Алиса и Боб могут договориться о стратегии заранее, но не могут обмениваться информацией во время игры (кроме своих выборов). Перед началом игры Боб подкупает работников казино и получает всю последовательность выборов казино, но он не может уже к этому моменту передать эту информацию Алисе.

При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.

Нужно доказать, что в игр в n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.

Я пока что знаю, как обеспечить 5 побед, а 6 не могу. Буду еще думать.

Прошу не спойлерить - если у вас есть полное решение, дайте ссылку на свой журнал или поместите его на pastebin.com и дайте ссылку туда - это занимает ровно минуту без регистрации.

Update: AAAAAAAAAAAAAAAAAAAAAA!
Еще две задачки из книги Винклера. По-моему, очень красивые и несколько сложнее, чем в прошлый раз. Комменты скрывать не буду Буду скрывать правильные решения несколько часов, но не гарантирую.

1. Учитель сидит в классе, на его столе стоят весы с двумя чашами. На чашах находится какое-то количество грузов. На каждом грузе написано как минимум одно имя ученика (возможно, больше одного имени). На данный момент правая чаша весов перевешивает.

Снаружи у входа стоят ученики. Когда ученик заходит в класс, он берет все грузы на обеих чашах, на которых написано его имя, и переставляет каждый такой груз на противоположную чашу. Те, что были слева, переходят направо, те, что справа - налево. Следующий ученик делает то же самое с грузами со своим именем, и так далее.

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


2. Алиса и Боб по очереди выбирают цифры от 1 до 9, без повторов (каждая цифра берется не больше одного раза). Выигрывает тот, кто первым соберет у себя три цифры, в сумме дающие 15. Алиса начинает. Есть ли у нее выигрышная стратегия?

Update: открываю все комментарии, в них есть правильные ответы, учтите.
Две простые задачки, которые можно решить в уме. Из книги Винклера, которую я купил на днях и наслаждаюсь. Первую я знал, она древняя и знаменитая, но вторая для меня новая, и я некоторое время помучился, пока не дошло.

1. Вдоль кругового маршрута в пустыне расположены заправочные станции. Бензина, который на них всех в сумме есть, как раз ровно хватает, чтобы объехать весь маршрут и вернуться в исходную точку. Бак у машины достаточно просторный, чтобы вместить бензин на весь маршрут, если нужно. Доказать, что есть такая станция, что машина с пустым баком может начать с нее и проехать весь маршрут.

2. Алиса и Боб играют в следующую игру. На столе выложены в ряд 50 монет, причем каждая из монет может быть любого достоинства. Алиса берет монету с одного из концов ряда, потом Боб берет опять с одного из концов, потом опять Алиса и так далее, пока монеты не закончились. Доказать, что Алиса всегда сможет набрать сумму, равную или больше той, что будет у Боба.

Update: учтите, что в комментариях есть уже верные ответы!

March 2014

S M T W T F S
       1
2 3 4 5 6 7 8
9 10 11 12 131415
16171819202122
23242526272829
3031     

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 22nd, 2017 10:34 pm
Powered by Dreamwidth Studios