| Почти доказательство :-) ID:46768 ответ на 46763 |
Пт, 2 мая 2003 00:00 [#] |
|
| Jack Daw |
|
 (иконки IM)
Форумы Покер.ру
|
|
Всем привет.
Да, Миша, ты оказался совершенно прав, указывая на пробелы в предлагаемом мной
методе. "На любой сложный вопрос есть простой неправильный ответ" 
Тем не менее, попробую обосновать свою точку зрения. Я также не пылаю большой любовью
симплекс-методу (что обусловлено, скорее, стилем преподавания в вузе, чем, собственно,
дисциплиной), поэтому предложенное доказательство построено на логических рассуждениях и
стандартных методах матанализа.
Докажем (Утверждение 1), что для любого конкрентого бокса приращение МО при опускании
ТЕКУЩЕГО билета больше, чем приращение МО при опускании в него СЛЕДУЮЩЕГО билета.
Иными словами, что:
(OurN+1)/(N+1) - OurN/N > (OurN+2)/(N+2) - (OurN+1)/(N+1), где OurN и N - натуральные числа,
причем N >= OurN.
(OurN+1)/(N+1) - OurN/N - (OurN+2)/(N+2) + (OurN+1)/(N+1) > 0
Опуская промежуточные преобразования, получаем:
(OurN*N + 2*N - 2*OurN) / N*(N+1)*(N+2) > 0
Очевидно, что числитель и знаменатель всегда больше 0. (т.к. N >= OurN), следовательно, и сама
дробь тоже всегда больше 0 при натуральных OurN и N.
Утверждение 1 доказано.
Теперь докажем (Утверждение 2), что, следуя предложенному в моем предыдущем посте
алгоритму, мы найдем OurN маскимально возможных приращений, из всех, которые только могут
возникнуть на любом из боксов при опускании неограниченого количества билетов в течениие
неограниченого времени.
Доказательство от противного. Согласно алгоритму ("рассчитать (N - OurN) / (N*N + N) для
каждого бокса и опустить туда, где f(n) -максимально."), мы находим для шага i максимальное
возможное приращение МО на данный момент времени.
Предположим, что на некоем шаге 'x' на каком-то из боксов 'b1' существует некое приращение МО
(delta MO(x,b1)), которое больше, чем мы нашли на на шаге 'i' на боксе 'b2' (delta MO(i,b2)). Тогда:
delta MO(x,b1) > delta MO(i,b2)
Так как, согласно нашему алгоритму, delta MO(i,b2) максимально на шаге i, то delta MO(i,b2) >=
delta MO(i,b1).
Следовательно,
delta MO(x,b1) > delta MO(i,b1), причем, x>i.
Это противоречит Утверждению 1, следовательно, сделанное нами предположение неверно.
Не существует в дальнейшем такого приращения МО, которое больше, чем найденное в данный
момент.
Вышеизложенное справедливо для всех i на диапазоне 1...OurN.
Утверждение 2 доказано.
Пусть есть оптимальное решение Sопт.
Его можно представить в виде суммы прирашений МО, полученных при последовательном
опускании билетов в ящики:
Sопт = delta MO(1,b1) + delta MO(2,b2) + ...+ delta MO(OurN,bOurN)
Расставим слагаемые по убыванию и сравним эту сумму с суммой прирашений, полученых следуя
нашему алгоритму, где delta MOmax(i) - прирашение МО, максимальное на i шаге:
Sалг = delta MOmax(1) + delta MOmax(2) + ...+ delta MOmax(OurN).
Количество слагаемых одинаковое (OurN), причем (из Утверждения 2) каждое i-е слагаемое из
Sалг больше или равно i-му слагаемому из Sопт, следовательно Sалг >= Sопт. По условию Sопт
есть оптимальное решение.
Следовательно Sалг =Sопт, что и требовалось доказать.
Best regards.
|
|
|