Ketahui apa yang saya sampai kepada • Konstantin Knoop • Tugas sains popular mengenai "Elemen" • Matematik

Tebak apa yang saya buat

Tugas

Kostya mengandung nombor semula jadi K dari 1 hingga 2013 dan bersedia untuk menjawab "ya" atau "tidak" kepada sebarang soalan yang membolehkan jawapan tersebut. Walau bagaimanapun, dia mempunyai hak untuk memberikan jawapan yang salah tidak lebih daripada sekali (untuk semua jawapan).

Sasha ingin bertanya kepada Kostya tidak lebih daripada 15 soalan, mengikut jawapan yang mana dia selalu boleh meneka nombor yang dimaksudkan. Bantuan dia untuk melakukannya.


Petua 1

Biasanya dalam tugas-tugas tersebut, mereka cuba bertanya "perbandingan-perbandingan", iaitu, "Adakah benar nombor anda kurang daripada ini" (atau "lebih daripada ini"). Bagaimanapun, tidak ada keperluan untuk Sasha membataskan dirinya kepada soalan-soalan semacam itu. Jenis pertanyaan yang lebih umum adalah seperti berikut: Sasha menulis beberapa set nombor (yang termasuk beberapa nombor dari 1 hingga 2013) dan meminta Kostya: "Benarkah anda merancang salah satu daripada nombor ini?".


Petua 2

Sekiranya Kostya tidak dapat disalah anggap, Sasha akan mempunyai 11 soalan (fikir mengapa). Oleh itu, Sasha mempunyai empat soalan "dalam stok", dan dia harus cuba bertanya supaya jika pada suatu ketika jawapan Kostya mula bertentangan satu sama lain, maka seseorang boleh meneka nombor K dengan cara yang standard, setiap kali mengurangkan separuh pilihan baki.


Petua 3

Cuba tampil dengan set untuk 11 soalan pertama Sasha supaya setelah menjawabnya Sasha boleh meninggalkan hanya 12 nombor dalam "senarai mencurigakan" – yang disediakan Kostya tidak salah, dan satu lagi angka untuk setiap kesalahan Bone yang mungkin.


Penyelesaian

Mula-mula kita buat apa yang disarankan di hujung 3.

Cara paling mudah untuk melakukan ini adalah dengan menggunakan sistem binari. Sejak 2013 kurang dari 2 tahun11 = 2048, maka rekod perduaan mana-mana nombor yang mungkin dikandung mengandung tidak lebih dari 11 digit. Memandangkan digit dalam setiap digit adalah 0 atau 1, Sasha boleh terus bertanya soalan pertama: "Adakah benar angka itu dalam i-m (kanan) nombor perduaan nombor yang dimaksudkan ialah 1?"dengan melalui semua i dari 1 hingga 11.

Jika Kostya tidak membuat kesilapan dalam menjawab soalan-soalan ini, maka Sasha akan mengetahui semua digit nombor yang dimaksudkan, iaitu, dia akan mengetahui nombor K (walaupun, kerana dia tidak tahu sama ada Kostya salah, dia tidak dapat menyimpulkan bahawa dia tahu nombor yang dimaksudkan). Jika Kostya membuat kesilapan dalam menjawab beberapa soalan, ia akan bermakna nombor yang dimaksudkan K berbeza dari tulang yang diberikan jawapan dalam mana-mana satu bit.Tetapi nombor ini juga hanya satu – dan kerana kesilapan boleh dibuat dalam mana-mana 11 bit, terdapat 11 nombor yang mencurigakan.

Nyatakan 12 nombor dari senarai yang dihasilkan. K0, K1, … , K11 (yang pertama – jika tiada kesilapan, selebihnya – sekiranya terdapat kesilapan dalam menjawab soalan yang sepadan).

Bagaimana seharusnya Sasha bertindak sekarang? Jika dia bertanya soalan seterusnya (lihat petunjuk 1 pada struktur soalan) tentang set d nombor (bagaimanapun, tetapi tidak termasuk K0; contohnya K1, … , Kd) dan mendapat jawapan "ya", ini boleh bermakna salah satu daripada dua perkara: salah satu daripada ini d nombor, sama ada Kostya salah dalam menjawab soalan ini. Tetapi jika Kostya salah, dia hanya dapat meneka K0kerana pilihan lain Kd+1, … , K11 maksudnya Kostya sudah tersilap dalam jawapan kepada beberapa soalan sebelumnya, dan dia tidak dapat membuat kesilapan yang kedua! Jadi, dengan jawapan "ya" Sasha tetap tepat d + 1 pilihan, dan dia memahami bahawa Kostya salah dalam salah satu jawapan yang terdahulu. Sejak selepas soalan ini Sasha mempunyai 3 lagi soalan yang tersisa di rizab itu, dia akan dapat meneka bilangan yang dirancang dari 8 pilihan. Oleh itu, kita boleh meletakkan d + 1 = 8, iaitu d = 7, dan pertimbangkan hanya jawapan "tidak" kepada soalan ke-12.

Jawapannya adalah "tidak" bermakna Kostya benar-benar tidak dapat memikirkan nombor. K1, … , K7 (jika tidak, ia akan menjadi kesilapan kedua). Oleh itu, selepas respon sedemikian, senarai nombor yang mencurigakan berkurangan kepada 5: K0, K8, K9, K10, K11. Berdoa dengan cara yang sama seperti di atas, kami pastikan bahawa dengan soalan ke-13 Sasha boleh bertanya tentang nombor-nombor K8, K9, K10: jika jawapannya adalah ya, dia akan meneka salah satu daripada empat nombor tersebut K0, K8, K9, K10apa untuknya akan cukup untuk dua soalan yang tinggal, dan dalam kes jawapan "tidak" dalam senarai suspek sahaja K0 dan K11.

Sekarang (soalan ke-14) sudah cukup untuk bertanya tentang satu nombor K11. Seperti dalam situasi yang dianalisis di atas, jawapan "ya" akan bermakna bahawa Kostya telah membuat kesilapan, dan kemudian Sasha akan meneka salah satu daripada dua nombor untuk soalan terakhir, ke-15. Nah, selepas jawapan "tidak" soalan ke-15, anda tidak boleh bertanya lagi – Sasha dapat dengan segera menyimpulkan bahawa Kostya telah mengandung K = K0.


Selepas perkataan

1. Adakah mungkin dilakukan tanpa menggunakan sistem perduaan? Ya, tentu saja.

Perhatikan bahawa pada setiap saat "permainan" antara Kostya dan Sasha, keadaan ("keadaan permainan") digambarkan sepenuhnya oleh dua nombor [a; b]: a – bilangan nombor yang dapat ditebak oleh Kostya, dengan syarat dia belum membuat kesilapan, tetapi b – bilangan nombor yang boleh ditebak oleh Kostya, dengan syarat dia telah membuat kesilapan dalam salah satu jawapan yang terdahulu.Permainan bermula dari [2013; 0], tetapi ia harus berakhir pada ketika itu apabila nombor "disyaki" tetap satu-satunya – sama ada di negeri [1; 0] atau pada [0; 1].

Biarkan soalan pertama Sasha berkaitan dengan set d nombor Kemudian selepas jawapan "ya" keadaan baru permainan menjadi [d; 2013 – d], dan selepas jawapan "tidak" – [2013 – d; d] (fikir mengapa ini begitu). Jika Sasha membahagikan set nombor 2013 ke dalam dua bahagian hampir sama, maka dia akan menerima salah satu negeri [1007; 1006] dan [1006; 1007]. Dengan soalan kedua, dia boleh memisahkan setiap bahagian ini dengan separuh – dan mendapat [504; 1006], atau [503; 1007] (di sini, nombor 1007 diperolehi seperti berikut: pertama, nombor 504 dari b = 1007, yang dimasukkan Sasha dalam setnya, dan kedua, 503 nombor dari a = 1006, yang tidak disertakan dalam set itu – tetapi jika Kostya membuat kesilapan dalam menjawab soalan ini, maka nombor-nombor ini boleh dibuat kepada mereka).

Meneruskan untuk bertanya soalan dengan cara yang sama, kita mendapat konsisten

[504; 1006] → [252; 755] → [126; 504] → [63; 315] → [32; 189] → [16; 111] → [8; 64] → [4; 36] → [2; 20] → [1; 11]

(atau [503; 1007] → [251; 755], yang kurang daripada rantaian di atas. Saya segera membenarkan diri saya untuk meninggalkan beberapa pilihan yang sama dalam rantai ini.)

Oleh itu, keadaan "1 + 11" yang diterangkan dalam penyelesaian kami boleh dicapai tanpa menyebut sistem binari.Nah, kemudian [1; 11] → ([1; 4] atau [0; 8]) → ([1; 1] atau [0; 4]) → ([1; 0] atau [0; 2]) → [0; 1].

2. Penyelesaian kami menunjukkan bahawa bukannya angka dari 1 hingga 2013, Sasha dapat membenarkan Kostya meneka nombor 0 hingga 2047, dan masih mengekalkan ramalan untuk 15 soalan. Walau bagaimanapun, ia tidak dapat dijawab dengan soalan generalisasi semula jadi. Biarkan Sasha dibenarkan untuk tidak menetapkan 15, tetapi N soalan. Di mana julat (dari 0 ke M) bolehkah dia membenarkan Kostya untuk meneka nombor-nombor itu supaya soalan-soalan ini cukup untuk meneka?

Jawapan lengkap kepada soalan ini (lebih tepatnya, bukti kesetiaan jawapan ini) jauh dari semudah yang sepertinya sepintas lalu. Ia boleh ditulis seperti ini: jika (di sini [x] – bahagian integer nombor x, iaitu integer terbesar tidak melebihi x) dengan jelas, kemudian M = sdan jika s ganjil kemudian M = s – 1. Ia juga menarik bahawa lebih daripada 20 tahun telah berlalu dari saat menetapkan tugas untuk mendapatkan penyelesaian lengkapnya!

Rupa-rupanya, buat kali pertama, masalah meneka dengan keupayaan untuk membuat kesilapan dalam jawapan telah dirumuskan oleh matematikawan Hungary yang luar biasa, Alfred Renyi dalam artikel 1961 di Hungary. Beberapa tahun kemudian (dalam autobiografinya "The Adventures of Mathematics"), ia dipopularkan oleh ahli matematik Amerika Stanislav Ulam.

"Hawkins and I [David Hawkins, ahli falsafah, penulis buku buku sains popular yang indah di Alam Semula Jadi – Nota auth.] memikirkan tugas yang berkaitan berikut: variasi pada Twenty Questions Game. Satu orang berfikir nombor dalam julat dari satu hingga satu juta (yang hanya kurang dari 220). Seorang lagi dibenarkan untuk meminta sehingga dua puluh soalan, yang mana peserta pertama harus menjawab hanya "ya" atau "tidak." Jelas sekali, nombor itu dapat ditebak jika anda mula bertanya: apakah angka ini dalam separuh pertama satu juta? Dalam soalan seterusnya, separuh selang nombor yang terhasil, dan sebagainya. Pada akhirnya, bilangan itu dapat ditebak dengan kurang daripada log.21,000,000 kali Katakan sekarang bahawa peserta mempunyai hak untuk berbaring sekali atau dua kali. Berapa banyak soalan yang perlu diambil untuk mendapatkan jawapan yang betul? Adalah jelas bahawa untuk meneka salah satu daripada 2n nombor diperlukan lebih banyak n soalan-soalan, kerana ketika dusta diberitahu tidak diketahui. Secara umum masalah ini tidak diselesaikan. "

Penyelesaian lengkap masalah Ulam untuk kes salah satu kesilapan diterima oleh Andrzej Pelz pada tahun 1986, dan untuk dua kesilapan pada tahun 1990. Selepas 10 tahun lagi, ahli matematik berjaya menyelesaikan masalah ini dengan "hak untuk tiga kesalahan." Untuk tugas dengan bkira-kirahanya kes berasingan sahaja yang telah diselesaikan oleh sejumlah besar kesilapan, dan tiada penyelesaian yang lengkap masih belum dijumpai.

3. Jika anda tidak memerlukan penyelesaian yang optimum dan bilangan soalan yang minimum, maka semuanya menjadi lebih mudah. Oleh itu, pada 1991, di Olimpik Matematik Semua Kesatuan, masalah berikut dicadangkan (penulis – A. Andzhans, I. Soloviev, V. Slitinsky.)

Penyiasat datang dengan rancangan untuk soal siasat saksi, menjamin pengesanan jenayah. Dia akan mengajukan soalan yang hanya boleh menjawab "ya" atau "tidak" (soalan yang akan ditanya mungkin bergantung kepada jawapan kepada yang sebelumnya). Penyiasat percaya bahawa semua jawapannya betul, dia mengira bahawa dalam mana-mana variasi jawapan tidak lebih daripada 91 soalan akan ditanya. Buktikan bahawa penyiasat boleh membuat pelan dengan tidak lebih daripada 105 soalan, menjamin penyelesaian jenayah dan sekiranya satu soalan boleh dijawab dengan salah (tetapi mungkin semua jawapan adalah betul).

Penyelesaian masalah ini didasarkan pada idea lain: bagaimana mengubah rencana rancangan soalan asal dengan menambah "soalan kawalan" kepadanya. Pertama, penyelidik meminta 13 soalan pertama mengenai pelan awal, dan kemudian menanyakan soalan ke-14 "Adakah anda berada dalam siri soalan sebelumnya?".Setelah menerima jawapan "tidak", dia boleh terus menanyakan satu siri 12, 11, 10, …, 1 soalan mengenai rancangan itu, mengulangi soalan kawalan selepas setiap siri (fikir mengapa jawapan "tidak" kepada soalan kawalan menjamin bahawa jawapan kepada soalan-soalan siri ini benar-benar setia). Jika jawapan "ya" diterima kepada salah satu soalan kawalan, maka keseluruhan siri terdahulu diulangi, dengan tidak lagi bertanya soalan kawalan. Sekiranya jawapannya adalah "ya" diterima ksoalan kawalan, maka sebagai tambahan kepada rancangan asal perlu bertanya k + (14 – k) = 14 soalan. Perhatikan bahawa kebohongan mungkin ada dalam jawapan kepada soalan kawalan – dalam kes ini, jawapan kepada siri berulang akan sama persis dengan yang pertama kali.

Kenapa "pengubahsuaian rancangan" bukan strategi yang optimum dan tidak menjamin jumlah soalan yang paling sedikit? Sebagai contoh, kerana tugas awal penyelidik adalah sama dengan meneka nombor yang dimaksudkan dari julat dari 0 hingga 291 – 1. Tetapi untuk ini, seperti yang sudah kita ketahui, bukan 105, tetapi hanya 98 soalan yang cukup: 298/99 > 298/27 = 291. Walau bagaimanapun, pengubahsuaian yang dicadangkan dalam masalah Olimpik meningkatkan panjang pelan dari N(N – 1) / 2 soalan tidak lebih daripada N, iaitu, atas perintah akar kuadrat dua kali panjang asal. Itu, secara amnya, juga tidak begitu buruk.

4. Mengapa ahli matematik yang serius melakukan tugas "mainan" sedemikian? Hakikatnya adalah masalah ini sangat dekat dengan masalah teori pengkodan klasik dan berkait rapat dengan mereka (lihat: Pengesanan dan Pembetulan Ralat, Kod Hamming). Sesungguhnya, dalam permainan yang kami terangkan, Kostya dan Sasha dapat bersetuju terlebih dahulu (sebelum Kostya memilih nombor yang dimaksudkan) mengenai senarai pertanyaan yang ditanya (termasuk menyetujui pertanyaan yang akan ditanya kedua ketika menjawab ya untuk pertanyaan pertama, dan yang mana satu jawapan "tidak", dan juga bersetuju dengan soalan berikut). Ini bermakna Kostya hanya dapat menghantar Sasha jujukan 15 jawapan – atau, jika anda suka, urutan 15 aksara "0" dan "1". Untuk setiap urutan itu, Sasha akan dapat meneka ("membina semula") bilangan rancangan Kostya, dan oleh itu menentukan jawapan kepada soalan yang Kostya salah. Ini adalah kod Hamming membetulkan satu kesilapan.

Artikel R. Hamming "Kod yang mengesan dan membetulkan kesalahan" diterbitkan pada tahun 1950 (asal dapat dilihat, misalnya, di sini, PDF, 3.1 MB). Pada masa itu, data asal ke dalam komputer telah dimuatkan dengan menggunakan kad yang meninju, dan peranti input kad yang menumbuk begitu tidak dapat dipercayai sehingga hampir tidak ada dek yang cukup tebal dapat dibaca tanpa kesilapan.Pelancaran program yang mengandungi kesilapan yang membawa kepada kemalangan yang terbaik, selepas itu perhitungan dihentikan dan dek terpaksa dibaca semula, dan paling teruk – untuk berhenti sepenuhnya mesin. Kod-kod yang dicipta oleh Hamming dibenarkan bukan sahaja untuk mengesan kesilapan, tetapi juga untuk membetulkannya secara automatik. Ia adalah revolusi sebenar!

Sejak itu, sememangnya kebolehpercayaan sistem komputer telah meningkat banyak kali, bagaimanapun, kod yang membetulkan kesilapan tidak menjadi kurang popular kerana ini: kini mereka menjadi asas protokol komunikasi. Barisan komunikasi pasti akan dipertingkatkan, tetapi keperluan untuk kod pembetulan tidak akan pernah hilang: kesilapan adalah satelit abadi dari mana-mana aktiviti manusia.


Like this post? Please share to your friends:
Tinggalkan Balasan

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: