Может ли правильное рандомизированное решение упасть?

Revision ru1, by antontrygubO_o, 2019-01-25 03:48:18

Просто из интереса:

Допустим, у какой-то задачи есть рандомизированное решение, падающее с вероятностью, не превышающей . Если у нее, скажем, 100 тестов, то вероятность падения на каком-то из них примерно равна . Следовательно, в одном случае из 104 правильное рандомизированное решение может упасть.

Было ли у кого-то подобное? Возможно даже, упавшее решение, перепосланное без изменений, получало АС? Или я где-то ошибаюсь?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian antontrygubO_o 2019-01-25 03:48:18 519 Первая редакция перевода на Русский
en1 English antontrygubO_o 2019-01-25 03:44:24 512 Initial revision (published)