Марафон головоломок! [Конкурс с призами]

[lim0n]

(Решение Задачи №222)

VAL в url=http://dxdy.ru/post470864.html#p470864]сообщении #470864[/url] писал(а):

Задача №222 (с ложным следом)

Бегун, воздух, стихия, гвоздь, рана, смерть, ...
Какого слова не хватает в списке?

Если в список добавить слово ямб, каждая из восемнадцати букв будет использована по два раза.

Задача №300библиотечная серия
${\color[HTML]{00C234} \boxed{\text{РЕШЕНО}}}$ [Первым правильно решил venco тут]

Искал книгу "Лена с ночи", не нашёл. Конечно, опять всё напутал...

(Не мое решение Задачи №299)

См. решение. Кстати, задач там ещё много...

[epros]

(Решение Задачи №297)

venco в сообщении #476566 писал(а):

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

На каждом шаге вероятность выиграть игроку "никто" равна вероятности выиграть любому другому игроку. Поскольку все из N реальных игроков изначально находятся в равных условиях с игроком "никто", а в игре в целом возможен только один из N+1 исходов (либо выиграет кто-то из игроков, либо никто), то вероятность того, что не выиграет никто, равна 1/(N+1).

Хм, или я поспешил?

Задача №301.
${\color[HTML]{00C234} \boxed{\text{РЕШЕНО}}}$ [Первым правильно решил Yu_K тут]

Даны четыре точки на плоскости. Известно, что каждая лежит на своей стороне квадрата. Как начертить этот квадрат?

[Yu_K]

(Решение Задачи №301)

Из картинки ниже понятен подход к построению
и маленькое кино - как разбор возможных вариантов выбора различных пар точек - всего три варианта
http://www.youtube.com/watch?v=weW76PevK6I

Задача №302.
Как рождаются сенсации про Палласово железо. Поздно ночью метеорит, размером с голову, упал в метре от того места, где мы сидели. Хорошо, что с собой был фотоаппарат - вот сфотографировал его - еще горяченький!!! Это не правдивое описание ситуации - какие есть варианты - что это такое? Да в качестве подсказки - объект достаточно холодный, фотография сделана мной неделю назад.


Трудящиеся просили дать пояснения.

(Пояснение к Задаче №297)

Рассмотрим вариант 2 игроков.
Возможные варианты исходов после первого раунда бросков
00
01
10
11
Все варианты равновероятны. Поэтому можем записать условие (уравнение) на определение вероятности $P_2$ - того что никто не выиграл в случае двух игроков.

$$P_2=\frac{1}{4}+\frac{1}{4}P_2$$

отсюда находим $P_2$.
Вариант 3 игроков - имеем варианты исходов
000
001
010
011
100
101
110
111
Аналогичное уравнение имеет вид -

$$P_3=\frac{1}{8}+\frac{1}{8}P_3+C^{2}_{3}\frac{1}{8}P_2$$

- отсюда находим $P_3$ при уже известном $P_2$. И т.д. получаем формулу приведенную ранее без объяснений.

А вот вопрос - чему равен предел $P_n$ при $n$ стремящемся к бесконечности?

lim0n в сообщении #476915 писал(а):

(Не мое решение Задачи №299)

+
Действительно google рулит - если взять в кавычки последовательность - то сразу выкатываемся на решение. Меня поразило тогда - что столько народу дали правильный ответ на такой бесконечно нереальный (ИМХО) в плане получения ответа вопрос. Но зато фавориты Ponder This - скажем Балакришнан и др. - не стали участвовать в решении этой задачи - просто вышли из игры на этом вопросе. Наверное теперь здесь эту задачу дисквалифицируют.

По задаче про разрезание окружности - просто интегрируем производные от функций распределения длин самого короткого и самого длинного интервалов, приведенные во втором томе В.Феллера. Можно усложнить задачу и поставить вопрос о нахождении средних значений всех промежуточных интервалов - тоже красивый ответ.

Задача про сопротивление платоновых тел описана на сайте - ссылку на который привел выше lim0n - там же где про черную кошку - кому интересно поищите - задача была там в 2007 году - принцип решения основан на симметрии.

[venco]

Yu_K в сообщении #476370 писал(а):

(Решение Задачи №259)

Такой вариант $\sqrt{7}+\sqrt{3}$
если правильный - могу привести картинку

Проверил - неправильно.

-- Ср авг 24, 2011 00:47:29 --

Yu_K в сообщении #476602 писал(а):

venco
По поводу упрощения ответа
[url]http://www.wolframalpha.com/input/?i=1%2FN*sum+%28-1%29^%28k%2B1%29%2Fk*binom%28N%2Ck%29+from+k%3D1+to+N[/url]
т.е. через производную от http://mathworld.wolfram.com/DigammaFunction.html или
http://mathworld.wolfram.com/HarmonicNumber.html через гармонические числа можно записать ответ в рекуррентной форме - матожидание длины максимума будет

$$M_n=\frac{1}{n^2}+M_{n-1}\frac{n-1}{n}, M_1=1$$

Рекуррентную форму принять не могу. Давайте закрытую форму в виде конечной суммы.

-- Ср авг 24, 2011 00:49:05 --

Yu_K в сообщении #476692 писал(а):

(Решение Задачи №164)

Задача №164
Найти сопротивление между соседними вершинами всех пяти платоновых тел, если каждое ребро имеет единичное сопротивление.
тетраэдр -- 1/2
куб -- 7/12
октаэдр -- 5/12
додекаэдр -- 19/30
икосаэдр -- 11/30

Правильно.
Жалко, что нашли в интернете, а не самостоятельно решили.

-- Ср авг 24, 2011 00:51:20 --

Yu_K в сообщении #476692 писал(а):

(Решение Задачи №297)

Задача №297.
N игроков играют в игру с призом.
Каждый бросает честную монету, и если орёл выпадает ровно у одного, то он выигрывает приз, и игра заканчивается. Иначе все у кого выпала решка, выбывают из игры, а оставшиеся повторяют броски. Если у всех оказалась решка, то приз не выигрывает никто. Какова вероятность того, что приз никто не выиграет?

$$P_n=\frac{1+\sum_{k=2}^{n-1}\binom{k}{n}P_k}{2^n-1}$$

$$P_2=\frac{1}{3}$$

Опять же, рекуррентная формула не принимается - она довольно очевидна.

-- Ср авг 24, 2011 00:52:19 --

epros в сообщении #477018 писал(а):

(Решение Задачи №297)

venco в сообщении #476566 писал(а):

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

На каждом шаге вероятность выиграть игроку "никто" равна вероятности выиграть любому другому игроку. Поскольку все из N реальных игроков изначально находятся в равных условиях с игроком "никто", а в игре в целом возможен только один из N+1 исходов (либо выиграет кто-то из игроков, либо никто), то вероятность того, что не выиграет никто, равна 1/(N+1).

Хм, или я поспешил?

Неправильно.

[Yu_K]

(Решение Задачи №259)

venco в сообщении #477339 писал(а):

Yu_K в сообщении #476370 писал(а):
(Решение Задачи №259)
Проверил - неправильно.

Согласен $\sqrt19$ будет поменьше для октаэдра, чем $\sqrt7+\sqrt3$ .

Головоломку теперь должен.

По задаче 156.

venco в сообщении #477339 писал(а):

Рекуррентную форму принять не могу. Давайте закрытую форму в виде конечной суммы.

Через гармонические числа - там выше была ссылка на вольфрам - и после графиков высвечивается формула в виде конечной суммы. Почему-то прямая ссылка на вольфрам сюда в форум не вставляется - но можно скопировать и посмотреть через браузер. Конкретно формулу запишем здесь.
Матожидание максимальной доли окружности при случайном ее разбиении на N интервалов равно

$$M_N=\frac{1}{N}\sum_{k=1}^{N}\frac{1}{k}$$

(Оффтоп)

Красивая задача - по-началу думал, что для двух интервалов появится "золотое сечение".

[venco]

Yu_K в сообщении #477457 писал(а):

(Решение Задачи №259)

venco в сообщении #477339 писал(а):

Yu_K в сообщении #476370 писал(а):
(Решение Задачи №259)
Проверил - неправильно.

Согласен $\sqrt19$ будет поменьше для октаэдра, чем $\sqrt7+\sqrt3$ .

Теперь правильно.

Yu_K в сообщении #477457 писал(а):

Головоломку теперь должен.

По задаче 297.

venco в сообщении #477339 писал(а):

Рекуррентную форму принять не могу. Давайте закрытую форму в виде конечной суммы.

Через гармонические числа - там выше была ссылка на вольфрам - и после графиков высвечивается формула в виде конечной суммы. Почему-то прямая ссылка на вольфрам сюда в форум не вставляется - но можно скопировать и посмотреть через браузер. Конкретно формулу запишем здесь.
Матожидание максимальной доли окружности при случайном ее разбиении на N интервалов равно

$$M_N=\frac{1}{N}\sum_{k=1}^{N}\frac{1}{k}$$

И здесь правильно. Только задача не 297, а 156.

[venco]

(Решение Задачи №298)

Yu_K в сообщении #476692 писал(а):

Задача №298.

Ломаная на плоскости строится из произвольно ориентированных отрезков единичной длины. Число звеньев наращивается до первого самопересечения ломаной с самой собой. Определить среднее число звеньев такой ломаной.

Не представляю, как эту задачу можно решить аналитически, поэтому даю численное решение:

Используется синтаксис C++

typedef complex<double> P;
const double EPS = 1e-10;

P pp[10000];

inline P random_shift&#40;&#41;
{
    return polar&#40;1., mtr.get_double&#40;2*M_PI&#41;&#41;;
}

inline double dot&#40;const P& p1, const P& p2&#41;
{
    return p1.real&#40;&#41;*p2.real&#40;&#41; + p1.imag&#40;&#41;*p2.imag&#40;&#41;;
}

inline bool intersects&#40;const P* pp1, const P* pp2&#41;
{
    P s1 = pp1[0], d1 = pp1[1]-s1, r1&#40;d1.imag&#40;&#41;, -d1.real&#40;&#41;&#41;;
    P s2 = pp2[0], d2 = pp2[1]-s2, r2&#40;d2.imag&#40;&#41;, -d2.real&#40;&#41;&#41;;
    P ds = s2-s1;
    double u = dot&#40;ds, r2&#41;/dot&#40;d1, r2&#41;;
    if &#40; u <= EPS || u >= 1-EPS &#41; return 0;
    double v = dot&#40;ds, r1&#41;/dot&#40;d2, r1&#41;;
    if &#40; v >= -EPS || v <= -1+EPS &#41; return 0;
    //TR&#40;A&#40;pp1,2&#41;|A&#40;pp2,2&#41;&#41;;
    return 1;
}

int random_len&#40;&#41;
{
    pp[0] = P&#40;0, 0&#41;;
    pp[1] = P&#40;1, 0&#41;;
    forNF &#40; i, 1, 10000 &#41; {
        pp[i+1] = pp[i] + random_shift&#40;&#41;;
        forN &#40; j, i &#41; {
            if &#40; intersects&#40;pp+i, pp+j&#41; &#41; {
                //TR&#40;A&#40;pp,i+2&#41;&#41;;
                return i+1;
            }
        }
    }
    abort&#40;&#41;;
}

void main&#40;&#41;
{
    NTR = 100;
    const int count = 1000000000;
    double sum = 0, sum2 = 0;
    forN &#40; i, count &#41; {
        int v = random_len&#40;&#41;;
        sum += v;
        sum2 += v*v;
    }
    double avg = sum/count;
    double dev = sqrt&#40;sum2/count-avg*avg&#41;;
    double err = dev/sqrt&#40;count&#41;;
    TR&#40;avg|err|dev&#41;;
}
 

avg err dev = 8.88636 0.000165979 5.24872

Получается чуть меньше $\frac {80}9$.
Первое число - среднее количество сегментов, второе - оценка погрешности, третье - среднеквадратичное отклонение.

(Решение Задачи №300)

lim0n в сообщении #476915 писал(а):

Задача №300библиотечная серия
Искал книгу "Лена с ночи", не нашёл. Конечно, опять всё напутал...

Камасутра.

Задача №303.
${\color[HTML]{00C234} \boxed{\text{РЕШЕНО}}}$ [Первым правильно решил VAL тут]

Клеточное поле 2хN раскрашено в два цвета - синий и красный, так что есть путь по синим клеткам от одной короткой стороны до другой. Сколько существует варантов раскраски?

[VAL]

(Решение Задачи №303)

venco в сообщении #477510 писал(а):

Задача №303.
Клеточное поле 2хN раскрашено в два цвета - синий и красный, так что есть путь по синим клеткам от одной короткой стороны до другой. Сколько существует варантов раскраски?

Пусть $a_n$ - число допустимых полосок длины $n$, заканчивающихся двумя синими клетками, а $b_n$ - одной синей клеткой.
Ясно, что $a_1=1, \ b_1=2, \ a_{n+1}=a_n+b_n, \ b_{n+1}=2a_n+b_n$.
Общее число вариантов - $f_n=a_n+b_n$.
Или $f_1=3, \ f_2=7, \ f_{n+1}=2f_n+f_{n-1}$.
Конечно, можно избавиться от рекуррентности, но там всякие корни из двойки вылезают...

Задача №304.
${\color[HTML]{00C234} \boxed{\text{РЕШЕНО}}}$ [Первым правильно решил venco тут]

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

[Psw]

(Решение Задачи №303)

venco в сообщении #477510 писал(а):

Задача №303.
Клеточное поле 2хN раскрашено в два цвета - синий и красный, так что есть путь по синим клеткам от одной короткой стороны до другой. Сколько существует варантов раскраски?

$S(N)=2S(N-1)+S(N-2)$ при $S(1)=3$, $S(2)=7$

или $S(N)=\frac 12 ( (1-\sqrt{2})^{N+1}+(1+\sqrt{2})^{N+1}))$
А если обязательно наличие 2-х цветов (полностью синяя раскраска не допустима), то еще 1 надо вычесть

Задача №305.
${\color[HTML]{00C234} \boxed{\text{РЕШЕНО}}}$ [Первым правильно решил VAL тут]


Позиция возникла после 5-ого хода черных. Привести ходы.
А можно ли получить позицию после 4-ого хода черных? Если да, то как.

P.S. Опоздал на 2 минуты
Номер задачи переправил на след., а решение уже не буду убирать.

[VAL]

venco в сообщении #475758 писал(а):

(Решение Задачи №234)

VAL в сообщении #471032 писал(а):

Задача №234

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

"синус" на "нутро". Каждое слово содержит очередную букву алфавита и ни одной буквы до неё.

(Решение Задачи №287)

VAL в сообщении #475755 писал(а):

Задача №287

В некоторые клетки квадрата $7\times7$ положили по одной монетке. Достоинство каждой монеты 1, 2 или 5 рублей. Сумма денег в каждом квадрате $2\times2$ - 7 рублей. Какой наименьшей суммой денег можно ?

69, например, так:

---------
| 1 1 1 |
|1515151|
| 1 1 1 |
|1515151|
| 1 1 1 |
|1515151|
| 1 1 1 |
---------

Оба раза верно.

-- 25 авг 2011, 08:54 --

lim0n в сообщении #476007 писал(а):

(Решение Задачи №249)

VAL в сообщении #471952 писал(а):

Задача №249
Интересно, уйдет ли из употребления первая часть этого слова, в связи известным переименованием?
Ну а вторая часть, точно уходит. Именно в связи с этим все его и знают.
Мы привыкли ссылаться на на то, что наш - какой-то особенный.

Менталитет. По второму пункту -- роман Т.Сёмушкина и одноимённый художественный фильм "Алитет уходит в горы" (1949).

Верно!

-- 25 авг 2011, 08:58 --

lim0n в сообщении #475993 писал(а):

(Решение Задачи №195)

VAL в сообщении #469695 писал(а):

Задача №195
Если к этому направлению добавить союз, оно сразу превратится в крупного переводчика.

Western Union -- система денежных переводов.

Верно!

-- 25 авг 2011, 08:59 --

lim0n в сообщении #476915 писал(а):

(Решение Задачи №222)

VAL в url=http://dxdy.ru/post470864.html#p470864]сообщении #470864[/url] писал(а):

Задача №222 (с ложным следом)

Бегун, воздух, стихия, гвоздь, рана, смерть, ...
Какого слова не хватает в списке?

Если в список добавить слово ямб, каждая из восемнадцати букв будет использована по два раза.

Верно!

[VAL]

(Решение задачи №305)

Psw в сообщении #477561 писал(а):

Задача №305.

Позиция возникла после 5-ого хода черных. Привести ходы.
А можно ли получить позицию после 4-ого хода черных? Если да, то как.

За пять, например, так:
1. Ng1-f3 d7-d5
2. Nf3-d4 Ke8-d7
3. Nd4-b5 Ng8-f6
4. Nb5-d6 Nf6-e8
5. Nd6xe8 Kd7xe8
А за четыре, не получится: Белый конь не может пробить черного ни на f6, ни на h6, ни на g8. Значит, погибший черный конь должен сделать не менее двух ходов. Еще один ход нужно сделать пешкой (пешка не могла взять белого коня, т.к. не было второго взятия) и два - фигурой побившей белого коня.

Задача №306.
Замените каждое из слов на то, которое я задумал прежде, чем написал слова, которые вы видите: альбатрос, банда, батон, болт, порция, трусы, шпиц.

[Psw]

VAL в сообщении #477581 писал(а):

(Решение задачи №305)

Psw в сообщении #477561 писал(а):

Задача №305.

Позиция возникла после 5-ого хода черных. Привести ходы.
А можно ли получить позицию после 4-ого хода черных? Если да, то как.

За пять, например, так:
1. Ng1-f3 d7-d5
2. Nf3-d4 Ke8-d7
3. Nd4-b5 Ng8-f6
4. Nb5-d6 Nf6-e8
5. Nd6xe8 Kd7xe8
А за четыре, не получится: Белый конь не может пробить черного ни на f6, ни на h6, ни на g8. Значит, погибший черный конь должен сделать не менее двух ходов. Еще один ход нужно сделать пешкой (пешка не могла взять белого коня, т.к. не было второго взятия) и два - фигурой побившей белого коня.

Нет

[VAL]

Psw в сообщении #477614 писал(а):

VAL в сообщении #477581 писал(а):

(Решение задачи №305)

Psw в сообщении #477561 писал(а):

Задача №305.

Позиция возникла после 5-ого хода черных. Привести ходы.
А можно ли получить позицию после 4-ого хода черных? Если да, то как.

За пять, например, так:
1. Ng1-f3 d7-d5
2. Nf3-d4 Ke8-d7
3. Nd4-b5 Ng8-f6
4. Nb5-d6 Nf6-e8
5. Nd6xe8 Kd7xe8
А за четыре, не получится: Белый конь не может пробить черного ни на f6, ни на h6, ни на g8. Значит, погибший черный конь должен сделать не менее двух ходов. Еще один ход нужно сделать пешкой (пешка не могла взять белого коня, т.к. не было второго взятия) и два - фигурой побившей белого коня.

Нет

Тогда так:

(Решение задачи №305)

1. Ng1-f3 d7-d5
2. Nf3-d4 Ng8-f6
3. Nd4-c6 Nf6-d7
4. Nc6xb8 Nd7xb8

Задача №307.

Замкните цикл:
гора - хлеб - вид - угар - лодка - кожа - позор - сом - челн - ?

[Psw]

VAL в сообщении #477668 писал(а):

Psw в сообщении #477614 писал(а):

VAL в сообщении #477581 писал(а):

(Решение задачи №305)

За пять, например, так:
1. Ng1-f3 d7-d5
2. Nf3-d4 Ke8-d7
3. Nd4-b5 Ng8-f6
4. Nb5-d6 Nf6-e8
5. Nd6xe8 Kd7xe8
А за четыре, не получится: Белый конь не может пробить черного ни на f6, ни на h6, ни на g8. Значит, погибший черный конь должен сделать не менее двух ходов. Еще один ход нужно сделать пешкой (пешка не могла взять белого коня, т.к. не было второго взятия) и два - фигурой побившей белого коня.

Нет

Тогда так:

(Решение задачи №305)

1. Ng1-f3 d7-d5
2. Nf3-d4 Ng8-f6
3. Nd4-c6 Nf6-d7
4. Nc6xb8 Nd7xb8

Теперь верно.

(Оффтоп)

За 5 ходов можно разными способами, мне, например, симпатичен такой - 1. Кf3 Kf6 2. Ke5 Kg4 3. K:g4 d5 4. Лg1 C:g4 5. Лh1 Cc8, ну или Kb1-a3-b1 вместо ходов ладьей.
А за 4 - верно про четность ходов коней g1 и b8, но это может быть и 0 у коня b8

[VAL]

Psw в сообщении #477679 писал(а):

(Оффтоп)

А за 4 - верно про четность ходов коней g1 и b8, но это может быть и 0 у коня b8

(Оффтоп)

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