Решения заданий С6 от Ленина В.И.

Некоторое время назад был план сделать подробные решения 50 задач С6 вместе с разбором используемых теорем и лемм. Начиная с сегодня буду выкладывать по 1-2 задаче. Задачи подберу наиболее оптимальные. Тема будет полезна и олимпиадникам.
Можете выкладывать свои задачи, если они окажутся образцово-показательными, пойдут в коллекцию.

Эта тема отлична от другой темы - решения задач по теории чисел, и заточена именно под С6.


23 дек 2009, 11:38
#1
Задача 1.
Решить уравнение в целых числах
`x^2+y^2=z^2`.

Решение:
| +
Это классическое уравнение, его решения называются "пифагоровыми" тройками.
Для начала упростим его, очень интересным (и используемым) образом!
Упрощение
Определение `НОД`. Если `НОД(a,b)=d`, где `a, b in ZZ, d in NN => EE a_1, b_1 in ZZ`, при этом `НОД(a_1,b_1)=1`, такие что
`a=a_1d, b=b_1d`.
В дальнейшем `НОД(a,b)` я буду сокращенно обозначать как `(a,b)`.

Пусть `(x,y)=d => x=x_1d, y=y_1d`, где `x_1,y_1 in ZZ, (x_1,y_1)=1`.
Тогда наше уравнение перепишется, как
`x_1^2d^2+y_1^2d^2=z^2`,
`d^2(x_1^2+y_1^2)=z^2 =>` как мы видим, `z^2` делится на `d^2` (записывается, как `z^2 vdots d^2`)
Если `z^2 vdots d^2 => z vdots d`. Утверждение вроде простое и интуитивное понятное, но надо уметь доказывать даже такие, казалось бы "простые" вещи.
Лемма. Пусть `a^2 vdots b^2, a, b in ZZ`. Доказать, что `a vdots b`. Попробуйте доказать сами.

Раз `z vdots d => EE z_1 in ZZ: z=z_1d`,
`d^2(x_1^2+y_1^2)=z_1^2d^2`,
`x_1^2+y_1^2=z_1^2`.
Получили такое же уравнение! Но у нас есть новое условие, а именно `(x_1,y_1)=1`. Т.е. мы упростили задачу. В этом и заключается метод упрощения, когда простыми действиями добавляются ограничивающие условия, вроде взаимной простоты неизвестных.
Заметим, что если `(x_1,y_1)=1 => (x_1,z_1)=(y_1,z_1)=1`. Легко доказывается от противного. Если `(x_1, z_1)=k>1 => y_1^2=z^2-x^2 vdots k^2 => y_1 vdots k => (x_1, y_1)>=k>1 O/`

Резюмируя вышесделанные манипуляции, нам надо решить уравнение в целых числах
`x_1^2+y_1^2=z_1^2`,
где `x_1, y_1, z_1` - взаимно простые.

Продолжение следует...

Теперь делаем достаточно простое наблюдение: одна из переменных `x_1, y_1` четная, другая нечетная, а `z_1` - нечетная. Во-первых, `x_1` и `y_1` четными одновременно быть не могут, в силу их взаимной простоты. А если они оба нечетные, возникает другая проблема. Настало время разобрать, какие остатки может давать квадрат выражения при делении на разные числа.
Пусть `a=2b+1 => a^2=(2b+1)^2=4(b^2+b)+1` - дает остаток при делении на `4`.
Пусть `a=2b=> a^2 =(2b)^2=4b^2` - делится нацело на `4`.
Т.е. квадрат нечетного числа всегда дает остаток `1` при делении на `4`, а квадрат четного числа дает остаток `0` при делении на `4`.
Вообще, это лучше показывать по другому, через сравнения по модулю, но об этом позже.
Итак, если `x_1, y_1` - нечетны, значит сумма их квадратов `x_1^2+y_1^2` дает остаток `1+1=2` при делении на `4`, НО `z_1^2`, при четном `z_1`, дает остаток `0`. Противоречие.

Пришли к тому, что одна из переменных `x_1, y_1` четная, другая нечетная.
Тут мы можем сказать: пусть, без ограничения общности, `x_1` - нечетно, `y_1` - четно. Перенесем `y_1^2` вправо:
`x_1^2=z_1^2-y_1^2`,
`x_1^2=(z_1-y_1)(z_1+y_1)`.
Заметим, что выражения `z_1-y_1` и `z_1+y_1` взаимно простые. Такая вещь очень часто встречается и надо это уметь доказывать и применять.
Пусть `(z_1-y_1, z_1+y_1)=p => z_1-y_1 vdots p` и `z_1+y_1 vdots p`. Значит, их разность
`z_1+y_1-(z_1-y_1)=2y_1 vdots p` и сумма `2z_1 vdots p`.
Как мы помним, `z_1` - нечетно, `y_1` - четно `=>` оба выражения `(z_1-y_1)` и `(z_1+y_1)` - нечетны, а следовательно `p`, как их делитель - нечетен. Поэтому, из того, что `2y_1 vdots p` следует, что `y_1 vdots p` (двойка роли не играет). Аналогично, `z_1 vdots p`. Но, т.к. `(z_1, y_1)=1 => p=1`, чтд.

А теперь, вступает еще одна отличная лемма.
Лемма древняя. Пусть `ab=x^2`, где `a,b,x in ZZ`, и `(a,b)=1`. Тогда `EE a_1, b_1 in ZZ`, такие, что `a=a_1^2, b=b_1^2` и соотв. `x=a_1b_1`.
Тоже достаточно "простая" вещь. Попробуйте доказать сами.

По этой лемме, из нашего равенства `x_1^2=(z_1-y_1)(z_1+y_1)`, и из доказанной нами взаимной простоты сомножителей в правой части, получаем, что `EE a, b in ZZ`, такие, что
`z_1-y_1=a^2` и `z_1+y_1=b^2`.
Решаем эту систему, получаем `z_1=(a^2+b^2)/2, y_1=(b^2-a^2)/2, x_1=ab`.
Для корректности, укажем на нечетность выражений `a` и `b` (следует из нечетности выражений `z_1-y_1` и `z_1+y_1`).

На самом деле, на этом все, уравнение решение. Если мы подставим найденные `x_1, y_1 и z_1`, получим тождество
`(ab)^2+((b^2-a^2)/2)^2=((a^2+b^2)/2)^2`.

Теперь, умножив все эти переменные на `d`, получим `x, y, z`:
`x=ab*d, y=(b^2-a^2)/2*d, z=(a^2+b^2)/2*d`, где `a,b in ZZ` и нечетны, а `d in ZZ`.

Если децл подумать, условие нечетности `a` и `b` можно выкинуть, а `d` заменить на `2n`, тогда наши решения запишутся так:
`x=2abn, y=(b^2-a^2)n, z=(a^2+b^2)n`, где `a, b, n in ZZ`.


23 дек 2009, 12:22
#2
Дорешал задачу. Это уравнение является базисным в задачах подобного типа. Оно простое, но там используется много специфических, для новичков, штучек.
Необходимо разобрать задачу до точки, тогда хорошо, т.к. там много хороших приемов, которые необходимо в дальнейшем делать на автомате.
Это очень хорошая и полезная задача!

Скоро добавлю решение второй задачи.

Задача 2. Решить уравнение в целых числах `x^2+y^2=3z^2`.


23 дек 2009, 14:08
#3
Задача 3.
Доказать, что `sqrt2` является иррациональным числом.


12 мар 2010, 23:32
#4
Задача 4.
Пусть `x+1/x in ZZ`.
Доказать для любого `n in NN`, что выражение `x^n+1/x^n` - тоже будет целым.


12 мар 2010, 23:34
#5
Срочно надо, решите плиииз!!! Натуральное число N 6 раз больше числа полученного N зачеркиванием первой цифры. Укажите все возможные значения N.

!
albega. Эта задача не относится к моей серии задач этого топика.


14 мар 2010, 16:24
#6
В продолжении к задаче 3...Мое решение задачи 3 в обсуждении поста позволит решить нижеследующую задачу

Задача 5.
Решить уравнение
`sqrt(2sqrt3-3)=sqrt(xsqrt3)-sqrt(ysqrt3)`
в рациональных числах.


15 мар 2010, 17:44
#7
Случайно набрел на задачку
Изображение
пример дебильной задачи, составленной идиотом.

В общем все сводится к решению уравнения
`y(x+1)^2=x^2-x-1`, где `y` - целый, `x` - рациональный.

Самое хреновое, это когда одна посредственность выдумывает такие задачи, а другие посредственности решают.

Что немного улучшить эту хреновость, дополним:
Решить уравнение
`y(x+1)^n=x^n-x-1`, при тех же условиях, `n>=2` - натуральное.


29 мар 2010, 06:21
#8
Задача 7
Расстояние между точкой и прямой определяется, как кратчайшее возможное расстояние между первый точкой и любой другой точкой, лежайщей на прямой.
В треугольнике `ABC` длины сторон равны `AB = 10, BC = 21`, и `CA = 17`. Пусть `P` точка внутри треугольника. Пусть `x` есть расстояние между `P` и `BC`, `y` расстояние
между точкой `P` и `CA`, `z` расстояние между `P` и `AB`. Вычислите максимально возможное значение выражения `xyz`.


20 апр 2010, 14:03
#9

!
Не моя задача. albega.


как решить `(1/k)^n=(1/n)^k`, `k>n` найти `k` и `n`????????????


29 апр 2010, 15:52
#10

!
Не моя задача. albega.
Не выкладывайте здесь задачи, есть другой топик.


Изображение


03 май 2010, 14:34
#11
Задача 8

`a,b,c in NN`,
Решить уравнение `ab=c(c-a-b)`.


08 май 2010, 12:01
1, 2  →