2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Стеклянные шарики
Сообщение26.09.2007, 22:06 
Заслуженный участник


14/01/07
787
Вспомнилась симпатичная задача на нахождение оптимальной стратегии:

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

Одна попытка - это одно бросание одного шарика с какого-то этажа. Если шарик после бросания не разбился, то он сохраняет все свои свойства и его можно использовать в дальнейшем; разбившийся шарик из игры выбывает. Если шарик разбивается при бросании с этажа номер n, то он разобьется и при бросании с этажа номер n+1. Шарики могут оказаться и небьющимися.

 Профиль  
                  
 
 
Сообщение26.09.2007, 22:16 
Заслуженный участник


09/02/06
4342
Москва
Можно за 19. Пробуем бросать с 10-гоб 20-го, c 100-го (с шагом 10). Если шарик разбился, на 10k, то бросаем второй с 10k-9,10k-8,... (c шагом 1).

 Профиль  
                  
 
 
Сообщение26.09.2007, 23:10 
Заслуженный участник
Аватара пользователя


01/03/06
13244
Москва
А почему эта стратегия является наилучшей? Конечно, если заранее предполагать, что можно действовать только так: разбить все этажи на группы последовательных этажей, и в каждой группе начинать проверку с верхнего этажа, то нетрудно понять, что указанное Рустом разбиение - оптимально. Но почему нет другой, ещё более оптимальной стратегии?

Добавлено спустя 14 минут 55 секунд:

И что означает эта фраза:
neo66 писал(а):
Шарики могут оказаться и небьющимися.
?

 Профиль  
                  
 
 
Сообщение26.09.2007, 23:16 
Заслуженный участник


14/01/07
787
19 - много.
Небьющиеся - означает: неразбивающиеся никогда :)

 Профиль  
                  
 
 
Сообщение26.09.2007, 23:21 
Модератор
Аватара пользователя


11/01/06
5419
Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

 Профиль  
                  
 
 
Сообщение26.09.2007, 23:27 
Заслуженный участник
Аватара пользователя


01/03/06
13244
Москва
neo66 писал(а):
Небьющиеся - означает: неразбивающиеся никогда
Спасибо, сейчас запишу, а то я все время забываю смысл этого термина. :oops:

 Профиль  
                  
 
 
Сообщение27.09.2007, 06:05 
Заслуженный участник
Аватара пользователя


21/12/05
5655
Новосибирск
Есть и обобщение: N этажей и n шариков.

 Профиль  
                  
 
 
Сообщение27.09.2007, 08:42 
Заслуженный участник


09/02/06
4342
Москва
maxal писал(а):
Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

Более оптимально стратегия, m, 2m-1, 3m-3,...(k+1)(m-k/2)>N. Отсюда максимальное количество ходов m>(N/(k+1)+k/2). Минумум по k получается $m=[\frac{\sqrt{8N+1}+1}{2}]$

 Профиль  
                  
 
 
Сообщение27.09.2007, 10:29 
Заслуженный участник


14/01/07
787
Эта задача предлагалась в свое время на вступительных экзаменах в НМУ. Хороша, а?

 Профиль  
                  
 
 
Сообщение27.09.2007, 10:48 
Заслуженный участник


09/02/06
4342
Москва
Для n шариков ответ получается - количества шагов равна m, где C(m,n)<=N<C(m+1,n) начиная с некоторого N>N0.

 Профиль  
                  
 
 
Сообщение27.09.2007, 11:00 
Заслуженный участник
Аватара пользователя


21/12/05
5655
Новосибирск
Нет, не так, но ключ у Вас есть.

 Профиль  
                  
 
 
Сообщение27.09.2007, 11:36 
Заслуженный участник


09/02/06
4342
Москва
bot писал(а):
Нет, не так, но ключ у Вас есть.

Почему не так. При n=1, очевидно, что m=N, согласуется с указанной формулой. Оно согласуется и при n=2 (хотя для индукции это не обязательно).
Докажем по индукции. Пусть это верно для N>C(2n,n)=N0 для всех n, что минимальное число ходов определяется из указанного свойства. Тогда вычисляем максимальное значение N для которого достаточно m ходов как сумму C(m,n)+C(m-1,n)+...=C(m+1,n).
Правда здесь надо биномиальные коэффициенты надо заменить функциями f(m,n) удовлетворяющим условиям f(1,n)=1, n>=1, f(m+1,n)=f(m,n-1)+f(m,n).

 Профиль  
                  
 
 
Сообщение27.09.2007, 14:17 
Заслуженный участник


14/01/07
787
Руст писал(а):
maxal писал(а):
Старая задача. По слухам с интервью в Microsoft.

А правильный ответ здесь: 14.

Более оптимально стратегия, m, 2m-1, 3m-3,...(k+1)(m-k/2)>N. Отсюда максимальное количество ходов m>(N/(k+1)+k/2). Минумум по k получается $m=[\frac{\sqrt{8N+1}+1}{2}]$


Это не более оптимальная стратегия, а просто оптимальная.
Что касается обобщений - это уже чистая техника и ничего нового не привносит. Забавно, правда, что 7 шариков (для 100 этажей) - минимизирует число испытаний.

 Профиль  
                  
 
 
Сообщение27.09.2007, 14:28 
Заслуженный участник


09/02/06
4342
Москва
neo66 писал(а):
Что касается обобщений - это уже чистая техника и ничего нового не привносит. Забавно, правда, что 7 шариков (для 100 этажей) - минимизирует число испытаний.

То, что k шариков минимизирует (для 2^{k-1}<=N<2^k этажей) очевидна делением попалам.
Общий ответ для количества шагов m получается из условия
$f(m-1,n)<N<=f(m,n),$ где
$$f(m,n)=C_{m+n-1}^{n}.$$

 Профиль  
                  
 
 
Сообщение27.09.2007, 16:43 
Заслуженный участник
Аватара пользователя


01/03/06
13244
Москва
neo66 писал(а):
Это не более оптимальная стратегия, а просто оптимальная.
А как это доказать?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group