Регистрация Спросить otvet5GPT
waves24
07.09.2021 01:24
Математика
Есть ответ 👍

Помагите если сможите​

133
259
Посмотреть ответы 1

Ответы на вопрос:

temirhanarmy
temirhanarmy
4,4(55 оценок)

Переформулируем. Пусть дано 200 пар чисел: (x_{1},y_{1}), (x_{2},y_{2}),\;...,\; (x_{200},y_{200}), причем каждое из чисел взято в отрезке [1,\; 100]. Требуется доказать, что найдутся две пары чисел (x_{i},y_{i}) и (x_{j},y_{j}), такие что x_{i}x_{j} и y_{i}y_{j} (по сути, x,y — координаты фишки на доске).

Доказательство:

Предположим обратное. Расставим пары по убыванию первого числа (то есть числа x). Внутри групп с одинаковым первым числом проведем обратную операцию: расставим числа по возрастанию второго числа (y). Например, если размеры доски 4\times 4, а расставлено 7 фишек, то подошла бы следующая расстановка:

(4,1)\\(4,2)\\(3,2)\\(3,3)\\(2,3)\\(2,4)\\(1,4)

Понятно, что такая расстановка возможна. Действительно, если это не так, то найдется число y_{i}, причем число y_{j} стоит выше числа y_{i}. Это противоречит предположению.

Пусть k — число переходов числа x на более низкое (в вышеприведенном примере таких переходов 3: с 4 на 3, с 3 на 2, с 2 на 1). Заметим, что числа y могут повторяться не более одного раза. Внутри групп они строго возрастают. Поэтому последнее число не меньше 200-k. При этом, очевидно, 200-k\leq 100 \Leftrightarrow k\geq 100. С другой стороны, переходов не больше чем 100-1=99 (спуск от 100 до 1). Противоречие, которое завершает доказательство.

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Математика

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

    otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.

Подпишись на наш телеграмм канал

GTP TOP NEWS