Школьная олимпиадная задача из Австралии

[Klein]

Для школьников 11-12 классов. Эквивалент 10-11 классов в России.

Докажите что для каждого целого числа $k$, удовлетворяющего $2\leq k \leq 100$, существуют положительные целые числа $b_2,b_3,...b_{101}$ удовлетворяющие $b_2^2+b_3^3+\dotsb+b_k^k=b_{k+1}^{k+1}+b_{k+2}^{k+2}+\dotsb+b_{101}^{101}$

[wrest]

Klein
У меня вопрос по нотации. Для $k=100$ равенство записывается как

$$\underbrace{b_2^2+b_3^3+\dotsb+b_{100}^{100}}_{\textit{99 слагаемых}}=b_{101}^{101}$$

а для $k=2$ соответтвенно как

$$b_2^2=\underbrace{b_3^3+b_4^4+\dotsb+b_{101}^{101}}_{\textit{99 слагаемых}}$$

Верно?

[Klein]

wrest в сообщении #1570673 писал(а):

Klein
У меня вопрос по нотации. Для $k=100$ равенство записывается как

$$\underbrace{b_2^2+b_3^3+\dotsb+b_{100}^{100}}_{\textit{99 слагаемых}}=b_{101}^{101}$$

а для $k=2$ соответтвенно как

$$b_2^2=\underbrace{b_3^3+b_4^4+\dotsb+b_{101}^{101}}_{\textit{99 слагаемых}}$$

Верно?

Я тоже так записал равенство.

[mihaild]

Вроде же не требуется, чтобы число слагаемых слева и справа суммарно было каким-то определенным, уравнение $a_1^2 + \ldots + a_n^2 = c_1^2 + \ldots + c_m^2$ имеет решение в натуральных числах при любых $n, m > 0$.

[wrest]

mihaild в сообщении #1570690 писал(а):

Вроде же не требуется, чтобы число слагаемых слева и справа суммарно было каким-то определенным

По-моему, как раз требуется:

Klein в сообщении #1570669 писал(а):

существуют положительные целые числа $b_2,b_3,...b_{101}$

То есть в суммарно слева и справа положительных целых (т.е. нулей быть не может) слагаемых должно быть $100$, слева $k-1$ слагаемых, справа соответственно $101-k$ слагаемых.

$$\underbrace{b_2^2+b_3^3+\dotsb+b_k^k}_{\textit{k-1 слагаемых}}=\underbrace{b_{k+1}^{k+1}+b_{k+2}^{k+2}+\dotsb+b_{101}^{101}}_{\textit{101-k слагаемых}}$$

[mihaild]

Для разрешимости нужно чтобы и слева и справа было хотя бы по одному слагаемому. Чтобы их суммарно было какое-то конкретное количество - не нужно.

[Klein]

Рассмотрим примеры и интервалы.

$k=2$, $b_2=11$, $b_3=b_4=2$, $b_i=1$, $5 \leq i \leq 101$

$11^2=2^3+2^4+1^5+1^6+\dotsb+1^{101}$


$k=51$, $b_i=1$, $2\leq i \leq 101$

$1^2+1^3+\dotsb+1^{51}=1^{52}+1^{53}+\dotsb+1^{101}$


И рассмотрим интервалы $3 \leq k \leq 10$, $11 \leq k \leq 50$, $52 \leq k \leq 101$.

С интервалами сложнее. Наверняка есть более красивое решение.

[mihaild]

[я выше писал бред, неправильно прочитал условие]

[Dendr]

Klein в сообщении #1570711 писал(а):

Наверняка есть более красивое решение.

Можно попытаться... Во-первых, заметить, что подстановкой единиц мы можем всегда избавиться от многих слагаемых.
Во-вторых, если начать с другой крайности, то можно заметить, что

$$2^{101}=2^{100}+2^{99}+...+2^4+2^3+2^2+4$$

Справа - лишняя четверка, и надо перебрать варианты $8=a^2$, или $16=a^2+b^3$, и т.д. Эти ничего не дают, зато следующий: $32=2^2+3^3+1^4$ подойдет. То есть на самом деле

$$2^{101}=2^{100}+...+2^5+1^4+3^3+2^2$$

.

Соответственно, для $k=99$ можно начать с записи тождества

$$1^{101}+2^{100}=2^{99}+...+2^2+5$$

Здесь сразу получаем $b_2=3, 3^2=9$. Ну допустим, для $k>51$ так можно попытаться. Но в общем виде не вижу, как доказать.

[Dendr]

Собственно, в общем виде приходим к тождеству

$$1^{101}+...+1^{k+2}+2^{k+1}=2^k+...+2^2+104-k$$

И далее задаться вопросом, для какого наименьшего $N$ все возможные значения суммы

$$\sum\limits_{n=2}^{N}(b_n^n-2^n)$$

покрывают на числовой оси весь интервал от 4 до $104-N$. Тогда для $k\in[N, 100]$ такая схема даст решение.
Ну а для $k<N$ использовать отдельный подход, их гораздо меньше.

[wrest]

Dendr в сообщении #1570720 писал(а):

Ну допустим, для $k>51$ так можно попытаться.

После 51 особо ничего и не меняется-то как-то.
Вот первая половина для $4<k<100$ (для $k=100$ решение ваше есть выше).

(Осторожно, многа букв)

$ k=99,1+2^{100}=2^{99}+…+2^4+2^3+3^2$
$ k=98,2+2^{99}=2^{98}+…+1^4+2^3+5^2$
$ k=97,3+2^{98}=2^{97}+…+1^5+1^4+4^3+1^2$
$ k=96,4+2^{97}=2^{96}+…+1^6+1^5+1^4+5^3+2^2$
$ k=95,5+2^{96}=2^{95}+…+1^4+3^3+3^2$
$ k=94,6+2^{95}=2^{94}+…+1^4+1^3+6^2$
$ k=93,7+2^{94}=2^{93}+…+1^6+1^5+3^4+3^3+5^2$
$ k=92,8+2^{93}=2^{92}+…+2^4+2^3+4^2$
$ k=91,9+2^{92}=2^{91}+…+1^6+1^5+1^4+5^3+3^2$
$ k=90,10+2^{91}=2^{90}+…+2^4+1^3+5^2$
$ k=89,11+2^{90}=2^{89}+…+1^5+1^4+4^3+3^2$
$ k=88,12+2^{89}=2^{88}+…+2^4+3^3+1^2$
$ k=87,13+2^{88}=2^{87}+…+1^4+2^3+6^2$
$ k=86,14+2^{87}=2^{86}+…+1^5+1^4+3^3+7^2$
$ k=85,15+2^{86}=2^{85}+…+2^4+3^3+2^2$
$ k=84,16+2^{85}=2^{84}+…+1^5+2^4+3^3+6^2$
$ k=83,17+2^{84}=2^{83}+…+2^4+2^3+5^2$
$ k=82,18+2^{83}=2^{82}+…+1^5+2^4+4^3+1^2$
$ k=81,19+2^{82}=2^{81}+…+1^4+1^3+7^2$
$ k=80,20+2^{81}=2^{80}+…+2^4+3^3+3^2$
$ k=79,21+2^{80}=2^{79}+…+1^4+3^3+5^2$
$ k=78,22+2^{79}=2^{78}+…+1^6+2^5+3^4+3^3+3^2$
$ k=77,23+2^{78}=2^{77}+…+1^5+3^4+1^3+2^2$
$ k=76,24+2^{77}=2^{76}+…+1^6+1^5+2^4+5^3+3^2$
$ k=75,25+2^{76}=2^{75}+…+1^5+2^4+2^3+8^2$
$ k=74,26+2^{75}=2^{74}+…+1^4+2^3+7^2$
$ k=73,27+2^{74}=2^{73}+…+2^4+3^3+4^2$
$ k=72,28+2^{73}=2^{72}+…+2^4+2^3+6^2$
$ k=71,29+2^{72}=2^{71}+…+1^5+2^4+3^3+7^2$
$ k=70,30+2^{71}=2^{70}+…+1^5+3^4+2^3+2^2$
$ k=69,31+2^{70}=2^{69}+…+1^6+1^5+2^4+5^3+4^2$
$ k=68,32+2^{69}=2^{68}+…+1^4+3^3+6^2$
$ k=67,33+2^{68}=2^{67}+…+1^5+2^4+4^3+4^2$
$ k=66,34+2^{67}=2^{66}+…+1^4+4^3+1^2$
$ k=65,35+2^{66}=2^{65}+…+1^5+3^4+2^3+3^2$
$ k=64,36+2^{65}=2^{64}+…+2^4+3^3+5^2$
$ k=63,37+2^{64}=2^{63}+…+1^4+4^3+2^2$
$ k=62,38+2^{63}=2^{62}+…+1^5+1^4+4^3+6^2$
$ k=61,39+2^{62}=2^{61}+…+1^5+1^4+1^3+10^2$
$ k=60,40+2^{61}=2^{60}+…+1^6+2^5+1^4+5^3+3^2$
$ k=59,41+2^{60}=2^{59}+…+2^4+2^3+7^2$
$ k=58,42+2^{59}=2^{58}+…+1^4+4^3+3^2$
$ k=57,43+2^{58}=2^{57}+…+1^6+2^5+3^4+2^3+7^2$
$ k=56,44+2^{57}=2^{56}+…+1^5+3^4+1^3+5^2$
$ k=55,45+2^{56}=2^{55}+…+1^4+3^3+7^2$
$ k=54,46+2^{55}=2^{54}+…+1^5+3^4+3^3+1^2$
$ k=53,47+2^{54}=2^{53}+…+2^4+3^3+6^2$
$ k=52,48+2^{53}=2^{52}+…+1^6+2^5+2^4+3^3+10^2$
$ k=51,49+2^{52}=2^{51}+…+2^4+4^3+1^2$
$ k=50,50+2^{51}=2^{50}+…+1^6+2^5+2^4+5^3+2^2$
$ k=49,51+2^{50}=2^{49}+…+3^4+1^3+1^2$
$ k=48,52+2^{49}=2^{48}+…+2^4+4^3+2^2$
$ k=47,53+2^{48}=2^{47}+…+1^5+2^4+4^3+6^2$
$ k=46,54+2^{47}=2^{46}+…+3^4+1^3+2^2$
$ k=45,55+2^{46}=2^{45}+…+1^5+3^4+1^3+6^2$
$ k=44,56+2^{45}=2^{44}+…+2^4+2^3+8^2$
$ k=43,57+2^{44}=2^{43}+…+2^4+4^3+3^2$
$ k=42,58+2^{43}=2^{42}+…+3^4+2^3+1^2$
$ k=41,59+2^{42}=2^{41}+…+3^4+1^3+3^2$
$ k=40,60+2^{41}=2^{40}+…+2^4+3^3+7^2$
$ k=39,61+2^{40}=2^{39}+…+3^4+2^3+2^2$
$ k=38,62+2^{39}=2^{38}+…+1^5+3^4+2^3+6^2$
$ k=37,63+2^{38}=2^{37}+…+1^6+1^5+3^4+3^3+9^2$
$ k=36,64+2^{37}=2^{36}+…+2^4+4^3+4^2$
$ k=35,65+2^{36}=2^{35}+…+1^5+1^4+3^3+10^2$
$ k=34,66+2^{35}=2^{34}+…+3^4+2^3+3^2$
$ k=33,67+2^{34}=2^{33}+…+1^5+1^4+5^3+2^2$
$ k=32,68+2^{33}=2^{32}+…+1^5+3^4+1^3+7^2$
$ k=31,69+2^{32}=2^{31}+…+1^4+4^3+6^2$
$ k=30,70+2^{31}=2^{30}+…+1^4+1^3+10^2$
$ k=29,71+2^{30}=2^{29}+…+1^6+2^5+2^4+5^3+5^2$
$ k=28,72+2^{29}=2^{28}+…+1^5+1^4+5^3+3^2$
$ k=27,73+2^{28}=2^{27}+…+3^4+2^3+4^2$
$ k=26,74+2^{27}=2^{26}+…+1^7+2^6+2^5+2^4+6^3+1^2$
$ k=25,75+2^{26}=2^{25}+…+3^4+1^3+5^2$
$ k=24,76+2^{25}=2^{24}+…+1^6+2^5+1^4+1^3+13^2$
$ k=23,77+2^{24}=2^{23}+…+3^4+3^3+1^2$
$ k=22,78+2^{23}=2^{22}+…+1^7+2^6+1^5+4^4+2^3+2^2$
$ k=21,79+2^{22}=2^{21}+…+1^5+2^4+5^3+1^2$
$ k=20,80+2^{21}=2^{20}+…+3^4+3^3+2^2$
$ k=19,81+2^{20}=2^{19}+…+1^5+3^4+3^3+6^2$
$ k=18,82+2^{19}=2^{18}+…+3^4+2^3+5^2$
$ k=17,83+2^{18}=2^{17}+…+1^5+3^4+4^3+1^2$
$ k=16,84+2^{17}=2^{16}+…+2^4+4^3+6^2$
$ k=15,85+2^{16}=2^{15}+…+3^4+3^3+3^2$
$ k=14,86+2^{15}=2^{14}+…+3^4+1^3+6^2$
$ k=13,87+2^{14}=2^{13}+…+1^5+2^4+5^3+3^2$
$ k=12,88+2^{13}=2^{12}+…+1^5+1^4+5^3+5^2$
$ k=11,89+2^{12}=2^{11}+…+1^6+1^5+3^4+5^3+3^2$
$ k=10,90+2^{11}=2^{10}+…+1^5+3^4+2^3+8^2$
$ k=9,91+2^{10}=2^{9}+…+1^4+1^3+11^2$
$ k=8,92+2^{9}=2^{8}+…+3^4+3^3+4^2$
$ k=7,93+2^{8}=2^{7}+…+3^4+2^3+6^2$
$ k=6,94+2^{7}=2^{6}+1^5+2^4+5^3+4^2$
$ k=5,95+2^{6}=2^{5}+1^4+5^3+1^2$

Осталось найти вторую половину, три решения для $k=4,3,2$, но я почему-то программу написал так, что она дотуда не ищет

Как видно, перебором пришлось проверять аж на глубину в шесть последних слагаемых с правой стороны.
Выглядит это всё бессистемно, и ясно что решений для каждого $k$ должо быть намного больше, особенно в середине.
То есть перебор это не тот метод, не олимпиадный. Ну хотя бы проверилось что почти всё действительно есть.

[wrest]

Руками донашёл
$k=4;96+2^5=1^4+3^3+10^2$
$k=3;97+2^4=4^3+7^2$
$k=2;98+7^3=21^2$

Теперь найдено что да, всё есть. Осталось доказать по-олимпиадному :)

[Klein]

Докажите что для каждого целого числа $k$, удовлетворяющего $2\leq k \leq 100$, существуют положительные целые числа $b_2,b_3,...,b_{101}$ удовлетворяющие $b_2^2+b_3^3+\dotsb+b_k^k=b_{k+1}^{k+1}+b_{k+2}^{k+2}+\dotsb+b_{101}^{101}$

----
Решение

Рассмотрим уравнение $b_2^2+b_3^3+\dotsb+b_k^k-b_{k+1}^{k+1}-b_{k+2}^{k+2}-\dotsb-b_{100}^{100}=L$ $(1)$

Подбираем положительные целые числа $b_2,b_3,...,b_{100}$ таким образом, чтобы $L$ было положительным.
Число $101$ простое, следовательно числа $100!$ и $101$ взаимно простые. Существуют целые числа $c, d$ удовлетворяющие уравнение $100!c+1=101d$ (следствие соотношения Безу).

Умножаем обе части уравнения $(1)$ на $L^{100!c}$

$(b_2L^{100!c/2})^2+(b_3L^{100!c/3})^3+\dotsb+(b_kL^{100!c/k})^k-(b_{k+1}L^{100!c/k+1})^{k+1}-$ $(b_{k+2}L^{100!c/k+2})^{k+2}-\dotsb-(b_{100}L^{100!c/100})^{100} &= L \cdot L^{100!c} &=(L^d)^{101}$

[wrest]

Klein в сообщении #1570819 писал(а):

Решение

Да, вполне.

Klein в сообщении #1570819 писал(а):

Существуют целые числа $c, d$ удовлетворяющие уравнение $100!c+1=101d$ (следствие соотношения Безу).

Более того, для любого простого $p$ число $(p-1)!+1$ делится на $p$, т.е. $c=1$ (теорема Вильсона).

[Dendr]

Klein в сообщении #1570819 писал(а):

Число $101$ простое, следовательно числа $100!$ и $101$ взаимно простые.

Что интересно... Ведь это для любого количества слагаемых работает.

То есть для наперед заданного $K\ge3$ мы можем для каждого $k: 2\le{k}<K$ выбрать числа $b_2, ..., b_K$, чтобы получить соответствующие равенства. Дело в том, что всегда$\ast$ существует простое $p\le{K}$ такое, что ${K!}\over{p}$ взаимно просто с $p$.
Ну а далее повторяем доказательство, используя вместо $100!$ выражение ${K!}\over{p}$ (а лучше - НОК всех чисел от $1$ до $K$ за исключением $p$), а на место $101$ подставляя $p$.

$\ast$ утверждение не очевидное, но оно следует из того, что между $n$ и $2n$ всегда найдется простое. Если $K$ - простое, просто берем $p=K$.
Иначе: если $K=2N$, берем простое $N<p<2N=K$. Если $K=2N+1$, берем простое $N+1<p<2N+2=K+1$ (но $2N+1$ заведомо составное, поэтому $p<K$). Видно, что $2p>K$, поэтому в разложении $K!$ множитель $p$ встретится только один раз.

Работает уже для $K=3$ (пусть это и тривиальный случай): ищем $a^2=b^3$, тогда просто берем $L=a^2$. Уравнение $2!c+1=3d$ решается $c=d=1$, домножаем $L$ на $L^2$:

$$L^2\cdot a^2=(La)^2=L\cdot L^2=L^3$$

Явно подставляя $L$, получаем, ответ, очевидный изначально: $(a^3)^2=(a^2)^3$.

Для $K=4$ будет $p=3$: $L=a^2-c^4$ (в данном случае его можно считать и отрицательным; в зависимости от того, что больше, $a$ или $c^2$, получится одно из искомых равенств), НОК двойки и четверки равен 4, поэтому получаем уравнение $4x+1=3y$. Например, решением будет $x=2, y=3$.
Тогда домножаем на $L^8$:

$$L^8a^2-L^8c^4=(L^4a)^2-(L^2c)^4=L\cdot L^8=(L^3)^3$$

То есть, для всех пар натуральных $\{a, c\}, a^2\ne c$:
Если $a>c^2$ запишем выражение $\left(a(a^2-c^4)^4\right)^2=\left((a^2-c^4)^3\right)^3+\left(c(a^2-c^4)^2\right)^4$
Если $a<c^2$ - выражение $\left(a(c^4-a^2)^4\right)^2+\left((c^4-a^2)^3\right)^3=\left(c(c^4-a^2)^2\right)^4$

Ну и можно продолжить: для всех $K$ найдется неограниченное количество "семейств" таких равенств.
И это не считая "внесистемных" вроде, для $K=4$: $28^2=8^3+6^4, 29^2+6^3=5^4$ и т.д.