Предположим, что после стирания 25 отрезков на доске остаются максимально возможное количество отрезков, то есть 24. Обозначим эти отрезки как AB1, AB2, AB3, ..., АВ24, где А и В - точки, соответствующие концам отрезка.
Всего на доске было отмечено 50 точек. Если из них не выбраны 25 точек, соединенных отрезками, то должны остаться 25 точек, несоединенных ни с одной из выбранных ранее точек. Обозначим эти точки как С1, С2, С3, ..., С25.
Поскольку на доске было всего 50 точек, это означает, что точки А и В были соединены отрезками с среди выбранных точек. Но по условию они не выбраны. Значит, наше предположение осталось невыполненным. Верно только, что осталось меньше 24 отрезков.
Рассмотрим дополнение предположенной ситуации. Поскольку отрезки AB1, AB2, ..., АВ24 не были стерты, значит, все 50 точек можно разделить на две дизъюнктные группы:
- Группа А, состоящая из точек, соединенных отрезками с точками А и В: А, В, A1, B1, A2, B2, ..., A24, B24;
- Группа С, состоящая из оставшихся точек, не соединенных отрезками с точками А и В: С1, С2, ..., С25.
Поскольку каждая пара точек из одной группы не соединена отрезком, то каждая тройка точек из А - B1 - С должна образовывать треугольник, не содержащий других точек. Или, другими словами, для каждого А подходит только одна точка С.
Поскольку точек А и В всего две, а точек С 25, то как минимум две точки С должны соответствовать одной точке А. По принципу Дирихле (принципу ящиков и шаров) это означает, что какие-то две точки С должны соединены отрезком.
Таким образом, мы доказали, что при любом изначальном количестве отрезков, стертых Васей, всегда найдутся 25 точек, любые две из которых соединены отрезком.