На клетчатой бумаге по линиям сетки выделили прямоугольник 20×25 клеток. В нем отметили все узлы, в том числе и лежащие на его границе. Какое наибольшее число отмеченных узлов можно выбрать так, чтобы никакие три из них не являлись вершинами прямоугольного треугольника?

задан 8 Дек '13 7:47

Что-то долго на задачу нет ответа. Разве число 45 не устраивает?

(8 Дек '13 17:54) Urt
10|600 символов нужно символов осталось
2

Расположим точки с правого и верхнего края, не считая угловой вершины. Их будет 20+25=45. Большее количество расположить нельзя. Действительно, если $%P$% -- одна из выделенных точек, то на её горизонтали и вертикали не могут одновременно находиться отмеченные точки $%A$% и $%B$%: в противном случае возникнет прямоугольный треугольник $%ABP$%. Тем самым, через каждую отмеченную точку можно провести горизонтальную или вертикальную прямую, на которой никаких других отмеченных точек больше нет, и поэтому проведённые нами прямые не повторяются.

Всего можно провести 21+26=47 прямых, откуда следует, что отмеченных точек не больше 47. Эту оценку можно улучшить, рассуждая так: если мы провели все горизонтальные прямые, то на каждой из них ровно по одной отмеченной точке, и тогда точек всего 21. Значит, какую-то из горизонталей мы не проводили. Аналогично насчёт вертикалей -- там тоже хотя бы одна из них не проводилась (если точек не 26). В итоге мы провели не более 45 прямых, и точек тем самым не более 45. Ответом будет число 45.

ссылка

отвечен 8 Дек '13 18:25

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,011

задан
8 Дек '13 7:47

показан
2277 раз

обновлен
8 Дек '13 18:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru