Решить математические задачки

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

Задача 1.1. В отличии от человеческих, в глазах саларианцев с планеты Сур’Кеш есть

целых 5 видов фоторецепторов (3 из них чувствительны к излучению в оптическом диа-

пазоне, 1 в инфракрасном, и 1 в ультрафиолетовом). В последние несколько десятилетий

среди саларианцев распостранилась мода красить свои рога в ненатуральный цвет, поэто-

му салоны красоты на Сур’Кеше ломятся от клиентов.

Чтобы достичь требуемого цвета, опытный мастер по покраске рогов смешивает раз-

личные краски очень точно, и в то же время он старается не делать лишней работы.

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

клиентом?

Задача 1.2. Множество X состоит из 1012 точек, выбранных равномерно наугад из 100-

мерного гиперкуба со сторонами длиной 1. Мы много раз проводим такой эксперимент:

выбираем равномерно наугад из того же единичного гиперкуба точку p, а затем ищем 10

ближайших к p точек из X. Обозначим их x1, x2, . . . , x10 в порядке увеличения расстоя-

ния до p (x1 — ближайшая к p, и т.д.). Оцените среднее расстояние между p и x10 при

многократном повторении этого эксперимента.

Задача 1.3. Аня и Бодя подбрасывали честную (орел и решка выпадают с вероятностью

1/2) монетку, причем Аня сделала это n раз, а Бодя — n + 1. Найдите вероятность того,

что у Боди выпало больше решек, чем у Ани.

Задача 1.4. Устав спасать человечество, супергерой Флеш открыл свою курьерскую до-

ставку. Каждый день он обходит достаточно большое число N клиентов по оптимальному

(кратчайшему возможному) маршруту и доставляет им корреспонденцию.

Благодаря нечеловеческой скорости перемещения Флеша его бизнес процветает. Через

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

увеличится пройденное им за день расстояние? (Считайте, что плотность распределения

клиентов по районам города останется неизменной.)

Задача 1.5. Есть n монет неизвесного веса и чашечные весы без гирь. Разрешается по-

местить некоторое число монет на одну чашу и такое же количество монет на другую

чашу. После этого весы показывают, какая из чаш весит больше, или же что чаши весят

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

что все монеты имеют одинаковый вес.

Задача 1.6. Пусть a1, a2, . . . , an — перестановка чисел 1, 2, . . . , n. Назовем число ai боль-

шим, если ai > aj для всех i < j 6 n. Найдите среднее количество больших чисел в

случайной перестановке 1, 2, . . . , n, взятой равномерно наугад.

Задача 1.7. В стране Прожектории N городов, соединенных авиарейсами по цепочке: 1 –

2 – 3 – ... – (N-1) – N. Иными словами, между каждой парой городов с соседними номерами

есть регулярный авиарейс. Беспробудно пьяный Женя Лукашин находится в городе 1 и

хочет добраться до города N. Для этого он каждое утро приходит в аэропорт и садится

на рейс в случайном направлении, который вылетает из текущего города. Оцените число

рейсов, которое понадобится Жене, чтобы попасть таким способом из города 1 в город N.

Задача 1.8. Есть круговая дорога, на которой в некоторых местах находятся n автозапра-

вок. Известны расстояния между соседними заправками, а также количество бензина на

каждой заправке. Имеется также автомобиль с известным постоянным расходом бензина и

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

2

не более C · n элементарных операций и позволяет найти ту заправку, начиная с которой

можно проехать по кругу всю дорогу, или же сказать, что такой заправки нет.