Математическое и загадочное

[E.K.]

Несмотря на подавленное настроение, да-да, по причине ни разу не простых задачек.. Но вы же готовы попробовать ещё? Так, чтобы ни разу раньше не было? Удивительное, непростое, немного арифметическое.. - будете решать? У меня есть немного накопленного материала.

 

Ну?

[E.K.]

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

 

Есть 25 верблюдов. Проводят забеги, в которых могут участвовать не более 5 верблюдов за один раз. Сколько забегов надо провести, чтобы определить трёх самых быстрых верблюдов? Часов-секундомера нет, ивзестно только в каком порядке верблюды пришли к финишу в каждом забеге.

 

Если решать задачку "тупо по футбольному", то получается 12 забегов: 5 пятёрок, останется 15 верблюдов = ещё три забега. И так далее. Но если чуть поумнее сделать, то можно уложиться в 8 забегов. Но чувствую, что можно и за 7 попыток решить задачку. Но как именно - пока не понимаю..

 

Верблюды обычные, примерно вот такие:

 

Ой какую старую фотку нашел...

 

Верблюды бегают самостоятельно, технические методы к ним не применяются.

 

И вот ещё хорошая фотка вроде бы из аэропорта Эр-Рияда..

[E.K.]

Задачка решается за 7 забегов, причём логика довольно несложная. Надо было просто сесть и внимательно подумать..

[santax]

7 забегов.

Обозначим верблюдов 1,2,3,..,24,25.

Первые 5 забегов: 1-5, 6-10, 11-15, 16-20, 21-25

Побеждают 1-3, 6-8, 11-13, 16-18, 21-23 (15 верблюдов).

Исключает 4,5,9,10,14,15,19,20,24,25 (10 верблюдов).

6й забег победителей (1,6,11,16,21):

победители 1,6,11

исключаем 16, 21, а также:

17,18 и 22,23 (слабее 16,21), 12,13 (слабее 11).

 

Остаются верблюды 1,2,3,6,7,8,11

1 самая быстрая.

остаются 2,3,6,7,8 - надо найти среди них 2х быстрых

8 исключает, так как она слабее 6 и 7

 

Остаются 2,3,6,7,11 - их отправляем 7м забегом и узнаем 2 место и 3 место по скорости.

[E.K.]

Да, всё верно. Но для более прозрачного понимания я бы разделил верблюдов по буквам:

 

25 верблюдов = "aaaaa bbbbb ccccc ddddd eeeee".

 

Пять заездов по 5 верблюдов. Выясняем их "технические характеристики" ->

 

#1-2-3-4-5 => {a1>a2>a3}, {b1>b2>b3}, {c1>c2>c3}, {d1>d2>d3}, {e1>e2>e3}

 

В шестой заезд берём 5 самых быстрых из каждой группы. Пусть это окажутся {a1>b1>c1}. Если буквы вдруг не совпадут, то простым переименованием всё будет понятно.

 

#6: {a1,b1,c1,d1,e1} - они пробежали, впереди всех a1>b1>c1.

 

Отсюда следует, что все верблюды категорий "d" и "e" проиграли гонку.. Поскольку "a1-b1-c1" быстрее их. По примерно похожим причинам из гонки выбывают верблюды "c2-c3-c4-c5" и "b3-b4-b5" - поскольку:

 => "a1>b1>b2" и "b3" в соревновании делать уже нечего..

 => "a1>b1>c1" и "c2,c3,.." тоже вылетают.

 

Итого, у нас остаётся набор вот таких накачанных верблюдов:

 

{a1>a2>a3, b1>b2, c1}

 

При этом "a1" круче всех и вообще. То есть, это альфа-номер-один. Остаётся выяснить какие две верблюдицы по скорости номер-2 и номер-3.. Но их и осталось только пять:

 

{a2,a3,b1,b2,c1}

 

Между ними проводим конкурс - и вуаля! Первые два победителя = номер-2 и номер-3, и всё на этом. Первые самые быстрые чемпионы = есть!

[E.K.]

Но что-то я чую, что "ответ=7" не является наиболее оптимальным. Кажется мне, что можно найти "вероятностное" решение, где с бОльшей вероятностью три самых-самых верблюда найдутся за 6 забегов. За шесть! И с гораздо меньшим успехом за 8-восемь.

 

Например, такой алгоритм:

 

#1. aaaaa => a1>a2>a3 (остальные два верблюда проиграли сразу).

#2. (a2,bbbb) - второй верблюд из первого заезда и ещё 4 новых. Тут результаты разъезжаются... (но об этом чуть позже, я же про Мексику ещё не все фотки выложил!)

[santax]

Мне кажется, что 6 не получится. Рассмотрим частный случай:

После первых 5 забегов (а они, как мы понимаем, необходимы). Имеем 15 верблюдов a1-3, b1-3, c1-3, d1-3, e1-3. Предположим, что тройка самых быстрых верблюдов это a1-3. Соответственно, возникает новая задача (теоретически верная по моим суждениям):

 

Есть 5 групп по 3 верблюда. Причем, мы знаем в каждой группе какой верблюд самый быстрый и самый медленный. А также известно, что в одной из групп находятся 3 самых быстрых верблюда из всех. Доказать, что одним забегом подтвердить это невозможно.

[E.K.]

Мне почему-то кажется, что можно ещё более оптимально. Вероятностно оптимально: с вероятностью 'p' за 6 забегов, с вероятностью 'q

 

aaaaa (5) bbbb (4) и ещё осталось 16 штук.

 

Забег1: a1>a2>a3 - тройка лидеров, остальных вычёркиваем.

 

Забег2: бегут a2 и bbbb (подмешиваем к 'bbbb' второго верблюда). Возможные результаты:

 

- a2,b1,bbb => остаются четверо: a1>a2>{a3,b1} // кто быстрее a3 или b1 мы не знаем.

- b1,a2,bbb => остаются трое {a1,b1}>a2.

- b1,b2,a2,bb => остаются трое a1, b1>b2.

- b1,b2,b2,a2,b или

- b1,b2,b2,b2,a2 => четверо: a1, b1>b2>b3.

 

То есть, к третьему забегу у нас 3 или 4 лидера и ещё 16 штук. Пойду попробую подумать над этим коктейлем..

[oit]

Я пока тоже так же понял про 7 забегов.

1-5 забег

1-2-3-4-5

6-7-8-9-10

11-12-13-14-15

16-17-18-19-20

21-22-23-24-25

 

6 забег

1-6-11-16-21

17-18

22-23

 

7 забег

1-2-3-6-11

7-8

12-13

[E.K.]

Итак, напоминаю, что: в начале разбили верблюдов на группы aaaaa, bbbb, cccc, dddd, eeee, ffff (пятёрка и пять по четыре = 25).

 

После забега1 остались три верблюда {a1>a2>a3}. Во забеге2 к четвёрке bbbb добавляем второе место из первого забега. То есть, бегут .

 

// в дальнейшем используется запись:

= бегут верблюды под номерами x1,y1 и три верблюда из группы z.

{s1,t1} > {{q1>q2}, r1} = означает, что s1 и t1 больше оставшихся, но кто из них больше друг друга неизвестно, а у остальных q1>q2, но больше или меньше r1 тоже неизвестно. Такая запись понятна?

(p=1/5) = вероятность события 1/5.

 

Итак, в забеге2 бегут . Возможные результаты:

 

- a2,b1,bbb => остаются четверо: a1>a2>{a3,b1} // кто быстрее a3 или b1 мы не знаем. Вероятность события (p=1/5).

- b1,a2,bbb => остаются трое {a1,b1}>a2,      (p=1/5).

- b1,b2,a2,bb => остаются трое a1, {b1>b2},   (p=1/5).
- b1,b2,b2,a2,b или

- b1,b2,b2,b2,a2 => четверо: a1, {b1>b2>b3}.    (p=2/5).

 

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

 

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

 

Забег3. Есть 16 неизвестных по скорости верблюдов и вот такие наборы =>

 

(1) a1>a2>{a3,b1}.

(2) {a1,b1}>a2.

(3) a1, {b1>b2}.

(4) a1, {b1>b2>b3}.

 

Вариант1. Бегут (так наиболее оптимально, остальные попытки можете проверить сами).

Вариант2. Бегут .

Вариант3. Бегут .

Вариант4. Бегут (именно 'b1', если 'b2' то получается вроде бы хуже.. больше верблюдов остаётся).

 

Итак, по резутатам забега-3 получается вот такие лидеры, остальные отсеиваются:

 

Забег3-Вариант1.  a1>a2>{a3,b1}  =>  .

 

a2,c1,c,c,c          => a1>a2>{a3,b1,c1}.  (p=1/25).

c1,a2,c,c,c          => {a1,c1}>a2.             (p=1/25).

c1,c2,a2,cc         => a1,{c1>c2}.             (p=1/25).

c1,c2,c3,**          => a1,{c1>c2>c3}.       (p=2/25).

 

Забег3-Вариант2.  {a1,b1}>a2     =>   .

 

a1,c1,c,c,c          => {a1,b1}>{a2,c1}.     (p=1/25).

c1,a1,c,c,c          => {c1>a1},b1.             (p=1/25). 

c1,c2,a1,cc         => b1,{c1>c2>a1}.       (p=1/25).

c1,c2,c3,**          => b1,{c1>c2>c3}.       (p=2/25).

 

Забег3-Вариант3.  a1, {b1>b2}        =>  .

 

b1,c1,c,c,c          => a1,b1>{b2,c1}.       (p=1/25).

c1,b1,c,c,c          => a1,{c1>b1>b2}.      (p=1/25).  

c1,c2,b1,c,c       => a1,{c1>c2>b1}.       (p=1/25).

c1,c2,c3,**         => a1,{c1>c2>c3}.       (p=2/25).

 

Забег3-Вариант4. a1, {b1>b2>b3}   => .

 

b1,c1,c,c,c          => a1,b1>{{b2>b3},c1}    (p=2/25).

c1,b1,c,c,c          => a1,{c1>b1>b2}.           (p=2/25).

c1,c2,b1,c,c       => a1,{c1>c2>b1}.            (p=2/25).

c1,c2,c3,**         => a1,{c1>c2>c3}.            (p=4/25).

 

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

{x1,y2}>z1 идентично {z1,y2}>x1 // я специально сейчас их сначала переложу, а потом оптимизарую, чтобы лучше видно было:

 

c1,c2,a2,cc         => a1,{c1>c2}.             (p=1/25).

 

c1,a2,c,c,c          => {a1,c1}>a2.             (p=1/25).

 

c1,a1,c,c,c          => {c1>a1},b1.             (p=1/25).     // UPD. Пардон, но это идентично варианту a1,{c1>c2}. Итого = 7 вариантов.

 

c1,c2,c3,**          => a1,{c1>c2>c3}.       (p=2/25).

c1,c2,a1,cc         => b1,{c1>c2>a1}.       (p=1/25).

c1,c2,c3,**          => b1,{c1>c2>c3}.       (p=2/25).

c1,b1,c,c,c          => a1,{c1>b1>b2}.      (p=1/25).  

c1,c2,b1,c,c       => a1,{c1>c2>b1}.        (p=1/25).

c1,c2,c3,**         => a1,{c1>c2>c3}.        (p=2/25).

c1,b1,c,c,c          => a1,{c1>b1>b2}.       (p=2/25).

c1,c2,b1,c,c       => a1,{c1>c2>b1}.        (p=2/25).

c1,c2,c3,**         => a1,{c1>c2>c3}.        (p=4/25).

 

a2,c1,c,c,c          => a1>a2>{a3,b1,c1}.  (p=1/25).

 

a1,c1,c,c,c          => {a1,b1}>{a2,c1}.     (p=1/25).

 

b1,c1,c,c,c          => a1,b1>{b2,c1}.       (p=1/25).

 

b1,c1,c,c,c          => a1,b1>{{b2>b3},c1}    (p=2/25).

 

То есть, остаётся 8 7 вариантов. Но не исключаю, что первые три тоже можно объединить.. Но это надо проверять.

 

(если не лень - проверьте плиз на ошибки в изложении, а я попозже вечером забег4 попробую)

[E.K.]

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

 

aaaaa bbbb ccccc dddd eeeee ff (5-4-5-4-5-2)

 

Бежим A-B, C-D, E, потом добавляем пару F. Получается проще..

 

Заезды AB (#1-2) ==>             Заезды CD (#3-4)  ==>             Заезд E (#5)  ==>

 

a1>a2>{a3,b1}  (p=1/5).     c1>c2>{c3,d1}   (p=1/5).       e1>e2>e3

{a1,b1}>a2     (p=1/5).     {c1,d1}>c2      (p=1/5).

a1, {b1>b2}    (p=1/5).     c1, {d1>d2}     (p=1/5).

a1, {b1>b2>b3} (p=2/5).     c1, {d1>d2>d3}  (p=2/5).

 

Далее надо "умно" подмешать оставшуюся пару 'ff'. "Умный подмес" должен зависить от результатов забегов 'AB' и 'CD'. Например, вот так:

 

Заезд F (#6):

 

(p=1/25)             // что означает, что в первых 4х заездах результаты были A1 и C1, это событие вероятности 1/25.

 

Возможные варианты результата забега (какая из F пришла первой, какая второй - неважно) =>

 

    ff,***         done! => Win: первые три в этом забеге,

                    т.е. за 6 раз мы определяем тройку лидеров с вероятностью: p = 1/25*1/10 = 1/250.

    f,*,f,**       а здесь сложнее..

                     f1,a1/c1,f2,**  done! => Win: первые три. За 6 заездов: p = 1/25*1/15 = 1/375.

                     f1,e1,f2,**         -> надо проверять на e2?f2, т.е. требуется 7я попытка.

 

    f,**,f,*        вылет на +7й кто третий или / или .

    f,***,f         - // - аналогично.

   

    *,f,*,f,*       +7й если первый e1: .

    *,f,**,f         - // -

    **,ff,*         а здесь и далее начинаются вылеты на #8.

 

 

То есть, технически с небольшой вероятностью можно уложиться в 6 забегов. Однако с бОльшей вероятностью будут вылеты на 8й забег. Увы, более оптимальной статистически стратегии, похоже, не существует.

 

Всё на этом про такую задачку. Пора переходить к более приятным.. Например ->

[E.K.]

Любители геометрии есть? Ловите ->

 

На сторонах AB и AD параллелограмма ABCD поставили точки I, J, K, L таким образом, что BI:IJ:JA = DK:KL:LA = 3:5:4. Доказать, что отрезки CI, CJ, CL, CK делят диагональ BD на 5 равных отрезков ->

[E.K.]

Есть "тупой" метод решения: просто подсчитать координаты точек пересечения. Для этого удобнее будет перевернуть картинку и точку C назначить центром (0,0) - так функции прямых будут попроще. Но меня уверяют, что есть красивое решение в уме - без всяких формул. Пока смотрю и не вижу.. Единственное, за что цепляется взгляд, - 3:5:4 это стороны прямоугольного треугольника.

[Борис Прокофьев]

У меня есть версия, но... для доказательства не хватает

1) JL || ВD (Δ AJL подобен Δ ABD по двум пропорциональным сторонам AJ:AB = AL:AD = 4:12 и углу между ними ∠A).

  Поскольку все треугольники из нарезки Δ BCD подобны своим "продолжениям" в Δ B1CD1, то можно доказывать, что B1D1 делится на 5 равных отрезков.

2) Δ AJL подобен Δ BB1J (по двум углам, там все три равны) с коэфф. 4:8 = 1/2. Аналогично Δ AJL подобен Δ DD1L с коэфф. 4:8 = 1/2.

  Откуда следует что Δ-ки B1BJ и LDD1 равны и B1J = LD1 = 2*JL

3) Δ AJL подобен Δ CD1B1 (по двум углам, там все три равны) с коэфф. 4:(4+5+3+5+3) = 4:20 = 1/5

4) Получается что JL = 1/5 * B1D1, а B1J = LD1 = 2*JL = 2/5 * B1D1

5) А вот как показать что красные точки делят B1J и LD1 именно пополам → не пойму... ( 

 

 

UPD. Решение сильно затрудняет похожесть условия задачи на флаг республики Сейшельские острова. 

Мыслительный процесс всякий раз приводит к образу пляжа Source d'Argent...

 

Изменено 11 декабря, 2019 пользователем Борис Прокофьев

[E.K.]

Ой-ай, там всё просто и элементарно, а когда ещё на "Сейшельский флаг" развернули - то вообще всё прозрачно стало. Примерно вот так:

 

BMB1 сравниваем с DAB1, а потом BNB2 с подобным ему DAB2. И всё... // это я в рейсе Париж-Москва - как только ноутбук открыл, так сразу и увидел.

 

Даже лишние чёрточки рисовать не требуется!

 

Светло-серый треугольник подобен нижнему закрашенному. А верхний закрашенный подобен нижнему тёмно-серому. 3-5-4 - всё..

 

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

 

Длина CD = 12 // нам же всё равно какую систему счисления и масштабы использовать

Плюс для удобства будем считать по "сейшельскому флагу".

 

Уравнения прямых:

 

CK: y = bx/(a+3)

CL: y = bx/(a+8)

DB: y = b(x-12)/(a-12)

 

Координаты по 'x' точек:

 

p1: b(x-12)/(a-12) = bx/(a+3)   // 'b' сразу сокращаем.

(x-12)(a+3) = x(a-12)

15x = 12a+36

x1 = 4(a+3)/5

 

p2: b(x-12)/(a-12) = bx/(a+8)

(x-12)(a+8) = x(a-12)

20x = 12(a+8)

x2= 3(a+8)/5

 

Расстояния по оси 'x' между точками: a 4/5(a+3) 3/5(a+8).

 

4/5(a+3) - a = (12 - a) / 5

3/5(a+8) - 4/5(a+3) = 24-12-a / 5 = (12 - a) / 5

 

Всё. Аналогично считаются остальные две точки. А потом и средняя часть.