три задачки
Oct. 15th, 2002 05:48 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaТри математических задачки олимпиадного типа. Первая лёгкая, вторая и третья чуть сложней, возможно. Решения напишу через день-два, если какие-то не решат в комментах.
1. Прямая линия, пересекающая шахматную доску размером 8x8, пересекает в ней какое-то количество шахматных полей-квадратов. Условимся, что прямая пересекает квадрат, если она проходит сквозь хотя бы одну точку внутри его (точки на границе "не считаются"). Найти максимальное число квадратов, которое может пересечь прямая.
2. На плоскости с координатной сеткой рисуем круг с радиусом 2 (радиус, не диаметр!). Какое-то количество вершин координатной сетки (точек-перекрестий) окажутся внутри круга; здесь, опять-таки, точки, оказавшиеся на границы круга, "не считаются". Найти минимальное и максимальное возможное число вершин сетки, могущих попасть внутрь круга.
3. Для каждого натурального числа n определим f(n) = количество положительных делителей числа n, т.е. чисел, на которые n делится без остатка -- включая 1 и само число n. Например, f(1)=1, а f(4)=3, потому что у четвёрки есть три делителя: 1, 2 и 4.
Каждое натуральное число n порождает бесконечную последовательность такого вида: n, f(n), f(f(n)), f(f(f(n))), ... То есть мы берём количество делителей последнего числа в списке и добавляем его в конец списка, потом опять берём уже его количество делителей и добавляем, и так до бесконечности.
Задание: найти (и доказать, естественно), для каких n порождаемая ими последовательность не содержит ни одного точного квадрата (т.е. числа вида k2, являющегося квадратом другого натурального числа).
1. Прямая линия, пересекающая шахматную доску размером 8x8, пересекает в ней какое-то количество шахматных полей-квадратов. Условимся, что прямая пересекает квадрат, если она проходит сквозь хотя бы одну точку внутри его (точки на границе "не считаются"). Найти максимальное число квадратов, которое может пересечь прямая.
2. На плоскости с координатной сеткой рисуем круг с радиусом 2 (радиус, не диаметр!). Какое-то количество вершин координатной сетки (точек-перекрестий) окажутся внутри круга; здесь, опять-таки, точки, оказавшиеся на границы круга, "не считаются". Найти минимальное и максимальное возможное число вершин сетки, могущих попасть внутрь круга.
3. Для каждого натурального числа n определим f(n) = количество положительных делителей числа n, т.е. чисел, на которые n делится без остатка -- включая 1 и само число n. Например, f(1)=1, а f(4)=3, потому что у четвёрки есть три делителя: 1, 2 и 4.
Каждое натуральное число n порождает бесконечную последовательность такого вида: n, f(n), f(f(n)), f(f(f(n))), ... То есть мы берём количество делителей последнего числа в списке и добавляем его в конец списка, потом опять берём уже его количество делителей и добавляем, и так до бесконечности.
Задание: найти (и доказать, естественно), для каких n порождаемая ими последовательность не содержит ни одного точного квадрата (т.е. числа вида k2, являющегося квадратом другого натурального числа).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2002-10-15 08:54 am (UTC)Re:
Date: 2002-10-15 08:55 am (UTC)Re:
Date: 2002-10-15 09:13 am (UTC)Re:
Date: 2002-10-15 09:17 am (UTC)no subject
Date: 2002-10-15 09:12 am (UTC)диагональ шахматной доски(сост.часть прямой)пересекает восемь квадратиков
2.max - 4, min - 1(а то и все - ноль)
Re:
Date: 2002-10-15 09:13 am (UTC)2. Ноль и один невозможны в принципе.
no subject
Date: 2002-10-15 09:23 am (UTC)Re:
Date: 2002-10-15 09:24 am (UTC)Re:
Date: 2002-10-15 09:25 am (UTC)no subject
Date: 2002-10-15 09:32 am (UTC)не совсем внимательно прочла условие задачки
no subject
Date: 2002-10-15 09:59 am (UTC)Типа, для доски MxN должно получиться M+N-1.
2. Если 2 - радиус, а не диаметр, то минимум - 9 (единственное положение: небольшой сдвиг в любом направлении увеличивает число захваченных вершин как минимум на одну), максимум - 14. Потребовалось показать, что
(2 - sqrt(7)/2)^2 + (3/2)^2 < 2^2, а также
(3 - sqrt(7)/2)^2 + (1/2)^2 < 2^2.
Re:
Date: 2002-10-15 12:27 pm (UTC)2. Да, верно! Но Вы забыли привести сами положения?
Re:
Date: 2002-10-15 12:51 pm (UTC)2. 9 - центр круга в узле сетки.
14 - поместим центр круга в середину клетки координатной сетки, тогда внутрь круга попадает 12 точек; смещаем круг параллельно линиям сетки так, чтобы попали еще две точки. Два неравенства доказывают, что другие точки из круга не "потерялись".
no subject
Date: 2002-10-15 10:50 am (UTC)(рассмотрим линию под углом меньшим 90, остальные идут симметрично)
В этом случае при переходе из квадрата в квадрат линия попадает или в квдрат выше или
в квадрат правее (или одновременно). В случае движение вверх + вправо (вправо + вверх -
аналогично), каждый переход от исходного квадрата добавляет 2 новых (например: из А1
переходим в А2, потом В2). Переход из А1 сразу в В2 не выгоден (теряется квадрат).
Рассуждая таким образом приходим к максимальному пути, условие окончания которого: манёвр
"вверх + вправо" невозможен. Получаем 1 + 2 * 7 = 15 (семь раз можно подняться вверх).
no subject
Date: 2002-10-15 10:55 am (UTC)на пол-клетки вверх (чтобы работало "вверх-вправо").
Re:
Date: 2002-10-15 12:28 pm (UTC)no subject
Date: 2002-10-15 02:36 pm (UTC)Re:
Date: 2002-10-15 02:55 pm (UTC)Никто не трогал третью задачу.
Date: 2002-10-15 01:45 pm (UTC)Краткое содержание решения.
1) Лемма: если n = (p1)^(a1) * (p2)^(a2) * ... * (pm)^(am), то
f(n) = (a1+1)(a2+1)...(am+1).
Доказательство опущено.
2) Лемма: для всякого n > 2, f(n) > n.
Доказательство опущено.
3) Тривиальное наблюдение: f(2) = 2, a f(n) < 2 тогда и только тогда, когда n = 1. (Тогда f(1)=1; но 1 - полный квадрат :)) ).
4) Последовательность b0 = n, b1 = f(n), b2 = f(f(n)), ... не больше чем за n шагов дойдёт до значения 2, и далее будет bm = 2 для всех m, больших или равных некоему k (ясно). Итак, пусть k - первое такое число, что bk = 2.
[Использую bk вместо bk из-за лени.]
Если k = 0, то n=2. Такая последовательность не содержит полных квадратов.
5) Пусть k>0. Тогда bk-1 - число с двумя делителями, но не 2: иными словами, bk-1 - нечетное простое число.
Если k-1 = 0, то мы вновь получаем последовательность без квадратов, для n - нечетных простых чисел.
6) Пусть k-1>0. Тогда у bk-2 ровно bk-1 делителей. Если число делителей - простое, то, согласно лемме (1), bk-2 - степень ОДНОГО простого числа p. bk-2 = p^(bk-1-1) = четная степень числа p, то-есть ПОЛНЫЙ КВАДРАТ.
Таким образом, единственные числа n, для которых НЕТ полных квадратов в последовательности - ПРОСТЫЕ. QED.
Re: Никто не трогал третью задачу.
f(n) = (a1+1)(a2+1)...(am+1).
Доказательство опущено.
Здесь p1, p2 итп. - простые множители n, а a1, a2 итп. - их степени в разложении n на простые множители. (это я не для тебя естественно, а для тех, кто, возможно, не понимает).
2) Лемма: для всякого n > 2, f(n) > n.
Наоборот, f(n)
f(n) = (a1+1)(a2+1)...(am+1).
Доказательство опущено.</i>
Здесь p1, p2 итп. - простые множители n, а a1, a2 итп. - их степени в разложении n на простые множители. (это я не для тебя естественно, а для тех, кто, возможно, не понимает).
<i>2) Лемма: для всякого n > 2, f(n) > n.</i>
Наоборот, f(n)<n. Впрочем, это у тебя описка ;)
Всё остальное верно; кстати, в пункте 6) необязательно было пользоваться простотой b<sub>k-1</sub> -- достаточно нечётности этого числа, из которой сразу следует, что b<sub>k-2</sub> - полный квадрат (т.к. все простые множители встречаются в его разложении с чётными степенями).
Re: Никто не трогал третью задачу.
Date: 2002-10-17 11:29 am (UTC)Re: Никто не трогал третью задачу.
Date: 2002-10-17 11:32 am (UTC)> Наоборот, f(n)<n. Впрочем, это у тебя
> описка ;)
> Всё остальное верно; кстати, в пункте 6)
> необязательно было пользоваться
> простотой bk-1
no subject
Date: 2002-10-15 01:58 pm (UTC)Лемма 2. Число делителей числа меньше числа, если число > 2. Тоже могу доказать.
Каждый ряд так уменьшаясь ударит по 1, 2 или по нечетному. В рядах с нечетным был квадрат. Только ряд 1,1,1,1... кончается на 1. Значит хороший ряд кончается на 2. Но перед 2 стоит либо 2, либо простое нечетное, а перед нечетным -- квадрат. Значит хорошие ряды порождаются простыми числами и 1.
Re:
Date: 2002-10-15 02:01 pm (UTC)хорошие ряды порождаются простыми числами и 1.
Только 1 не считается, он квадрат ;)