на доске 100 на 100 стоит 200 фишек. Докажите что найдутся две фишки одна из которых строго правее и строго выше другой

207

338

Посмотреть ответы 3

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

danielfokin

Математика

4,6(38 оценок)

Допустим таких конфигураций не существует.

Тогда не существует и аналогичных конфигураций "строго левее и строго выше" и так далее, потому что если бы они были, мы бы могли их поворотами доски или отражениями привести к конфигурации "строго правее и строго выше"

Значит координаты любых двух фишек на нашей доске не могут быть обе различными. Значит фишки максимум занимают одну вертикаль и одну горизонталь, но так можно разложить лишь 199 фишек. А у нас 200. Значит, мы получаем противоречие исходному предположению.

dianadalla

Математика

4,4(23 оценок)

Переформулируем. Пусть дано 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 — координаты фишки на доске).

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

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

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

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

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

vikulka1488

Математика

4,4(83 оценок)

Последняя правка сделана 2 месяцев назад участником worobiew крестьянская война наблюдать за этой страницей крестьянская война или крестьянское восстание — массовые выступления крестьян против феодалов, приобретающие масштабы общегосударственной гражданской войны. в за пределами россии обычно применяется только к крестьянской войне (bauernkrieg): крестьянская война в китае (874—901) крестьянская война в эстонии (1343—1345) — эстонское национально-освободительное движение за освобождение страны от германско-датского владычества. крестьянская война в германии — народное восстание в центральной европе, прежде всего, на территории священной римской империи в 1524—1526 годах. крестьянская война в китае (1628—1647) крестьянская война в швейцарии крестьянская война в бразилии — крестьянское восстание в южной бразилии, развернувшееся в