Нестандартные задачи

[maxal]

Профессор Снэйп писал(а):

TOTAL писал(а):

student писал(а):

Найдите всех натуральных решений уравнение
$13^{n+1}-14^n=2001$

$13^3(13^{n-2}-1)=14^2(14^{n-2}-1)$, откуда $n=2+338k$ и ничего не подходит кроме $n=2$

А откуда, кстати, берётся число $338 = 2 \cdot 13^2$?

На самом деле там даже больший множитель вылазит:

? znorder(Mod(14,13^3))
%1 = 169
? znorder(Mod(13,14^2))
%2 = 14
? lcm(%1,%2)
%3 = 2366

Добавлено спустя 8 минут 2 секунды:

Trius писал(а):

Можно ли из степеней двойки выбрать геометрическую прогресию так, чтоб ее сума была равна $ 10^8$?

Очевидно, нельзя. Достаточно записать $10^8$ в двоичной системе счисления и убедиться, что расстояние между соседними единицами не является константой.

[TOTAL]

Профессор Снэйп писал(а):

А откуда, кстати, берётся число $338 = 2 \cdot 13^2$?

По модулю $13^3$ и биному Ньютона

$$ 14^{n-2} - 1 = (1+13)^{n-2} - 1=13(n-2)\left(1+13\frac{n-3}{2}\right)=0 $$

[Trius]

maxal писал(а):

Профессор Снэйп писал(а):

TOTAL писал(а):

student писал(а):

Добавлено спустя 8 минут 2 секунды:

Trius писал(а):

Можно ли из степеней двойки выбрать геометрическую прогресию так, чтоб ее сума была равна $ 10^8$?

Очевидно, нельзя. Достаточно записать $10^8$ в двоичной системе счисления и убедиться, что расстояние между соседними единицами не является константой.

Для школьника за час и без калькулятора это не самая простая задача

[maxal]

Trius писал(а):

maxal писал(а):

Trius писал(а):

Можно ли из степеней двойки выбрать геометрическую прогресию так, чтоб ее сума была равна $ 10^8$?

Очевидно, нельзя. Достаточно записать $10^8$ в двоичной системе счисления и убедиться, что расстояние между соседними единицами не является константой.

Для школьника за час и без калькулятора это не самая простая задача

В данном случае достаточно найти три последних единицы числа $5^8$. Дел на пару минут с ручкой и бумажкой

[arqady]

Sonic86 писал(а):

5. Набор чисел $a,b,c$ совпадает с набором $a^4-2b^2,b^4-2c^2,c^4-2a^2$, причем $a+b+c=-3$. Найти $a,b,c$.

$$a^4+b^4+c^4-2(a^2+b^2+c^2)=a+b+c.$$

Поэтому

$$27(a^4+b^4+c^4)-6(a^2+b^2+c^2)(a+b+c)^2=-(a+b+c)^4,$$

что эквивалентно

$$\sum_{cyc}(a-b)^2(11a^2+14ab+11b^2)=0,$$

а это даёт

$$a=b=c.$$

[Sonic86]

arqady, спасибо, блин, большое!!! А я парился и парился...

[arqady]

Sonic86, вот так проще:
http://www.artofproblemsolving.com/Foru ... p?t=206083
В то же время, мой способ более сильный, имхо. С помощью него можно решить задачу, которую я предложил в указанной ссылке.

[Sonic86]

Придумал задачу.
последовательность $x_{n+1} = \frac{1}{2} (x_n + \frac {a}{x_n })$ при начальном значении $x_0$, близком к $\sqrt{a}$, сходится к $\sqrt{a}$.
Докажите или опровергните, что если $x_0$ - наилучшее приближение к $\sqrt{a}$, то все $x_n$ являются наилучшими приближениями к $\sqrt{a}$.
Наилучшее приближение - в обычном смысле: $\frac{p}{q}$ - наилучшее приближение к $\alpha$, $\leftrightarrow$ $|\frac{p}{q}-\alpha |=\min \limits_{\frac{x}{y}, y<q+1} |\frac{x}{y}-\alpha |$

[TOTAL]

Sonic86 писал(а):

Придумал задачу.
последовательность $x_{n+1} = \frac{1}{2} (x_n + \frac {a}{x_n })$ при начальном значении $x_0$, близком к $\sqrt{a}$, сходится к $\sqrt{a}$.

При любом положительном $x_0$ квадратично сходится к $\sqrt{a}$
Уже $x_1$ не является наилучшим приближением. Например, $a=\sqrt{2}$

[Sonic86]

Ага, понял.
Тогда вопрос в том, чтобы найти множество всех таких чисел.
Другая задача: доказать (или опровергнуть?) исходное утверждение для $a=2$.
Если обозначить $y_n$, где $n$ - неотрицательное, - последовательность наилучших приближений к $\sqrt{2}$,
то для $x_0 =1$ и $x_{n+1} = \frac{1}{2} (x_n + \frac{2}{x_n })$ имеем:
$x_0 =1=y_0$,
$x_1 =\frac{3}{2}=1+\frac{1}{2}=y_1$,
$x_2 = \frac{17}{12}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}=y_3$,
$x_3 = \frac{577}{408}=y_7$
В общем, $x_n = y_{2^n-1}$

Мне интересно просто - насколько это закономерный факт. Может, будут какие-то соображения.
Вот в случае с $a=3$ различие имеется только в последнем знаке цепной дроби, но получающееся приближение даже лучше, так как $[\sqrt{3}]>1/2$.
Вот еще: в случае кубического корня (отображение $x_n$ вообще говоря строится из численного метода Ньютона касательных для поиска корней) (кстати, для кубического корня из 2 эта последовательность сходится к нему с ужасающей скоростью) такого не получается - около половины знаков цепной дроби не являются знаками лучших приближений. Это, видимо, связано с естественной формой представления числа ветвящейся цепной дробью. Для квадратичных иррациональностей это представление совпадает с представлением в виде простой цепной дроби, поэтому приближения получаются лучше.
Насчет $a=\sqrt{2}$ не знаю, что сказать..., но предел - иррациональность степени 4.
Точно! Для $a \in \mathbb{N}$, такого, что $[\sqrt{a}]<1/2$ ,будет $x_n = y_{2^n-1}$, а для $a: [\sqrt{a}]>1/2$ будет то же самое, исключая последний знак цепной дроби.

[Руст]

Ecли обозначить $\sqrt a <x_1=\sqrt a \cth z_1$ то получается $x_{n+1}=\sqrt a \cth (2^nz_1)$.
Отсюда получается неулучшаемая оценка приближения $0<x_{n+1}-\sqrt a <\frac{(x_n-\sqrt a )^2}{2\sqrt a }$, неулучшаемо в том смысле, что
$x_{n+1}-\sqrt a >(1-\delta )\frac{(x_n-\sqrt a)^2}{2\sqrt a}$ начиная с некоторого номера $n$ при любом положительном $\delta >0$.
Если $x_n=\frac{p_n}{q_n}$, то $x_{n+1}=\frac{p_n^2+q_n^2}{2p_nq_n},p_{n+1}=p_n^2+q_n^2,q_{n+1}=2p_nq_n.$
Поэтому, если $x_n-\sqrt a =\frac{\delta_n}{q_n^2}$, то $x_{n+1}-\sqrt a=b_n\frac{\delta_n^2}{2q_n^4\sqrt a}=c_n2\sqrt a \frac{\delta_n^2}{q_{n+1}^2}.$ Здесь $b_n,c_n$ последовательности быстро стремящиеся к 1.
Поэтому $x_{n+1}$ остается таким же хорошим приближением, что и $x_n$ только если последнее удовлетворяло уравнению Пелля $p_n^2-aq_n^2=1$, т.е $p_n+\sqrt a q_n=(b+c\sqrt a )^k$, где $b+c\sqrt a$ - фундаментальное решение уравнения Пелля. В этом случае $x_{n+1}=\frac{p_{n+1}}{q_{n+1}}$ есть следующее решение $p_{n+1}+q_{n+1}=(b+c\sqrt a)^{2k}$.
Таким образом, мы всегда получаем наилучшее приближение в том и только в том случае, когда $x_1=\frac{x_0^2+a}{2x_0}=\frac{p_1}{q_1}$ является решением $p_1^2-aq_1^2=1$, т.е. $x_0^2=a\pm 1$. В этом случае все дроби являются решением уравнения Пелля.
Если $x_0$ целое то это возможно только, если $a=k^2\pm 1, x_0=k$. Но для любого натурального $a$, не являющегося квадратом целого числа, существует начальное (дробь с минимальным знаменателем) приближение $x_0$, что все $x_i$ будут наилучшими приближениями.

[Sonic86]

1. Придумал довольно интересную задачу.
р - простое число
Для любых а и k найти число решений сравнения $x_1 + ... + x_k \equiv a (mod p)$

2. Еще одна, может кого заинтересует:
Найти множество всех простых р, представимых в виде $p=(A-B)(A-C)-(B+C)^2$, где
$A=a^2+b^2+c^2+d^2$, $B=ab+bc+cd$, $C=ca+ad+db$.
Можно ли вообще это множество как-то проще определить?
Можно на разминку доказать, что 2 не представимо в указанном виде.

3. Еще несколько:
Доказать, что все числа вида $(8n-1)*4^k$ есть в точности все числа, не представимых в виде суммы трех квадратов.
Найти во множестве чисел, представимых в виде суммы трех квадратов максимальный по включению моноид по умножению.
Доказать, что главный асимптотический член для такого n-ого числа равен 6n.
Даны числа вида $(kn+b)*a^m$ для всех m,n, расположенные по возрастанию, $k,b=const$.
Найти n-й член в отсортированной последовательности.

4. Доказать или опровергнуть, что для любого простого p, большего 7, и для любого а
всегда есть решение сравнения:
$x^3+y^3 \equiv a (mod p)$.

[Sonic86]

Еще задачки про суммы трех квадратов.
1. Описать все числа, единственным образом представимые в виде суммы трех квадратов.
2. Конечно ли множество чисел, не делящихся на 4,
представимых единственным образом в виде суммы трех квадратов.
Если да, то опишите его (перечислите) (у меня получилось 33 числа в пределах 500).

[pakandrew]

Извините за off-top но,
как доказать следующий факт :
Если сумма всех делителей числа $N$ равна $2N-1$ ,то $N=k^2$,где $k$-нечетно или $N=2^s$

[Руст]

Это не верно. возьмите $N=2$, сумма делителей $3=2\cdot 2-1$.