тигр

задача дня -- 4

С давних пор мне нравятся задачи на тему сравнения чисел. Обычно берутся какие-то два сравнительно близких друг к другу числа, и требуется определить, какое из них больше. К условию при этом добавляют что-нибудь вроде "не используя калькуляторов и таблиц".

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

Предлагаю таким способом проверить, что 11^11 > 9^12 ("крышечка", как обычно, означает возведение в степень). Это довольно близкие числа: они равны 285311670611 и 282429536481 соответственно. Но убедиться в справедливости неравенства нужно в пределах легко проверяемых устных вычислений.

Надеюсь, "правила игры" понятны. Комментарии я не скрываю.
pequim1

задача дня -- 3

Вот совсем "свеженькая" интересная задача. Она только вчера вечером появилась, и сам я пока решения не знаю.

Всякое ли рациональное число можно представить в виде произведения четырёх рациональных чисел, сумма которых равна нулю?

Комменты не "скринятся".
тигр

задача дня -- 2

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

Даю две формулировки условия. Сначала -- более "математизированная".

Дан массив целых чисел X[1..n]. Требуется найти максимум величины X[i]-X[j] по всем i<=j. Массив разрешается читать только один раз в режиме read-only. Дополнительная память состоит всего из нескольких ячеек (скажем, не больше пяти).

А вот более "занимательная" переформулировка.

Представим себе, что нам стала известна "инсайдерская" информация о курсе доллара на следующий месяц. Мы сидим у монитора, и на экране мелькают цифры -- не слишком быстро (чтобы мы могли проделать простейшие устные вычисления), но и не слишком медленно (записать на бумагу мы уже ничего не можем). Числа идут по дням, и они округлены до целого числа рублей (для простоты). Курс всё время колеблется. У нас есть некоторое количество баксов, и мы хотим наиболее выгодно их продать в один из дней, когда курс достаточно высокий, чтобы чуть позже купить их по подходящей цене, когда курс существенно снизится. Считается, что мы в каждый момент можем удерживать в голове несколько чисел (например, два или три). Требуется определить, на какую максимальную выгоду мы можем рассчитывать при такой сделке. Разницей между курсом покупки и продажи для простоты полагается пренебречь.

UPD (02.05) Раскрываю все комментарии. Спасибо всем, кто участвовал. По отдельности анализировать ответы не буду. Задача действительно была несложной, и все решения используют примерно ту же самую идею. В одном из первых же ответов прозвучало почти буквально то, что бы сказал я сам. Что касается длинных программных кодов, то я их, к сожалению, "не чтец" (для меня это примерно как читать "на чукотском" :)) Но из общих соображений было понятно, что там реализовано примерно то же самое (иногда почему-то длинновато).
тигр

задача дня -- 1

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

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

Вот условие первой задачи.

Дана числовая последовательность x(n), заданная рекуррентно, где x(1)=a -- фиксированное число интервала (0;1), и далее x(n+1)=x(n)+x(n)^2/n^2. Требуется доказать, что эта последовательность ограничена.

UPD (14.04) Один мой коллега прояснил происхождение этой задачи. Оказывается, она есть в сборнике Садовничий В.А., Григорьян А.А., Конягин С.В. Задачи студенческих математических олимпиад. 1987. Задача под номером 15, она предлагалась на мехматской олимпиаде. Решение там дано примерно такое, как здесь изложил rus4.

А вот какое решение было известно мне (придумал его не я). Сначала по индукции доказываем, что x(n) < an. Далее подставляем это значение и улучшаем оценку: x(n+1)=x(n)(1+x(n)/n^2) < x(n)(1+a/n) < x(n)*exp(a/n). Отсюда x(n+1) < a*exp(a(1+1/2+...+1/n)) < Cn^a, поскольку гармонические суммы растут примерно как ln n. Наконец, делаем третий "заход", после которого тем же способом получается x(n+1) < x(n)(1+1/n^{2-a}), и далее всё следует из сходимости ряда с общим членом 1/n^{2-a} ввиду 2-a > 1.
mohan2

есть белая овца среди черных овец

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

Имеется стадо овец, куда первоначально входит одна белая и одна чёрная овца. Ежедневно проделывают следующую процедуру: выбирают наудачу одну овцу из стада, и запоминают её цвет. Затем её возвращают в стадо, и добавляют туда же одну новую овцу чёрного цвета.

Если в какой-то из дней оказывается выбранной белая овца, и в предыдущий день имело место то же самое, то принимается решение сделать из неё шашлык. Какова вероятность такого события при неограниченном повторении процедуры?


Задача решается "по-честному", то есть у неё нет какого-то совсем "очевидного" решения. То есть тут в любом случае что-то придётся считать.

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

головоломка

Всем желающим предлагаю подумать над следующей интересной головоломкой (пост открытый).

Незнайка пишет по кругу числа от 1 до 19 включительно в некотором порядке. После этого Знайка подсчитывает суммы из трёх подряд идущих чисел и выбирает среди этих сумм максимальную. Цель Незнайки -- добиться того, чтобы полученное Знайкой число было как можно меньше. Какого наилучшего результата может добиться Незнайка?

Чтобы было понятнее, вот пример. Компьютер случайным образом выдал такую перестановку чисел: 18, 9, 10, 14, 2, 4, 16, 13, 17, 19, 7, 6, 1, 8, 15, 5, 3, 12, 11. Они идут по кругу, то есть за последним следует первое. Знайка получит при этом такие числа: 18+9+10=37, 9+10+14=33, 10+14+2=26, ... , 3+12+11=26, 12+11+18=41, 11+18+9=38. Наибольшим значением окажется сумма 13+17+19=49. Ясно, что это очень много: при случайном выборе три довольно больших числа оказались рядом, и результат получился плохой. Этот пример показывает, что числа надо как-то умело чередовать, чтобы таких больших значений не возникало.

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

Комменты убираются под "скрин", но через какое-то время будут раскрыты.

UPD (13.02.15) Правильных ответов поступило довольно много, причём примеры все приводили разные. Наилучший результат равен 32. Доказать, что лучше нельзя, довольно несложно (см. комменты). Найти подходящий пример, как мне кажется, задача более трудоёмкая (особенно если ответ заранее не известен). Использовать компьютер для этого дела не запрещалось, так как полный перебор вариантов тут вряд ли возможен, и требовалось так или иначе использовать "эвристические" подходы.

Всех благодарю за участие.
newtiger

без единого гвоздя

Придумалась вчера одна любопытная вероятностная задача. У меня не один раз бывали вопросы, где требовалось дать чисто интуитивный ответ по принципу "как кажется". Здесь же задание будет несколько другое.

Пост открытый, как и все остальные на аналогичную тему.

Сюжет задачи такой. Представим себе тираж "Спортлото". Скажем, выпали случайно какие-то 6 номеров из 49. Каково должно быть при этом среднее значение наименьшего из номеров?

На всякий случай поясню, что это значит. Пусть проводится много тиражей, и мы в каждом из них запоминаем наименьший из номеров. Скажем, если выпали 32, 34, 10, 47, 16, 25, то мы запоминаем 10. В другом тираже выпали 28, 47, 40, 20, 21, 5. Здесь мы запоминаем число 5, и так далее. После того, как все тиражи прошли, мы вычисляем среднее арифметическое тех номеров, которые мы запомнили. И требуется сказать, каково будет это значение, если тиражей пройдёт много?

Здесь не так трудно произвести подсчёт "эвристического" характера, чтобы предсказать ответ. А именно, будем считать, что среднее значение наименьшего номера получается тогда, когда 6 номеров среди 49 распределены "равномерно". Это значит, что промежутки между выпавшими номерами полагаются одинаковыми. До первого номера (то есть до наименьшего) идёт в среднем x номеров. Потом следует x номеров между первым и вторым по величине, столько же между вторым и третьим, и так далее. После самого большого значения также идёт x номеров.

Шесть чисел задают семь промежутков, каждый имеет длину x. Эти промежутки вместе должны содержать 49-6=43 числа, откуда x=43/7. То, что это значение дробное, не ведёт к эффекту типа "два землекопа и две трети" (с), потому что речь идёт об оценке среднего значения, а оно может быть дробным. Понятно, что наименьшее число на единицу больше того значения, которое у нас получилось (длины промежутка слева), откуда мы получаем оценку 50/7. В общем случае, если выпадают k номеров из n, те же соображения приводят к ответу (n+1)/(k+1). И этот ответ, полученный "эвристическим" путём, действительно является верным.

А теперь собственно вопрос: как это доказать (строго), не делая при этом сложных арифметических вычислений? Имеется в виду, что достаточно просто взять и посчитать всё "в лоб", как это обычно делается. Получатся какие-то суммы произведений, их можно будет "свернуть", и получится указанный выше ответ. Но как это сделать "без единого гвоздя", то есть так, чтобы все вычисления осуществлялись устно?

Я знаю, что вопросы такого рода кое-кто из моих френдов помещает, так что интересно будет подумать. Комменты я оставляю открытыми.
pequim1

13,7%

ТигрИнформАгентство сообщает, что комментарии из этого поста раскрыты для ознакомления.

Сама по себе вероятностная задача, которая там рассматривалась, решается стандартными способами, и ответ в ней составляет 15*74/86. Это примерно 0,137, то есть свыше 13 с половиной процентов. Причиной того, что я устроил этот опрос, является то, что этот ответ, в правильности которого никогда не было сомнений, мне даже сейчас кажется удивительным. В смысле, "почему так много?" Интуитивно кажется, что вероятность намного меньше. Я сам без вычислений назвал бы, наверное, процентов 5 от силы.

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

Есть классические примеры того, когда тот или иной ответ в вероятностых задачах выглядит "парадоксально". Например, это касается так называемого "парадокса дней рождения", о котором можно прочитать здесь, если кто не знает. Видимо, само явление "искажения" в каком-то смысле закономерно. Его можно сравнить с тем, что далёкие предметы нам кажутся маленькими, к чему все привыкли, и что никого не удивляет. Это даже не назовёшь какой-то ошибкой или искажением восприятия. Наверное, и с вероятностными вопросами происходит что-то подобное.

А для любителей "бразилейры" -- вот такая видеозапись, где Мария Рита (дочь Элиш Режины) поёт песню 70-х годов вместе с Фагнером (одним из авторов этой песни).

  • Current Music
    Fagner e Maria Rita -- Mucuripe
pequim1

седьмое небо

У Тигра сейчас, как, наверное, у многих, образовались своего рода "мини-каникулы". По этому поводу захотелось устроить очередной опрос на вероятностную тему. Ниже будет предложено условие одной достаточно несложной
задачи. Решать её не требуется, а нужно сделать следующее: внимательно прочитать условие, и безо всяких вычислений предложить "мгновенный" ответ на уровне ощущения. Будет спрошено, чему равна вероятность некоторого события,
и в комментарии (они все до поры до времени будут скрыты) нужно указать свой ответ (можно в процентах). Просьба при этом давать только серьёзные ответы, то есть не надо предлагать "146%" и прочего.

Если кто захочет решить задачу и получить точный и правильный ответ -- это можно сделать уже после того, как будет дан ответ "вскидочный" -- в противном случае не будет интересно. А вот само условие.

В лифт девятиэтажного дома заходят 6 человек. Каждый из них может с одинаковой вероятностью выйти на любом этаже со второго по девятый. Все выходы считаются совершенно независимыми. Какова вероятность того, что на седьмом этаже выйдут ровно два человека из шести?

UPD (25.01.14) Комментарии раскрыты.
тигр

мини-плоскости

Купил я себе сегодня новую клавиатуру (всего за 200 рублей :)) Старая была вполне работоспособна, но на ней стёрлись многие буквы, и меня это постоянно раздражало. Так что теперь я могу печатать быстрее, чем раньше. И под это дело у меня возникла мысль, а не написать ли новый пост? Тем более, что тема "подвернулась" сама собой: сегодня я вспомнил об одной старой задаче, которая предлагалась в самом первом выпуске журнала "Квант". Было это в далёком 1970 году. Задача достаточно непростая, и её решение, приведённое несколькими номерами позже, было длинным и сложным. Но сама постановка задачи весьма проста, и смысл должен быть понятен каждому. Прежде всего, вот ссылка на тот номер журнала, в котором приведено решение. Речь идёт о задаче М5. Там, среди прочего, даются и "занимательные" переформулировки, но я не буду из них исходить, и вообще по этой ссылке ходить не обязательно. Сейчас всё будет изложено "с нуля".

Журнал у меня с некоторого времени почти весь "под замком", но посты на математическую тему я обычно делаю открытыми для всех. Итак, приступим. Этот пост можно ещё "приурочить" к началу учебного года, хотя у меня пока продолжается отпуск :)

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

(А1) Через любые две различные точки проходит одна и только одна прямая.

Если рассматривать "обычные" точки и прямые, то эта аксиома для всех должна быть "наглядно-очевидной". Сейчас я упомяну ещё об одной аксиоме -- она во многом выглядит ещё проще, и у неё очень простой смысл. Далее мы её даже почти не будем привлекать. Важно здесь то, что этими двумя аксиомами мы в данном изложении и ограничимся. Интерес представляет то, что даже из таких совсем простых положений можно извлечь весьма интересные и нетривиально доказываемые факты.

(А2) Существуют по крайней мере три точки, не лежащие на одной прямой.

Смысл у этой аксиомы очень простой: не все точки лежат на одной и той же прямой. Этим постулируется, что мы имеем дело не с одной прямой, а с чем-то вроде плоскости. В курсе планиметрии именно эти аксиомы излагаются в самом начале.

Возникает вопрос: что эти две простые аксиомы могут описывать? Здесь надо абстрагироваться от обычной геометрии и представить себе следующее. "Точками" разрешается называть любые объекты. Например, роль "точек" могут играть люди, составляющие некоторую компанию. А "прямыми" будут называться те или иные совокупности точек. Например, в случае людей это могут быть какие-нибудь комиссии, создаваемые из отдельных участников.

Всем известно, что на плоскости имеется бесконечное число точек. Нас же будет интересовать случай, когда общая совокупность "точек", которую мы рассматриваем, конечна. Скажем, речь идёт об учениках школьного класса. Пусть в этом классе организовано несколько кружков, или комиссий, или чего-то ещё. Будем тогда говорить, что совокупность учеников, входящих в одну такую "комиссию", представляет собой "прямую".

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

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

Приведём простейший пример "мини-плоскости", например, из 10 точек. Расположим 9 точек вдоль одной прямой, а десятую точку поместим вне этой прямой и соединим линиями с каждой из девяти точек. Получится схема, в которой точек 10, и линий нарисовано тоже 10.

Можно привести примеры, когда линий будет больше, чем точек. В частности, аксиомы А1 и А2 не запрещают проводить линию всего лишь через одну точку. Это ничему не помогает и не мешает -- просто увеличивает число линий. Если такие линии есть, то их можно просто стереть, сравнивая далее количество линий и количество точек. Так вот, оказывается, что на "мини-плоскости" линий всегда имеется столько же, сколько точек, или больше. Это и есть то утверждение, о котором далее пойдёт речь, и это точная переформулировка задачи из "Кванта".

Далее я намерен изложить её решение в такой форме, чтобы оно содержало минимум формул и обозначений, и чтобы смысл был наиболее "прозрачен" для читателя. Я буду основываться на доказательстве, идею которого предложил известный американский математик Джон Конвей. Сам же доказываемый факт был впервые установлен в работе 1948 года, авторами которой были де Брёйн и Эрдёш.

Collapse )

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