QUOTE(sh_ @ 23.11.2010, 11:12)
Кстати, про доказательство оптимальности в задаче не спрашивается.
Требование док-ва оптимальности следует из вопроса задачи. Если вы привели не оптимальную стратегию то получите неверный ответ. А обоснование верности вашего ответа - само собой разумеющееся. В задачах, в которых не надо док-ва оптимальности, это прописывается в условии.