Mengapa solusi satu paragraf untuk Masalah IMO 6 1988 bekerja?
Emanouil Atanassov, yang terkenal dikatakan telah menyelesaikan masalah IMO "tersulit" dalam satu paragraf dan kemudian menerima hadiah khusus, memberikan bukti yang dikutip di bawah ini,
Pertanyaan: Misalkan a dan b adalah bilangan bulat positif sehingga $ab+1$ membagi $a^2+b^2$ Menunjukkan bahwa $\frac{a^2+b^2}{ab+1}$ adalah kuadrat dari bilangan bulat
Bukti: $k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Menganggap $k$bukanlah kotak yang sempurna. Perhatikan bahwa untuk solusi integral apa pun$(a,b)$ kita punya $a>0, b>0$karena k bukanlah kuadrat sempurna. Membiarkan$(a,b)$ menjadi solusi integral dengan $a>0, b>0$ dan $a+b$minimum. Kami akan menghasilkan solusi integral lain darinya$(a',b)$ dengan $a'>0 , \ b>0$ dan $a'+b<a+b$. Kontradiksi (Kami menghilangkan argumen untuk sampai pada$(a',b)$)
$a'=0$ cukup untuk $k$berbentuk persegi, tetapi tidak benar secara umum. Bukti ini sepertinya menyiratkan$a'=0$ untuk semua solusi $(a,b)$. Satu-satunya asumsi yang dibantah adalah minimalitas$a+b$, bukan asumsinya $k$bukanlah kotak yang sempurna. Bagaimana pernyataan yang secara remeh mengikuti dari bukti ini?
EDIT: Berikut adalah bukti yang dimodifikasi, tetapi tanpa asumsi $k$ bukanlah kotak yang sempurna.
$k=\frac{a^2+b^2}{ab+1} \implies a^2-kab+b^2=k, k\in \mathbb{Z}$ Membiarkan $(a,b)$ menjadi solusi integral dengan $a>0, b>0$ dan $a+b$minimum. Kami akan menghasilkan solusi integral lain darinya$(a',b)$ dengan $a'>0 , \ b>0$ dan $a'+b<a+b$. Kontradiksi (Kami menghilangkan argumen untuk sampai pada$(a',b)$)
Saya juga telah menghapus kalimat kedua, karena $a,b>0$diberikan dalam pertanyaan. Apa yang disiratkan oleh bukti ini bahwa yang pertama tidak?
Jawaban
- Jika ada solusi $(a,b)$ untuk itu $k$ bukan kuadrat sempurna $a,b>0$.
- Juga, jika ada solusi $(a,b)$ untuk itu $k$ bukanlah kuadrat sempurna, maka akan ada, di antara solusi tersebut, yang untuknya $a+b$ minimal.
- Kemudian penulis menemukan solusi lain $(a',b)$ dengan $a'<a$, yang menyiratkan itu $a'+b<a+b$.
- Tapi itu tidak mungkin, karena kami mengasumsikan itu $(a,b)$ adalah solusinya $a+b$ mengambil nilai terkecil.
Solusi lengkap verbatim dari en.wiki/Vieta jumping :
Lompatan Vieta standar
Konsep lompatan Vieta standar adalah bukti kontradiksi, dan terdiri dari tiga langkah berikut:${}^{[1]}$
- Berasumsi terhadap kontradiksi bahwa ada solusi yang melanggar persyaratan yang diberikan.
- Ambil solusi minimal tersebut menurut beberapa definisi minimalitas.
- Tunjukkan bahwa ini menyiratkan adanya solusi yang lebih kecil, karenanya kontradiksi.
Contoh
Masalah # 6 di IMO 1988: Biarkan $a$ dan $b$ menjadi bilangan bulat positif sehingga $ab + 1$ membagi $a^2 + b^2$. Buktikan itu$\frac{a^2 + b^2}{ab + 1}$ adalah kotak yang sempurna.${}^{[2]}$${}^{[3]}$
- Perbaiki beberapa nilai $k$itu adalah bilangan bulat positif bukan kuadrat. Asumsikan ada bilangan bulat positif$(a, b)$ untuk itu $k = \frac{a^2 + b^2}{ab + 1}$.
- Membiarkan $(A, B)$ menjadi bilangan bulat positif yang $k = \frac{A^2 + B^2}{AB + 1}$ dan semacam itu $A + B$ diminimalkan, dan tanpa kehilangan asumsi umum $A \ge B$.
- Pemasangan $B$, ganti $A$ dengan variabel $x$ untuk menghasilkan $x^2 – (kB)x + (B^2 – k) = 0$. Kita tahu bahwa salah satu akar persamaan ini adalah$x_1 = A$. Dengan sifat standar persamaan kuadrat, kita tahu bahwa akar lainnya memenuhi$x_2 = kB – A$ dan $x_2 = \frac{B^2 – k}{A}$.
- Ekspresi pertama untuk $x_2$ menunjukkan bahwa $x_2$ adalah bilangan bulat, sedangkan ekspresi kedua menyiratkan itu $x_2 \ne 0$ sejak $k$bukanlah kotak yang sempurna. Dari$\frac{x_2^2 + B^2}{x_2B + 1} = k > 0$ selanjutnya mengikuti itu $x_2$adalah bilangan bulat positif. Akhirnya,$ A \ge B$ menyiratkan itu $x_2 = \frac{B^2 − k}{A} < A$ dan dengan demikian $x_2 + B < A + B$, yang bertentangan dengan minimalitas $A + B$.
Saya pikir saya sudah menemukannya dan akan menyinggung bukti Wikipedia yang diberikan dalam jawaban Alexey karena argumennya sama dan saya yakin sumber saya tidak dapat diandalkan dalam langkah "menghilangkan".
Minimalitas $A+B$bertentangan. (2) dan (3) tidak relevan dengan$k$. (4) berkata$x$ tidak bisa $0$ jika $k$bukanlah kotak yang sempurna. Begitu$x\neq 0$. Tapi jika$x\neq 0$, murni melalui aljabar, tidak bergantung $k$menjadi persegi atau tidak, kami bertentangan dengan minimalitas. Jadi, intinya,$(A,B)$ meminimalkan $A+B$. hanya jika$x_2=0$. Karena tidak ada minimum$(A,B)$ berpasangan saat $k$ bukan bujur sangkar, kita dapat menyimpulkan bahwa tidak ada pasangan seperti itu.
Apakah Atanassov menganggap ini sepele atau tidak sehingga dia menyimpannya di kepalanya tetap menjadi misteri.