2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 10:41 


14/06/22
70
Для школьников 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}$

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 11:20 


05/09/16
11674
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 слагаемых}}$$

Верно?

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 12:05 


14/06/22
70
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 слагаемых}}$$

Верно?

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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 13:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 13:50 


05/09/16
11674
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 слагаемых}}$$

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 13:57 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 15:30 


14/06/22
70
Рассмотрим примеры и интервалы.

$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$.

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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 15:33 
Заслуженный участник
Аватара пользователя


16/07/14
8807
Цюрих
[я выше писал бред, неправильно прочитал условие]

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 16:50 


02/04/18
240
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$ так можно попытаться. Но в общем виде не вижу, как доказать.

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 17:55 


02/04/18
240
Собственно, в общем виде приходим к тождеству
$$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$ использовать отдельный подход, их гораздо меньше.

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 19:43 


05/09/16
11674
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$, но я почему-то программу написал так, что она дотуда не ищет :mrgreen: :facepalm:

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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение21.11.2022, 20:47 


05/09/16
11674
Руками донашёл
$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$

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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение22.11.2022, 02:52 


14/06/22
70
Докажите что для каждого целого числа $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}$

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение22.11.2022, 10:32 


05/09/16
11674
Klein в сообщении #1570819 писал(а):
Решение

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

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

 Профиль  
                  
 
 Re: Школьная олимпиадная задача из Австралии
Сообщение22.11.2022, 14:00 


02/04/18
240
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$ и т.д.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group