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

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

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



Задача 58214

Тема:   [ Целочисленные решетки (прочее) ]
Сложность: 7
Классы: 9,10

Докажите, что для любого n существует окружность, на которой лежит ровно n целочисленных точек.

Решение

Докажем сначала, что уравнение x2 + y2 = 5k имеет ровно 4(k + 1) целочисленных решений. При k = 0 и k = 1 это утверждение очевидно. Докажем, что уравнение x2 + y2 = 5k имеет ровно восемь таких решений (x, y), что x и y не делятся на 5; вместе с 4(k - 1) решениями вида (5a, 5b), где a и b — решение уравнения a2 + b2 = 5k - 2, они дают нужное количество решений. Эти решения получаются друг из друга перестановками x и y и изменениями знаков; мы будем называть их нетривиальными решениями.
Пусть x2 + y2 делится на 5. Тогда (x + 2y)(x - 2y) = x2 + y2 - 5y2 тоже делится на 5. Поэтому одно из чисел x + 2y и x - 2y делится на 5. Легко проверить также, что если x + 2y и x - 2y делятся на 5, то x и y делятся на 5.
Если (x, y) — нетривиальное решение уравнения x2 + y2 = 5k, то (x + 2y, 2x - y) и  (x - 2y, 2x + y) — решения уравнения $ \xi^{2}_{}$ + $ \eta^{2}_{}$ = 5k + 1, причем ровно одно из них нетривиально. Остается доказать, что нетривиальное решение единственно с точностью до перестановки x и y и изменения знаков. Пусть (x, y) — нетривиальное решение уравнения x2 + y2 = 5k. Тогда как пары $ \Bigl($±$ {\frac{2x-y}{5}}$$ {\frac{x+2y}{5}}$$ \Bigr)$ и  $ \Bigl($±$ {\frac{x+2y}{5}}$, ±$ {\frac{2x-y}{5}}$$ \Bigr)$, так и пары $ \Bigl($±$ {\frac{2x+y}{5}}$$ {\frac{x-2y}{5}}$$ \Bigr)$ и  $ \Bigl($±$ {\frac{x-2y}{5}}$$ {\frac{2x+y}{5}}$$ \Bigr)$ являются решениями уравнения $ \xi^{2}_{}$ + $ \eta^{2}_{}$ = 5k - 1, но целочисленными будут пары ровно одного из этих видов, так как ровно одно из чисел x + 2y и x - 2y делится на 5. При этом мы получим нетривиальное решение, потому что (x + 2y)(x - 2y) = (x2 + y2) - 5y2 при k$ \ge$2 делится на 5, но не делится на 25. Таким образом, каждое из восьми нетривиальных решений уравнения x2 + y2 = 5k дает восемь нетривиальных решений уравнения $ \xi^{2}_{}$ + $ \eta^{2}_{}$ = 5k - 1, причем для одной половины решений нужно воспользоваться формулами первого вида, а для другой половины решений — формулами второго вида.
Перейдем теперь непосредственно к решению задачи. Пусть n = 2k + 1. Докажем, что на окружности радиуса 5k/3 с центром (1/3, 0) лежит ровно n целочисленных точек. Уравнение x2 + y2 = 52k имеет 4(2k + 1) целочисленных решений. Кроме того, 52k при делении на 3 дает остаток 1, поэтому одно из чисел x и y делится на 3, а другое при делении на 3 дает остаток ±1. Следовательно, ровно в одной из пар (x, y), (x, - y), (y, x) и (- y, x) первое и второе числа дают при делении на 3 остатки -1 и 0 соответственно. Поэтому уравнение (3z - 1)2 + (3t)2 = 52k имеет ровно 2k + 1 целочисленных решений.
Пусть n = 2k. Докажем, что на окружности радиуса 5(k - 1)/2/2 с центром (1/2, 0) лежит ровно n целочисленных точек. Уравнение x2 + y2 = 5k - 1 имеет ровно 4k целочисленных решений, причем одно из чисел x и y четно, а другое нечетно. Поэтому уравнение (2z - 1)2 + (2t)2 = 5k - 1 имеет ровно 2k целочисленных решений.


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


Задача 30932

Темы:   [ Четность и нечетность ]
[ Целочисленные решетки (прочее) ]
Сложность: 3-
Классы: 6,7,8

На клетчатой бумаге нарисован замкнутый путь (по линиям сетки). Доказать, что он имеет чётную длину (сторона клетки имеет длину 1).

Подсказка

При прохождении пути шагов вверх должно быть столько же, сколько шагов вниз, а шагов вправо – столько же, сколько шагов влево (см. решение задачи 30310).

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

Задача 65345

Темы:   [ Теория вероятностей (прочее) ]
[ Целочисленные решетки (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
[ Классическая комбинаторика (прочее) ]
Сложность: 3
Классы: 8,9,10,11

Точка выходит из начала координат на прямой и делает a шагов на единицу вправо, b шагов на единицу влево в каком-то порядке, причём  a > b.  Размахом блуждания точки назовём разность между наибольшей и наименьшей координатами точки за всё время блуждания.
  а) Найдите наибольший возможный размах блуждания.
  б) Найдите наименьший возможный размах.
  в) Сколько существует различных последовательностей движения точки, при которых размах блуждания будет наибольшим возможным?

Решение

  б) В конце своего пути точка неизбежно (каков бы ни был порядок шагов вправо и влево) имеет координату  a – b.  Значит, размах не может быть меньше
a – b.
  Такой размах получается, например, так: точка движется вправо-влево ровно b раз, а затем  a – b  раз вправо.

  а) Пусть наименьшая координата точки за все время блуждания равна  x ≤ 0.  До момента t, когда точка впервые достигла этого положения, она не могла быть в точках с координатами, большими  x + b.  После момента t она не могла быть в точках с координатами, большими  x + a.  Значит, наибольший размах не превышает a.
  Такой размах получается, например, если точка сначала делает a шагов вправо.

  в) Как видно из а), наибольший размах получается, если все шаги вправо точка делает подряд. Первый шаг вправо может быть по счету первым, вторым и так далее до номера  b + 1  (сначала b шагов влево, а затем все шаги вправо). Таким образом, всего  b + 1  способ.

Ответ

а) a;  б)  a – b;  в)  b + 1.

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

Задача 78577

Темы:   [ НОД и НОК. Взаимная простота ]
[ Целочисленные решетки (прочее) ]
[ Симметрия помогает решить задачу ]
Сложность: 3
Классы: 10,11

В прямоугольном бильярде размером p×2q, где p и q – нечётные числа, сделаны лузы в каждом углу и в середине каждой стороны длины 2q. Из угла выпущен шарик под углом 45° к стороне. Доказать, что шарик обязательно попадет в одну из средних луз.

Решение

Разобьём плоскость на прямоугольники p×q, то есть рассмотрим сетку с шагом q по горизонтали и p – по вертикали. Бильярд занимает два соседних прямоугольника этой сетки. Распрямим путь шара, симметрично отражая его относительно стенок. Тогда шар будет двигаться по прямой  y = x  (точнее, по лучу этой прямой, выходящему из начала координат), а лузы будут расположены в узлах сетки. Этот луч впервые пройдёт через узел сетки в точке с координатами  (m, m),  где
m = НОК(p, q).  Поскольку m нечётно, эта точка соотвествует средней лузе.

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

Задача 35753

Темы:   [ Принцип Дирихле (прочее) ]
[ Целочисленные решетки (прочее) ]
Сложность: 3
Классы: 8,9,10

В выпуклом многоугольнике на плоскости содержится не меньше m2+1 точек с целыми координатами. Докажите, что в нем найдется m+1 точек с целыми координатами, которые лежат на одной прямой.

Подсказка

Раскрасьте целые точки плоскости в m2 цветов. Найдутся две точки одного цвета.

Решение

По принципу Дирихле среди m2+1 точек с целыми координатами найдутся такие две точки (k, l) и (k1, l1), что k=k1 (mod m) и l=l1 (mod m). Тогда m+1 точек $(k+\frac{k_1-k}mi,l+\frac{l_1-l}mi)$, $0\le i\le m$, имеют целые координаты и лежат на отрезке, соединяющем точки (k, l) и (k1, l1).
Прислать комментарий


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



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

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