Ciekawe zadanie dowodowe.

[nijak]

Dane są liczby całkowite \(m, n \ge 2\). Wykazać, że istnieją takie dodatnie liczby całkowite \(a_1 < a_2 <\dots < a_m,\) że dla dowolnych
liczb całkowitych \(1 \le i < j \le m\) liczba \(\frac{a_j}{a_j- a_i}\) jest całkowita i podzielna przez \(n\).

[grdv10]

Tym razem moje wątpliwości są poważniejsze. Proszę, pokaż konkurs (już zakończony), z którego pochodzi to zadanie. Muszę mieć pewność, że nie pochodzi z aktualnie trwającego konkursu.

[nijak]

Pochodzi z olimpiady matematycznej z marca 2022 roku.

[grdv10]

I w takiej sytuacji można się zastanawiać. Ale nie mam w Wigilię za wiele czasu na wymyślanie rozwiązań. Oto plik pdf ze strony OM z rozwiązaniami. Warto, żebyś tam czasem patrzał.

https://om.mimuw.edu.pl/static/app_main ... m73_3r.pdf

A to jest strona Olimpiady: https://om.mimuw.edu.pl/

[iwanka]

Do rozwiązania zadania dotarłam razem z Panem szw1710. Idea naszego rozwiązania jest identyczna z rozwiązaniem ze strony OM, ale rozumowanie jest nieco inne. Rozwiązanie na stronach OM sprawdziliśmy dopiero po wymyśleniu naszego.

Lemat. Dla wszystkich \( m, n \geqslant 2 \) istnieją liczby całkowite \( a_1, a_2, \ldots , a_m \leqslant 0 \) takie, że
\[1\leqslant i < j\leqslant m \implies n\ \Big|\ \frac{a_j}{a_j - a_i}.\]

Ustalmy dowolną liczbę naturalną \(n\geqslant 2\). Dowód lematu poprowadzimy indukcyjnie względem \(m\).

1. \( m = 2\)
Określamy, \( a_1 < 0, a_2 = 0.\)Wtedy\[ n | 0 = \frac{a_2}{a_2 - a_1}.\]
2. Założenie indukcyjne: przypuśćmy, że istnieją \( a_1, a_2, \dots , a_m \leqslant 0 \) takie, że\[ 1\leqslant i < j\leqslant n \implies n |\frac{a_j}{a_j - a_i}\](tzn. że teza lematu jest prawdziwa dla \( m \)).

3. Udowodnimy, że teza lematu jest prawdziwa dla \( m+1 \).
Z założenia indukcyjnego istnieją \( a_1, a_2, \ldots , a_m \leqslant 0 \) takie, że\[ 1 \leqslant i < j \leqslant m \implies n |\frac{a_j}{a_j - a_i}.\]Weźmy \( a_{m+1} = 0 \). Niech \( 1 \le i < j \le m+1 \). Dla \( j \leqslant m\) mamy \[n\ \Big|\ \frac{a_j}{a_j - a_i} \]na mocy konstrukcji. Dla \( j = m + 1\) mamy \[n|0=\frac{a_j}{a_j-a_i} = \frac{a_{m+1}}{a_{m+1}-a_i}.\]

Przejdźmy teraz do dowodu właściwej tezy zadania. W tym celu weźmy liczby \( a_1 < a_2 < \ldots < a_m \) spełniające tezę lematu. Przyjmijmy \[b = \prod_{1 \leqslant i < j \leqslant m}(a_j - a_i) > 0\] (pan szw1710 powiedział mi, że jest to wyznacznk Vandermonde'a). Gdyby zdarzyło się \( b < \frac{-a_1}{n} \), to weźmy takie \( k \in \nn \), że \( kb > \frac{-a_1}{n} \). Istnieje zatem \( k \in \nn \) takie, że \( B = kb > \frac{-a_1}{n} \). Dalej, niech \( b_i = a_i + n \cdot B.\)
Skoro \(nB + a_1 > 0\), to \(b_1 > 0\), skąd \[0 < b_1 < \ldots < b_m.\]Niech \( 1 \leqslant i < j \leqslant m.\) Wtedy
\[\frac{b_j}{b_j-b_i} = \frac{a_j + nB}{a_j - a_i} = \frac{a_j}{a_j+a_i} + nk \cdot \frac{\displaystyle\prod_{1 \leqslant r < s \leqslant m}(a_s-a_r)}{a_j - a_i} \in \nn.\]Zatem \[n\ \Big|\ \frac{b_j}{b_j - b_i},\] co kończy dowód tezy postawionej w zadaniu.

Pozdrawiam.

[Tulio]

Prawie idealnie zrobiona indukcja (pierwsza część). Pamiętajmy, że na razie co zrobiłaś to:
1. Napisałaś, że przeprowadzisz dowód indukcyjny
2. Wykazałaś prawdziwość dla \(m=2\)
3. Stworzyłaś założenie indukcyjne (że teza lematu jest prawdziwa dla \(m\))
4. Dowiodłaś, że jeżeli jest prawdziwa dla \(m\) to jest też prawdziwa dla \(m+1\)
5. Skończyłaś, a nie powinnaś (nie skorzystałaś z indukcji!)

Piąty krok nie jest opcjonalny inaczej mamy do czynienia z magią (ostatnie zdanie Pana Jana Kraszewskiego). Proszę zobaczyć na przykłady tutaj

Tak więc na końcu powinno się znaleźć:
"Na mocy zasady indukcji matematycznej prawdziwa jest teza dla każdego \(m\)" - można w tym miejscu też (jak na wikipedii) przedstawić jakie jest prawdziwe twierdzenie.

W szkole (i na forum) dowód bez tego przechodzi "bo wiadomo o co chodzi". W ogólności (na studiach, w pracach) bez tego tylko wspomnieliśmy, że użyjemy indukcji, a de facto tego nie zrobiliśmy i mamy tylko jakieś zapiski z których nic nie wynika.

[grdv10]

Drogi Panie Tulio, rozwiązanie zadania powstało na prośbę użytkownika nijak, o którym wiedzieliśmy, że sroce spod ogona nie wypadł. Owszem, mogliśmy zaznaczyć, że korzystamy z indukcji. Niektóre skróty są po prostu świadome.

Opcjonalność czy też obligatoryjność - jak Szanowny Pan woli - piątego kroku (chyba o ten Panu chodzi...)

Gdyby zdarzyło się \( b < \frac{-a_1}{n} \), to weźmy takie \( k \in \nn \), że \( kb > \frac{-a_1}{n} \).

można skwitować stwierdzeniem, że istnieje liczba naturalna \(k\) o odpowiedniej własności. Jest to wyłącznie kwestia redakcji (jeśli od razu mamy \(b>\frac{-a_1}{n}\), to przyjmujemy \(k=1\) i już).

Tak więc na końcu powinno się znaleźć:
"Na mocy zasady indukcji matematycznej prawdziwa jest teza dla każdego m" - można w tym miejscu też (jak na wikipedii) przedstawić jakie jest prawdziwe twierdzenie.

Zwykle tego rodzaju rozwiązania redagowane są z myślą o odbiorcy z jakimś wyrobionym już stopniem kultury matematycznej. Gdyby pójść jeszcze dalej, trzeba by było podać aksjomaty Peano liczb naturalnych czy udowodnić, że \(1+1=2\).

Pański post jest po prostu niepotrzebnym czepianiem się. Proszę nie podpierać się autorytetem Jana Kraszewskiego, ale swoim.

[Tulio]

Nie czepiam się, informuję. Informuję jak powinno być poprawnie, do tego służy forum, by m.in. udoskonalać pracę wspólnymi siłami.

PS. Pisałem to z nadzieją, że może komuś pomóc w przyszłości z dowodami indukcyjnymi. Bez jawnego poparcia indukcją matematyczną dowód jest niepełny. Proszę nie uważać, że to był atak. To była pomoc.

[grdv10]

Nie czepiam się, informuję. Informuję jak powinno być poprawnie, do tego służy forum, by m.in. udoskonalać pracę wspólnymi siłami.

Merytorykę Pańskiego posta rozumiem. Jeśli przeznaczymy to nasze rozwiązanie dla powszechnego odbiorcy, to istotnie, można Pańskie uwagi uwzględnić. Na szczęście zarzucił Pan brak odpowiednich stwierdzeń i nic więcej. Nie sądzę jednak, że przeciętny forumowy odbiorca jest w stanie zrozumieć rozwiązanie zadania olimpijskiego. Pozwólmy więc sobie czasem na skróty.

PS. Pański dopisek właśnie przeczytałem. Ogólnie twierdzenie o indukcji jest jednym z mniej rozumianych. I rzeczywiście, wielu poprzestaje na sprawdzeniu jego założeń, co formalnie jest zrobione w naszym poście. Ale naprawdę, post był celowany w usera nijak, który wie, o co chodzi.

[Tulio]

Jeśli przeznaczymy to nasze rozwiązanie dla powszechnego odbiorcy, to istotnie, można Pańskie uwagi uwzględnić. [...] Nie sądzę jednak, że przeciętny forumowy odbiorca jest w stanie zrozumieć rozwiązanie zadania olimpijskiego. Pozwólmy więc sobie czasem na skróty.

Przecież to właśnie napisałem:

W szkole (i na forum) dowód bez tego przechodzi "bo wiadomo o co chodzi".

Informacja była dla chętnych, którzy chcieliby coś więcej.

Na szczęście zarzucił Pan brak odpowiednich stwierdzeń i nic więcej.

Nieprawda
Zarzuciłem brak odpowiednich stwierdzeń i wskazałem jak poprawić.

Ale naprawdę, post był celowany w usera nijak, który wie, o co chodzi.

To również rozumiem i ponownie: to nie był atak, a informacja dla innych, którzy kiedyś tutaj wejdą i przeczytają ten post.

[grdv10]

Na szczęście zarzucił Pan brak odpowiednich stwierdzeń i nic więcej.

Nieprawda
Zarzuciłem brak odpowiednich stwierdzeń i wskazałem jak poprawić.

Me culpa. ,,Nic więcej" w mojej wypowiedzi znaczyło, że niczego więcej Pan nie zarzucił. Istotnie, wskazał Pan sposób naprawy.

Może zatem tę dyskusję skwituję w ten sposób:

Osobiście wydaje mi się, że zauważenie, że tezę w wersji dla liczb ujemnych (lemat) można łatwo dostać, udowodnienie lematu, a potem zmodyfikowanie odpowiedniego ciągu nieco upraszcza rozumowania. Natomiast rozwiązanie ze stron OM najpierw zauważa, że wystarczy coś dodać, a potem już dowód idzie bezpośrednio, co uważam za bardziej skomplikowaną metodę. Ale ogólnie zawsze byłem zdania, że dobra jest każda metoda, byle poprawna. Sztuką jest wymyśleć jakiś sposób rozwiązania, a dopiero potem można go upraszczać. Ale my rozwiązaliśmy zadanie celowo nie patrząc na strony OM, co zrobiliśmy dopiero po znalezieniu naszego rozwiązania.

Dziękuję za zabranie głosu. Nadesłane wyjaśnienia przekonują mnie, że to nie było czepialstwo.

PS. Myślę, że zostawimy rozwiązanie w takiej postaci, w jakiej jest, choćby właśnie dla treningu. Niech czytelnicy zobaczą, co można zarzucić i to rzeczywiście będzie miało większy walor dydaktyczny niż poprawianie rozwiązania zgodnie z przedstawionymi tu uwagami.

[Tulio]

Nie da się (ja nie mogę)? do Ciebie / do Pana wysłać wiadomości prywatnej (wolę formę na Ty, Pana Jana Kraszewskiego użyłem z innych znanych mi powód, proszę napisać, jak mamy być na Pan) więc aby nadmienię, że o ile podejrzenie o czepianie się rozumiem, to zdania:

Proszę nie podpierać się autorytetem Jana Kraszewskiego, ale swoim.

niestety nie. Wszak jest to jeden z "dogmatów" nauki by popierać się autorytetem wyższym, w szczególności autorem książek z danej dziedziny (wymóg jaki tu napisałem poznałem dopiero od tego autora). W matematyce najpierw przekonujemy się oczywiście dowodami, ale w przypadku wątpliwości co do dowodu nie znam innej metody jak wskazać, że mądrzejszy ode mnie ma takie a takie zdanie.

PS. Myślę, że zostawimy rozwiązanie w takiej postaci, w jakiej jest, choćby właśnie dla treningu. Niech czytelnicy zobaczą, co można zarzucić i to rzeczywiście będzie miało większy walor dydaktyczny niż poprawianie rozwiązania zgodnie z przedstawionymi tu uwagami.

Zgadzam się.

PS. Przepraszam za tę dyskusję nie na temat, ale patrz: pierwsze zdanie.

[grdv10]

Celowo zabroniłem pisać do siebie PW na tym forum ze względu na pewną część niechcianej korespondencji. Zawsze jest ze mną kontakt choćby przez stronę bloga, gdzie jest adres e-mail, ale to już wymaga kilku zabiegów. Zobaczenia profilu, gdzie linkuję blog i odnalezienia adresu email. Więc jeśli ktoś chce naprawdę skontaktować się ze mną, zawsze może to zrobić.

Myślę, że właściwą formą jest ,,Ty". Powiem tak: sformułowań ,,Szanowny Panie", ,,proszę pana" itp. używam, gdy na coś się zdenerwuję.

Ja też przepraszam za to co złe w moich wypowiedziach. Łapa na zgodę. Dobrego dnia życzę.