Архив задач олимпиады по математике и криптографии
Круговой "морской бой"
Аня с Борей играют в «морской бой» по следующим правилам: на окружности выбираются 29 различных точек, пронумерованных по часовой стрелке натуральными числами от 1 до 29. Аня рисует корабль – произвольный треугольник с вершинами в этих точках. Боря (не зная расположение корабля Ани) производит «выстрел»: он называет два различных натуральных числа k и m от 1 до 29, и, если отрезок с концами в точках с номерами k и m, совпадает с одной из сторон треугольника Ани, то корабль считается «раненым». Сможет ли Боря, играя обдуманно, гарантированно «ранить» корабль, где бы Аня его ни расположила, сделав не более 134 выстрелов?
Всего имеется C329=3654 различных треугольников. Один выстрел «ранит» 27 треугольников. Сделав 134 выстрела, удастся «ранить» не более 134∙27=3618 треугольников. Так как C329>134∙27, то 134 выстрелов не хватит, чтобы гарантированно «ранить» корабль.