Никита

Решение задачи 502

2022-12-18T22:54:21.268Z

Условие:

Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число N от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно N орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?

Решение:

Обозначим через a, b, c количества орехов в трех коробках. Ноздрев оперирует с восемью числами: 0, a, b, c, a + b, b + c, a + c, 1001 (a + b + c). Рассмотрим отрезок [0;1001] и отметим на нем восемь вышеперечисленных чисел. Отрезок в общем случае разбивается на семь частей. Пусть Чичиков назвал число N. Рассмотрим минимальное расстояние от N до одного из отмеченного числа. Это минимальное количество орехов необходимое переложить Ноздреву, чтобы предъявить коробки с суммарным числом N. Таким образом, при фиксированном расположении орехов Чичиков может получить максимум половину (с округлением вниз) длины наибольшего отрезка душ.

Как же расположить орехи, чтобы Чичиков получил как можно меньше? Надо минимизировать длину максимального отрезка. Заметим, что длина наибольшего отрезка не меньше 1001 / 7 = 143, то есть Чичиков гарантировано получает 71 душу. Ноздрев может расположить орехи так: 143, 286, 572, тогда отрезок [0;1001] разобьется на семь равных отрезков, то есть больше 71 души Чичиков не сможет получить.

Ответ: 71.

Подсказка к задаче 502

2022-12-18T22:29:45.782Z

Ноздрев имеет восемь чисел, прибавляя к которым или вычитая из которых ему надо получить число N.

Подсказка к задаче 500

2022-05-23T20:13:49.439Z

Нарисуйте равносторонний треугольник и три полуокружности.

Решение задачи 500

2022-05-23T20:12:50.240Z

Условие:
Существует ли такая отличная от круга фигура, ограниченная отрезками и дугами окружностей, что все отрезки, делящие пополам ее периметр, имеют одинаковые длины?

Решение:
Существует. Возьмем равносторонний треугольник АВС. Построим на каждой стороне во внутрь полуокружность. Дуги, находящиеся внутри треугольника, обозначим пунктиром (см. рисунок). Покажем, что ADCFBE — фигура, удовлетворяющая условию.

Нетрудно видеть, что отрезок AF делит периметр пополам. Начнем двигать концы отрезка так, что он делил периметр пополам. Если точка А сместится на дугу АD в точку G, то точка F перейдет в какую-точку H, на дуге FB, то есть концы отрезка всегда лежат на одной из трех полуокружностей.

Так как GH делит периметр пополам, то длина дуги AG равняется длине дуги FH. Значит, дуга AGDF равна дуге GDFH, то есть отрезки имеют одинаковую длину.

Ответ: Да.

Подсказка к задаче 498

2021-01-13T15:09:57.730Z

Переведите число p в двоичную дробь

Решение задачи 498

2021-01-13T15:08:54.516Z

Условие:

Дано вещественное число p из отрезка [0;1]. С помощью симметричной монетки реализовать вероятность p.

Решение:

Представим число p в виде двоичной дроби. Например, 5/8 = 0, 101. Конечно, дробь может получиться бесконечной длины. В любом случае, мы представляем число p в виде суммы (возможно, бесконечной) целых степеней 1/2.

Реализуем для примера вероятность 41 / 64 = 1/2 + 1/8 + 1/64. Выпишем вектор степеней в порядке возрастания: (1, 3, 6). Реализуем следующий процесс:

1) Подрасываем монетку один раз, если выпал орел, то заканчиваем процесс с успехом, иначе подбрасываем монетку еще два раза (3 − 1)

2) Если выпали два орла, то заканчиваем процесс с успехом. Если выпали два орла, бросаем еще три (6 − 3) раза, иначе заканчиваем процесс с неуспехом.

3) Если выпали три орла, то заканчиваем процесс с упехом, иначае заканчиваем процесс с неуспехом.

Для наглядности представим наш процесс в виде схемы:

Галочкам обозначены успешные исходы

Какая вероятность закончить процесс с успехом? Есть три пути (три способа дойти до галочек), посчитаем вероятности каждого.

1) Вероятность первой галочки одна вторая (вероятность что выпал орел)

2) Вероятность второй галочки: сначала должна выпасть решка, потом два раза орел, то есть 1/2 ∙ 1/4 = 1/8

3) Вероятность третьей галочки: сначала должна выпасть решка, потом два раза орел, потом три раза орел: 1/2 ∙ 1/4 ∙ 1/8 = 1/64

Суммируя все вероятности, получаем 1/2 + 1/4 + 1/64 = 41/64, что и требовалось.

Два замечания:

1) мы заканчиваем процесс, только когда выпали все орлы при очередном бросании

2) продолжаем бросать только когда выпали все решки при очередном бросании

Как же все-таки реализовать "страшную" вероятность, например p = ln(10) / 10?

Переводим число в двоичную дробь: p = 0, 10001100011000.... Пусть d = (d1, d2, ...) — вектор степений, или, говоря по-другому, номера позиций, на которых стоят единички.

Итак, наши действия:

1) Кидаем монетку d1 раз, если выпали все орлы, то заканчиваем процесс с успехом. Если выпали все решки, то подбрасываем еще d2−d1 раз. Иначе заканчиваем процесс с неуспехом.

2) Если выпали все орлы, то заканчиваем процесс с успехом. Если выпали все решки, то подбрасываем еще d3−d2 раз. Иначе заканчиваем процесс с неуспехом

3) и так далее

Может ли процесс продолжаться бесконечно? Нет, потому что вероятность такого события равна пределу 1/2^n, при n стремящемуся к бесконечности, то есть нулю.

Подсказка к задаче 497

2020-09-20T17:13:36.349Z

Изначально Лошадка может в одной из клеток, то есть 63 вариант. Переберите поочередено эти варианты.

Решение задачи 497

2020-09-20T17:12:31.808Z

Условие:

Ежик стоит в левой нижней клетке поля 8×8. А в какой-то другой клетке
пасется Лошадка. На поле стоит туман, ничего не видно, но ежику надо найти Лошадку. Лошадка каждую минуту переходит на соседнюю по стороне
клетку и громко говорит, куда она перешла (влево, вправо, вверх или вниз).
Ежик тоже может сделать шаг в одну из соседних по стороне или диагона-
ли клеток, как только услышит Лошадку. Ежик найдет Лошадку, если
окажется с ней на одной клетке. Что же делать Ежику?

Решение:

Предположим, что мы видим Лошадку. В таком случае поймать ее (оказаться в одной клетке) не очень сложно. Сначала можно встать с ней на одну горизонталь, а потом, оставаясь с ней постоянно на одной горизонтали, каждый ход приблажаться. У нас преимущество — мы можем ходить по диагонали.

Вернемся к условию задачи. Пронумеруем все клетки от 1 до 64 (мы стоим на 64-ой). Также мы будем запоминать все ходы Лошадки, т.е. то, что она говорит. Изначально она могла находиться в одной из 63-ех возможных клетках. Мы ней знаем в какой, будем перебирать все 63 варианта.

Предполагаем, что Лошадка изначально стоит в первой клетке. То есть теперь мы ее как будто видим. Начинаем ее ловить, если мы ее поймали, то задача решена. Если нет, значит Лошадка изначально была не в первой клетке. Пусть на поиск Лошадки мы потратили N шагов.

Предполагаем, что Лошадка изначально стоит во второй клетке. Мы знаем какие первые N шагов она сделала (мы все запоминали). Значит мы знаем, где она находится сейчас, если она изначально была во второй клетке. Начинаем ее ловить, если поймали, то задача решена. Если нет, то изначально Лошадка была не во второй клетке. Пусть на поиск Лошадки мы потратили еще M шагов.

Предполагаем, что Лошадка изначально стоит в третьей клетке. Мы знаем какие первые N+M шагов она сделала (мы все запоминали). Значит мы знаем, где она находится сейчас, если она изначально была в третьей клетке. Начинаем ее ловить, если поймали, то задача решена. Если нет, то изначально Лошадка была не в третьей клетке. И так далее.

Перебираем все 63 варианта один за одним. В какой-то момент мы найдем Лошадку.

Ответ на витражи

2020-04-29T18:03:49.982Z

Подсказка к задаче 496

2020-04-28T18:29:27.978Z

Поделите каждый член прогрессии на минимальную степень p^n q^m, где n и m минимальные степени вхождения p и q среди членов прогрессии.