Temukan semua segitiga dalam pembedahan dekagon
Di halaman $97$ dari "Four Colors Suffice" karya Robin Wilson, teka-teki berikut muncul:
[P] keluarkan bahwa, jika semua titik sudut dari sebuah dekagon beraturan digabungkan, dan semua sisi serta diagonal dihasilkan tanpa batas, jumlah segitiga yang terbentuk akan menjadi $10,000$.
Dinyatakan bahwa teka-teki, menurut salah satu James Maurice Wilson, dimaksudkan untuk "membutuhkan kecerdikan daripada pengetahuan" untuk solusinya. Saya belum memecahkan masalah, tapi saya rasa saya bisa membuktikannya$10,000$ terlalu besar.
Kita punya $5$ garis memanjang diagonal, dan $10$garis memanjang sisi. Ada$5$ poin ($2$ merah, $2$ abu-abu, dan $1$putih) di masing-masing bekas. Ada$8$ menunjuk pada masing-masing yang terakhir ($2$ masing-masing berwarna hijau, merah, biru, dan abu-abu.)
Ada $1$ titik putih, dan $10$poin dari masing-masing empat warna lainnya. Paling banyak ada satu segitiga untuk setiap rangkaian$3$ poin non-collinear: $$\binom{41}3-10\binom83-5\binom53=10,050$$
Setiap titik hijau berdekatan dengan titik merah, yang pada gilirannya berdekatan dengan titik biru umum. Empat titik tersebut adalah simpul dari sosok seperti layang-layang, tetapi jika kita memilih salah satu$3$di antaranya, tidak ada segitiga, karena diagonal layang-layang tidak tampak. Ini menghilangkan$10\binom43=40$ segitiga.
Demikian pula, setiap titik merah bersebelahan dengan dua titik biru dan titik abu-abu membentuk layang-layang dengan satu diagonal. Dua dari$4$ pilihan $3$ ini dari ini $4$ beri segitiga, tapi $2$pilihan termasuk kedua titik biru tidak. Ini menghilangkan yang lain$20$ segitiga, jadi kita sudah di bawah $10,000$, dan masih banyak pilihan lainnya $3$ titik non-collinear yang tidak berfungsi dengan baik.
Apakah jawaban yang diberikan salah, atau saya melewatkan sesuatu?
Jawaban
Saya bisa membenarkan hitungan dengan tepat $10,000$segitiga. Keluar dari jawaban Misha Lavrov, ada$10,890$cara untuk memilih tiga garis yang saling tidak sejajar dalam diagram. Namun, beberapa dari tripel garis ini akan berpotongan dalam satu titik, jadi ini harus dikurangi untuk mengoreksi hitungan. Yaitu,
Ada $\binom{5}3=10$ tiga kali lipat garis yang berpotongan di tengah dekagon.
Untuk setiap simpul, ada $9$ garis bertemu di puncak, menghasilkan $10\cdot \binom{9}3=840$ tiga kali lipat.
Untuk setiap titik merah di diagram Anda, ada tiga garis yang bertemu di sana, menghasilkan $10\cdot \binom{3}3=10$ tiga kali lipat.
Penomoran simpul $v_1,\dots,v_{10}$, lalu melewati garis $\{v_1,v_6\}$, $\{v_3,v_5\}$, dan $\{v_7,v_9\}$semua berpotongan pada titik yang sama. Mengambil ketiga rotasi ini memberi$10$ lebih banyak tiga kali lipat.
Sama halnya dengan poin terakhir, ada $10$ rotasi dari masing-masing tripel berikut, yang bertemu di dalam dekagon:
- $\{v_1,v_6\},\{v_5,v_8\}$ dan $\{v_4,v_7\}$.
- $\{v_1,v_6\},\{v_3,v_7\}$ dan $\{v_5,v_9\}$.
Mengurangi ini $10+840+10+10+10+10=890$ tiga kali lipat daun persis $10,000$ segitiga.
Nah, solusi Anda melewatkan beberapa segitiga yang dibentuk oleh garis-garis yang bukan merupakan sisi dari dekagon atau diagonal yang menghubungkan simpul yang berlawanan.
Namun, saya merasa saya juga punya solusi, dan solusi saya membuktikannya $10\,000$ agak terlalu kecil ...
Garis yang kita gambar ada $10$ kelas kesetaraan dari garis paralel:
- $5$ kelas kesetaraan yang mengandung $5$garis sejajar masing-masing, sejajar dengan salah satu sisi dekagon. Ini juga termasuk diagonal yang menghubungkan simpul dari dekagon itu$3$ atau $5$ langkah terpisah.
- $5$ kelas kesetaraan yang mengandung $4$garis paralel masing-masing. Ini termasuk diagonal yang menghubungkan simpul dari dekagon itu$2$ atau $4$ langkah terpisah.
Jika kita memilih $3$garis yang berbeda dari tiga kelas kesetaraan yang berbeda, mereka akan membentuk segitiga. Ini memberi kita$$ \underbrace{\binom 53 \cdot 5^3}_{\text{3 lines of first type}} + \underbrace{\binom 52 \cdot 5^2}_{\text{2 lines of first type}} \cdot \underbrace{\binom 51 \cdot 4}_{\text{1 line of second type}} + \\ \underbrace{\binom 51 \cdot 5}_{\text{1 line of first type}} \cdot \underbrace{\binom 52 \cdot 4^2}_{\text{2 lines of second type}} + \underbrace{\binom 53 \cdot 4^3}_{\text{3 lines of second type}} = 10\,890 $$ segitiga.
(Dengan fungsi pembangkit, kita juga bisa mendapatkan angka ini sebagai koefisien $x^3$ di $(1+5x)^5 (1 + 4x)^5$. Sini,$1+5x$ mewakili jumlah cara yang bisa kita pilih $0$ atau $1$ baris dari kelas kesetaraan tipe pertama, dan $1+4x$ represents the number of ways we can choose $0$ or $1$ lines from an equivalence class of the second type. We multiply these together, and take the coefficient of $x^3$ to find cases where we choose $3$ lines total.)