ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 124]      



Задача 79292

Темы:   [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Касательные к сферам ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4-
Классы: 10,11

Шарообразная планета окружена 37-ю точечными астероидами. Доказать, что в любой момент на поверхности планеты найдётся точка, из которой астроном не сможет наблюдать более 17 астероидов.

Примечание. Астероид, расположенный на линии горизонта, не виден.

Решение

Проведём через центр планеты и произвольную пару астероидов плоскость П (будем считать её экваториальной). Проведём ось планеты, перпендикулярную плоскости П. Она пересекает поверхность планеты в "полюсах" A и B. Тогда легко видеть, что наблюдатели в точках A и B видят вместе лишь 37 − 2 = 35 астероидов, а потому один из них видит менее 18 астероидов.
Прислать комментарий


Задача 98267

Темы:   [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 8,9

На координатной плоскости отмечены некоторые точки с целыми координатами. Известно, что никакие четыре из них не лежат на одной окружности. Докажите, что найдётся круг радиуса 1995, в котором не отмечено ни одной точки.

 

Решение

  Допустим, что такого круга нет, то есть внутри каждого круга радиуса 1995 найдётся отмеченная точка. Рассмотрим бесконечную горизонтальную полосу ширины 4000. Разобьём её на квадраты 4000×4000. Рассмотрим 4001 такой квадрат подряд, образуемый ими прямоугольник обозначим через П. В каждом квадрате найдётся отмеченная точка (так как в такой квадрат можно поместить круг радиуса 1995). Расстояния до этих точек от нижнего края полосы не могут быть все различны, так как расстояний – 4000, а точек – 4001. Итак, найдутся две отмеченные точки на одинаковой высоте. Абсциссы этих двух точек – какие-то два целых числа из некоторого отрезка, поэтому существует ограниченное число возможностей для их значений.
  Рассмотрим теперь достаточно много таких горизонтальных полос, не пересекающих друг друга. В каждой из них в прямоугольнике, находящимся над П, существует пара отмеченных точек на одной высоте. Найдутся две пары, у точек которых абсциссы одной пары совпадают с соответствующими абсциссами другой пары. Четыре построенные точки суть вершины прямоугольника, то есть лежат на одной окружности. Противоречие.

Прислать комментарий

Задача 109937

Темы:   [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Процессы и операции ]
[ Перебор случаев ]
[ Инварианты ]
Сложность: 4-
Классы: 9,10,11

Имеется таблица n×n, в  n – 1  клетках которой записаны единицы, а в остальных клетках – нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?

Решение

  Докажем, что в исходной таблице найдется подтаблица 2×2, в которой стоит одна единица и три нуля.
  Найдется строка, в которой стоят одни нули (так как строк n, а единиц  n – 1).  Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. В этой ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой – ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.   Выберем в нашей таблице произвольную подтаблицу 2×2: пусть в ее левом верхнем углу стоит число a, в правом верхнем – b, в левом нижнем – c и в правом нижнем – d, а после проведения операции – a1, b1, c1, d1 соответственно. Рассмотрим выражения
D = (a + d) – (b + c)  и  D1 = (a1 + d1) – (b1 + c1).   Возможны три случая.
  1) Выбранная клетка находится вне нашей подтаблицы, но лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке c a и b, тогда  a1 = a + 1,  b1 = b + 1,  c1 = cd1 = d  и  D1 = (a + 1 + d) – (b + 1 + c) = D.
  2) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда, очевидно, D1 = D.
  3) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она – верхняя левая клетка подтаблицы, тогда  a1 = a – 1,  b1 = b + 1,  c1 = c + 1,  d1 = d  и  D1 = D – 3.  (Если правая нижняя, то опять  D1 = D – 3,  в противном случае  D1 = D + 3.)
  Таким образом, мы показали, что остаток от деления D на 3 – инвариант. Однако в исходной таблице мы нашли подтаблицу 2×2, в которой  D = ±1,  а мы должны получить таблицу, в которой все числа равны, то есть с  D = 0,  что невозможно.

Ответ

Нельзя.

Прислать комментарий

Задача 110072

Темы:   [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Разрезания на части, обладающие специальными свойствами ]
[ Геометрия на клетчатой бумаге ]
Сложность: 4-
Классы: 7,8,9

Автор: Лифшиц Ю.

Мишень представляет собой треугольник, разбитый тремя семействами параллельных прямых на 100 равных правильных треугольничков с единичными сторонами. Снайпер стреляет по мишени. Он целится в треугольничек и попадает либо в него, либо в один из соседних с ним по стороне. Он видит результаты своей стрельбы и может выбирать, когда стрельбу заканчивать. Какое наибольшее число треугольничков он может с гарантией поразить ровно пять раз?

Решение



Покажем, что стреляющий может добиться 25 призовых мишеней. Рассмотрим разбиение мишени на 25 треугольных кусков 2×2 , т.е. состоящие из четырех треугольников (см. рис.) . Тогда, стреляя в центр каждого из них до тех пор, пока в одном из четырех треугольников куска не накопится пять попаданий, он получит ровно 25 призовых мишеней.
Покажем, что стрелок не может гарантировать себе большего количества. Действительно, при стрельбе в произвольный треугольничек какого-то куска стрелок может всегда попадать в центральный треугольничек этого куска. Тогда призовых мишеней будет не больше 25, так как в остальные он не попадет ни разу.

Ответ

25.00
Прислать комментарий


Задача 115467

Темы:   [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Теория графов (прочее) ]
Сложность: 4-
Классы: 7,8,9,10

На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.
Докажите, что у семи из них есть общий дедушка.

Решение

  Рассмотрим граф, где вершины соответствуют дедам, а рёбра – общим внукам. Если вершин не более двух, то у каждого деда десять внуков.
  Предположим, что вершин ровно три. Они соединены 10 рёбрами. По принципу Дирихле какие-то две вершины соединены не более чем тремя рёбрами. Тогда из третьей вершины выходит не менее семи рёбер. Следовательно, у деда, соответствующего этой вершине, семь внуков.
  Предположим, что на вершин более трёх. По условию из каждой вершины выходит хотя бы одно ребро и каждые два ребра имеют общую вершину. Рассмотрим вершину A, из которой выходит хотя бы два ребра AB и AC, и произвольную из оставшихся вершин D. Тогда каждое рёбро из D должно вести в A (иначе найдутся два ребра без общей вершины). Значит, ребер, соединяющих B с C, нет, и все рёбра выходят из A.
  Дед, соответствующий вершине A, будет общим для всех 10 ребят.

Прислать комментарий

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 124]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .