เดาว่าฉันจะทำอะไรได้บ้าง• Konstantin Knoop •งานวิทยาศาสตร์ยอดนิยมเรื่อง "Elements" •คณิตศาสตร์

คาดเดาสิ่งที่ฉันทำ

งาน

Kostya รู้สึกจำนวนธรรมชาติ K ตั้งแต่ 1 ถึง 2013 และพร้อมที่จะตอบว่า "ใช่" หรือ "ไม่" กับคำถามใด ๆ ที่ให้คำตอบดังกล่าว อย่างไรก็ตามเขามีสิทธิที่จะให้คำตอบที่ผิดพลาดได้ไม่เกินหนึ่งครั้ง (สำหรับคำตอบทั้งหมด)

Sasha ต้องการถาม Kostya ไม่เกิน 15 คำถามตามคำตอบที่เขาสามารถคาดเดาจำนวนที่ต้องการได้ ช่วย เขาทำมัน


เคล็ดลับ 1

โดยปกติในงานดังกล่าวพวกเขาพยายามที่จะถามคำถาม "เปรียบเทียบ" นั่นคือ "ความจริงที่ว่าหมายเลขของคุณน้อยกว่านี้" (หรือ "มากกว่านี้") อย่างไรก็ตามมีอย่างไม่จำเป็นต้องให้ Sasha จำกัด ตัวเองให้เป็นเพียงคำถามดังกล่าว ประเภทของคำถามทั่วไปมีดังนี้: Sasha เขียนตัวเลขใด ๆ (ซึ่งรวมถึงตัวเลขบางส่วนจาก 1 ถึง 2013) และถาม Kostya: "เป็นความจริงที่คุณวางแผนให้ตัวเลขเหล่านี้หรือไม่?"


เคล็ดลับ 2

ถ้า Kostya ไม่เข้าใจผิดคำถาม 11 ข้อจะเพียงพอสำหรับ Sasha (คิดว่าทำไม) ดังนั้น Sasha มีคำถามสี่คำถามว่า "อยู่ในสต๊อก" และเขาควรจะถามคำถามเพื่อที่ว่าถ้าในบางประเด็นคำตอบของ Kostya เริ่มแย้งกันและกันเราสามารถคาดเดาจำนวนได้ K ในทางมาตรฐานในแต่ละครั้งลดลงครึ่งหนึ่งของจำนวนตัวเลือกที่เหลืออยู่


เคล็ดลับ 3

ลองมาตั้งคำถามสำหรับ Sasha ครั้งแรก 11 คำถามเพื่อให้ Sasha สามารถออกจากหมายเลขได้เพียง 12 รายการใน "รายการที่น่าสงสัย" – หนึ่งครั้งที่ Kostya ไม่ได้เข้าใจผิดและอีกจำนวนหนึ่งสำหรับข้อผิดพลาด Bone ที่เป็นไปได้


การตัดสิน

อันดับแรกเราทำในสิ่งที่แนะนำในเคล็ดลับที่ 3

วิธีที่ง่ายที่สุดในการทำเช่นนี้คือการใช้ระบบไบนารี ตั้งแต่ 2013 มีค่าน้อยกว่า 211 = 2048 แล้วบันทึกไบนารีของตัวเลขที่เป็นไปได้ใด ๆ ที่มีตัวเลขไม่เกิน 11 หลัก เนื่องจากตัวเลขในแต่ละตัวเลขเป็น 0 หรือ 1 Sasha สามารถถามคำถามแรกได้โดยตรง: "เป็นความจริงที่ตัวเลขมา ผม-m (ขวา) จำนวนไบนารีของจำนวนที่ต้องการคือ 1?"โดยจะผ่านทั้งหมด ผม ตั้งแต่ 1 ถึง 11

ถ้า Kostya ไม่ทำผิดพลาดในการตอบคำถามเหล่านี้จากนั้น Sasha จะหาตัวเลขทั้งหมดของจำนวนที่ต้องการนั่นคือเขาจะรู้จำนวน K (แม้ว่าเนื่องจากเขาไม่ทราบว่า Kostya ผิดหรือไม่ก็ตามเขาไม่สามารถสรุปได้ว่าเขารู้จำนวนที่ตั้งใจไว้) ถ้า Kostya ทำผิดพลาดในการตอบคำถามบางอย่างก็จะหมายความว่าจำนวนที่ต้องการ K แตกต่างจากกระดูกที่ให้คำตอบในหนึ่งบิตแต่ตัวเลขนี้เป็นเพียงหนึ่ง – และตั้งแต่ข้อผิดพลาดอาจจะทำในใด ๆ ของ 11 บิตมีจำนวน 11 ตัวที่น่าสงสัย

แสดงเลข 12 จากรายการผลลัพธ์ K0, K1, … , K11 (ครั้งแรก – ในกรณีที่ไม่มีข้อผิดพลาดส่วนที่เหลือ – ในกรณีที่มีข้อผิดพลาดในการตอบคำถามที่เกี่ยวข้อง)

Sasha ควรทำอะไรตอนนี้? ถ้าเขาถามคำถามถัดไป (ดูคำแนะนำ 1 เกี่ยวกับโครงสร้างของคำถาม) เกี่ยวกับชุดของ d ตัวเลข (อย่างไรก็ตาม แต่ไม่รวม K0; ตัวอย่างเช่น K1, … , Kd) และได้คำตอบว่า "ใช่" มันอาจหมายถึงหนึ่งในสองสิ่ง: อย่างใดอย่างหนึ่งเหล่านี้ d ตัวเลขทั้ง Kostya ถูกเข้าใจผิดในคำตอบสำหรับคำถามนี้ แต่ถ้า Kostya ผิดเขาก็เดาได้ K0เพราะตัวเลือกอื่น ๆ Kd+1, … , K11 หมายความว่า Kostya ถูกเข้าใจผิดในคำตอบของคำถามก่อน ๆ และเขาไม่สามารถทำผิดพลาดได้อีก! ดังนั้นด้วยคำตอบ "ใช่" Sasha ยังคงเหมือนเดิม d + 1 ตัวเลือกและเขาเข้าใจว่า Kostya ผิดในคำตอบก่อนหน้านี้ เนื่องจากหลังจากที่คำถามนี้ Sasha มีคำถามเพิ่มอีก 3 คำถามเขาสามารถคาดเดาจำนวน 8 ตัวเลือกได้ ดังนั้นเราจึงสามารถใส่ได้ d + 1 = 8, ie d = 7 และพิจารณาเฉพาะคำตอบ "ไม่" กับคำถามที่ 12

คำตอบคือ "ไม่" หมายความว่า Kostya ไม่คิดตัวเลข K1, … , K7 (มิฉะนั้นจะเป็นความผิดพลาดครั้งที่สองของเขา) ดังนั้นหลังจากการตอบกลับดังกล่าวรายการตัวเลขที่น่าสงสัยลดลงเหลือ 5: K0, K8, K9, K10, K11. การโต้เถียงเช่นเดียวกับข้างต้นเราจะตรวจสอบให้แน่ใจว่าด้วยคำถามที่ 13 Sasha สามารถถามเกี่ยวกับตัวเลขได้ K8, K9, K10: ถ้าคำตอบคือใช่เขาจะต้องคาดเดาหนึ่งในสี่ตัวเลข K0, K8, K9, K10สิ่งที่จะเพียงพอสำหรับคำถามสองข้อที่เหลือและในกรณีของคำตอบ "ไม่" ในรายการที่น่าสงสัยจะยังคงอยู่เท่านั้น K0 และ K11.

ตอนนี้ (คำถามที่ 14) ก็เพียงพอที่จะถามเกี่ยวกับหมายเลขหนึ่ง K11. เช่นเดียวกับในสถานการณ์ที่ได้มีการวิเคราะห์ข้างต้นคำตอบ "ใช่" จะหมายความว่า Kostya ได้ทำผิดแล้ว Sasha จะคาดเดาตัวเลขสองข้อสำหรับคำถามสุดท้าย 15 ข้อ ดีหลังจากคำตอบ "ไม่" ของคำถามที่ 15 คุณจะไม่สามารถถามได้อีกต่อไป – Sasha สามารถสรุปได้ทันทีว่า Kostya ได้ตั้งครรภ์แล้ว K = K0.


เล่ม

1. สามารถทำได้โดยไม่ต้องใช้ระบบไบนารีหรือไม่? ใช่แน่นอน

โปรดสังเกตว่าในแต่ละช่วงเวลาของ "เกม" ระหว่าง Kostya และ Sasha สถานการณ์ ("รัฐเกม") จะอธิบายได้อย่างสมบูรณ์โดยตัวเลขสองตัว [; ]: – จำนวนตัวเลขที่ Kostya สามารถเดาได้หากว่าเขายังไม่ได้ทำผิด แต่ – จำนวนตัวเลขที่ Kostya สามารถเดาได้หากว่าเขาได้ทำผิดในคำตอบก่อนหน้านี้แล้วเกมเริ่มจาก [2013; 0] แต่ควรจะสิ้นสุดในขณะนั้นเมื่อจำนวน "สงสัย" ยังคงเป็นคนเดียว – นั่นคือในสถานะ [1; 0] หรือบน [0; 1]

ให้คำถามแรกของ Sasha เกี่ยวข้องกับชุดของ d หมายเลข จากนั้นหลังจากคำตอบ "ใช่" สถานะใหม่ของเกมกลายเป็น [d; 2013 – d] และหลังจากคำตอบ "ไม่" – [2013 – d; d] (คิดว่าทำไมนี่เป็นเช่นนั้น) ถ้า Sasha แบ่งชุดของตัวเลข 2013 เป็นสองส่วนเกือบเท่ากันแล้วเขาจะได้รับหนึ่งในรัฐ [1007; 1006] และ [1006; 1007] ด้วยคำถามที่สองเขาสามารถแยกชิ้นส่วนเหล่านี้ได้ครึ่งหนึ่งและรับทั้งสอง [504; 1006] หรือ [503; 1007] (นี่จะมีหมายเลข 1007 ดังนี้: อันดับแรกคือตัวเลข 504 ที่มาจาก = 1007 ซึ่ง Sasha รวมอยู่ในชุดของเขาและประการที่สองตัวเลข 503 ที่มาจาก = 1006 ซึ่งเขาไม่ได้รวมไว้ในชุด – แต่ถ้า Kostya ทำผิดพลาดในการตอบคำถามนี้ตัวเลขเหล่านี้อาจถูกสร้างขึ้นมา)

การถามคำถามต่อเนื่องในลักษณะเดียวกับที่เราได้รับอย่างสม่ำเสมอ

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

(หรือ [503; 1007] → [251; 755] ซึ่งน้อยกว่าในห่วงโซ่ข้างต้นฉันอนุญาตตัวเองให้ละเว้นตัวเลือกที่คล้ายกันหลายตัวในห่วงโซ่นี้)

ดังนั้นสถานการณ์ "1 + 11" ที่อธิบายไว้ในโซลูชันของเราอาจถึงได้โดยไม่ต้องกล่าวถึงระบบไบนารีดีแล้ว [1; 11] → ([1; 4] หรือ [0; 8]) → ([1; 1] หรือ [0; 4]) → ([1; 0] หรือ [0; 2]) → [0; 1]

2. โซลูชันของเราแสดงให้เห็นว่าแทนที่จะใช้ตัวเลขตั้งแต่ 1 ถึง 2013 Sasha สามารถอนุญาตให้ Kostya คาดเดาตัวเลขตั้งแต่ 0 ถึง 2047 และยังคงสามารถคาดเดาได้ประมาณ 15 คำถาม อย่างไรก็ตามคำถามที่ไม่ได้เป็นคำถาม generalizing ธรรมชาติมาก ปล่อยให้ Sasha ได้รับอนุญาตให้ตั้งค่าไม่ได้ 15 แต่ว่า ยังไม่มีข้อความ ปัญหา ช่วงใด (จาก 0 ถึง M) เขาสามารถอนุญาต Kostya เดาตัวเลขเพื่อให้คำถามเหล่านี้จะพอเพียงสำหรับการคาดเดาได้รับการรับรอง?

คำตอบที่เต็มไปด้วยคำถามนี้ (อย่างแม่นยำมากขึ้นคือหลักฐานของความถูกต้องของคำตอบนี้) อยู่ห่างไกลจากความเรียบง่ายอย่างที่เห็นได้ในทันที สามารถเขียนได้ดังนี้: ถ้า (ที่นี่ [x] – ส่วนจำนวนเต็มของจำนวน xคือจำนวนเต็มสูงสุดไม่เกิน x) ชัดเจนแล้ว M = sและถ้า s แปลกแล้ว M = s – 1. เป็นเรื่องที่น่าสนใจมากว่า 20 ปีที่ผ่านมานับจากช่วงเวลาแห่งการกำหนดงานเพื่อให้ได้แนวทางที่สมบูรณ์!

เห็นได้ชัดว่าเป็นครั้งแรกที่ปัญหาเดากับความสามารถในการทำผิดพลาดในคำตอบได้รับการกำหนดโดยนักคณิตศาสตร์ที่โดดเด่นฮังการีอัลเฟรด Renyi ในบทความ 1961 ในฮังการี ไม่กี่ปีต่อมา (ในอัตชีวประวัติของเขา "การผจญภัยของคณิตศาสตร์") มันเป็นที่นิยมโดยนักคณิตศาสตร์ชาวอเมริกัน Stanislav Ulam

"ฮอว์กินกับฉัน [เดวิดฮอว์กินส์ปราชญ์ผู้เขียนต่อจากหนังสือวิทยาศาสตร์ภาษายอดเยี่ยมของธรรมชาติที่ยอดเยี่ยม – ประมาณ AUT] ครุ่นคิดเกี่ยวกับงานที่เกี่ยวข้องต่อไปนี้: รูปแบบในเกมยี่สิบคำถาม คนหนึ่งคิดว่ามีจำนวนตั้งแต่ 1 ล้านบาท (ซึ่งน้อยกว่า 2)20) บุคคลอื่นได้รับอนุญาตให้ถามคำถามได้ถึงยี่สิบคำถามซึ่งผู้เข้าร่วมรายแรกต้องตอบว่า "ใช่" หรือ "ไม่" เท่านั้น เห็นได้ชัดว่าตัวเลขนี้สามารถคาดเดาได้หากคุณถามว่าเป็นตัวเลขแรกในช่วงครึ่งล้านหรือไม่? ในคำถามถัดไปอีกครั้งให้ลดลงครึ่งหนึ่งของช่วงเวลาที่เกิดขึ้นของตัวเลขและอื่น ๆ ในท้ายที่สุดจำนวนที่สามารถคาดเดาน้อยกว่าบันทึก21,000,000 ครั้ง สมมติว่าผู้เข้าร่วมมีสิทธิโกหกครั้งหรือสองครั้ง มีคำถามกี่ข้อที่จะได้คำตอบที่ถูกต้อง? เป็นที่ชัดเจนว่าเพื่อที่จะคาดเดาได้ว่าหนึ่งใน 2n จำเป็นต้องใช้หมายเลขเพิ่มเติม n คำถามเพราะเมื่อโกหกบอกไม่เป็นที่รู้จัก โดยทั่วไปปัญหานี้ไม่สามารถแก้ไขได้ "

ทางออกที่สมบูรณ์ของปัญหา Ulam สำหรับกรณีของข้อผิดพลาดหนึ่งได้รับโดย Andrzej Pelz ในปี 1986 และสองข้อผิดพลาดในปี 1990 หลังจากนั้นอีก 10 ปีนักคณิตศาสตร์สามารถแก้ปัญหาได้อย่างสมบูรณ์แบบสำหรับ "ข้อผิดพลาดสามข้อ" สำหรับงานที่มีขเกี่ยวกับเฉพาะกรณีเฉพาะที่แยกต่างหากได้รับการแก้ไขโดยข้อผิดพลาดจำนวนมากและยังไม่พบโซลูชันที่สมบูรณ์

3. หากคุณไม่ต้องการโซลูชันที่เหมาะสมและจำนวนคำถามที่น้อยที่สุดทุกอย่างจะง่ายขึ้น ดังนั้นในปี 1991 ที่ All-Union โอลิมปิกโอลิมปิกปัญหาต่อไปนี้ได้เสนอ (ผู้เขียน – A. Andzhans, I. Soloviev, V. Slitinsky.)

ผู้ตรวจค้นมาพร้อมกับแผนการสอบปากคำของพยานซึ่งรับประกันการตรวจค้นอาชญากรรม เขาจะถามคำถามที่เป็นไปได้ที่จะตอบว่า "ใช่" หรือ "ไม่" (คำถามที่ถามจะขึ้นอยู่กับคำตอบของคำถามก่อนหน้านี้) นักวิจัยเชื่อว่าคำตอบทั้งหมดจะถูกต้องเขาคำนวณว่าในรูปแบบของคำตอบใด ๆ ไม่เกิน 91 คำถามจะถูกถาม พิสูจน์ว่าผู้ตรวจสอบสามารถวางแผนได้โดยไม่เกิน 105 คำถามรับประกันการแก้ปัญหาอาชญากรรมและในกรณีที่สามารถตอบคำถามได้ไม่ถูกต้อง (แต่อาจเป็นได้ว่าคำตอบทั้งหมดถูกต้อง)

การแก้ปัญหานี้ขึ้นอยู่กับแนวคิดอื่น: การปรับเปลี่ยนแผนเดิมของคำถามด้วยการเพิ่ม "คำถามควบคุม" ลงในนั้น ประการแรกผู้ตรวจสอบจะถามคำถามแรก 13 ข้อในแผนแรกและถามคำถามที่ 14 ว่า "คุณเคยตั้งคำถามก่อนหน้านี้หรือไม่"เมื่อได้รับคำตอบว่า "ไม่" เขาสามารถถามคำถามต่อไปได้ 12, 11, 10, … คำถาม 1 ข้อของแผนซ้ำคำถามควบคุมหลังจากแต่ละชุด (คิดว่าทำไมคำตอบ "ไม่" กับคำถามควบคุมจึงรับประกันได้ว่าคำตอบสำหรับคำถามของซีรี่ส์จริงๆแล้ว จริง) ถ้าคำตอบ "ใช่" ได้รับหนึ่งในคำถามควบคุมแล้วชุดก่อนหน้านี้ทั้งหมดจะถูกทำซ้ำโดยไม่ต้องถามคำถามเพิ่มเติมอีก หากได้รับคำตอบว่า "ใช่" kคำถามควบคุมแล้วนอกเหนือจากแผนเดิมจะต้องถาม k + (14 – k) = 14 คำถาม โปรดทราบว่าการโกหกอาจเป็นคำตอบสำหรับคำถามควบคุม – ในกรณีนี้คำตอบของชุดซ้ำจะเหมือนกับคำตอบแรก

เหตุใด "วางแผนการปรับเปลี่ยน" ไม่ใช่กลยุทธ์ที่ดีที่สุดและไม่ได้รับประกันจำนวนคำถามที่น้อยที่สุด ตัวอย่างเช่นเนื่องจากงานเริ่มต้นของผู้ตรวจสอบนั้นเท่ากับการคาดเดาจำนวนที่ต้องการจากช่วงตั้งแต่ 0 ถึง 291 – 1 แต่สำหรับเรื่องนี้อย่างที่เรารู้อยู่แล้วไม่ใช่ 105 แต่มีเพียง 98 คำถามเท่านั้น: 298/99 > 298/27 = 291. อย่างไรก็ตามการแก้ไขที่เสนอในปัญหาการแข่งขันกีฬาโอลิมปิกเพิ่มความยาวของแผน ยังไม่มีข้อความ(ยังไม่มีข้อความ – 1) / 2 คำถามไม่เกิน ยังไม่มีข้อความนั่นคือตามลำดับของรากที่สองของความยาวเดิมสองเท่า ว่าโดยทั่วไปยังไม่เลวร้าย

4. ทำไมนักคณิตศาสตร์ขั้นสูงถึงทำเช่น "ของเล่น" งานเลย? ความจริงก็คือว่าปัญหานี้ใกล้เคียงกับปัญหาคลาสสิกของทฤษฎีการเขียนโค้ดและเกี่ยวข้องกับพวกเขามาก (ดู: การตรวจจับข้อผิดพลาดและการแก้ไข Hamming Code) อันที่จริงในเกมที่เราอธิบายไว้ Kostya และ Sasha สามารถตกลงล่วงหน้าได้ (ก่อนที่ Kostya จะเลือกจำนวนที่ตั้งใจไว้) เกี่ยวกับรายชื่อคำถามที่ถาม (รวมถึงการยอมรับว่าคำถามใดจะได้รับคำถามที่สองเมื่อตอบคำถามใช่กับคำถามแรกและคำถามใด ตอบ "ไม่" และในทำนองเดียวกันเห็นด้วยกับคำถามต่อไปนี้) ซึ่งหมายความว่า Kostya สามารถส่งคำสั่ง Sasha ได้ถึง 15 คำตอบ – หรือถ้าต้องการให้มีลำดับอักขระ 15 ตัว "0" และ "1" สำหรับแต่ละลำดับดังกล่าว Sasha จะสามารถคาดเดาจำนวนแผนการของ Kostya ได้ (และหาคำตอบว่า Kostya เข้าใจผิดว่าเป็นใคร) นี่คือโค้ดของ Hamming ที่แก้ไขข้อผิดพลาด

บทความ "รหัสที่ตรวจพบและแก้ไขข้อผิดพลาด" ของอาร์. แฮมมิงแฮมตีพิมพ์ในปีพ. ศ. 2493 (ต้นฉบับสามารถดูตัวอย่างเช่นนี่ PDF, 3.1 MB) ในเวลานั้นข้อมูลต้นฉบับลงในคอมพิวเตอร์ถูกโหลดโดยใช้บัตรเจาะและอุปกรณ์ป้อนข้อมูลของบัตรเจาะไม่น่าเชื่อถือมากจนเกือบจะไม่มีดาดฟ้าหนาพอที่จะอ่านได้โดยไม่มีข้อผิดพลาดการเปิดตัวโปรแกรมที่มีข้อผิดพลาดนำไปสู่ความผิดพลาดที่ดีที่สุดหลังจากที่การคำนวณหยุดลงและต้องอ่านดาดฟ้าอีกครั้งและที่เลวร้ายที่สุด – เพื่อหยุดการทำงานของเครื่อง รหัสที่คิดค้นโดย Hamming ช่วยให้ไม่เพียง แต่ตรวจหาข้อผิดพลาดเท่านั้น แต่ยังสามารถแก้ไขได้โดยอัตโนมัติ มันเป็นการปฏิวัติจริง!

ตั้งแต่นั้นเป็นต้นมาความน่าเชื่อถือของระบบคอมพิวเตอร์มีเพิ่มขึ้นหลายครั้งอย่างไรก็ตามรหัสที่แก้ไขข้อผิดพลาดไม่ได้รับความนิยมน้อยลงเพราะเหตุนี้จึงเป็นพื้นฐานของโปรโตคอลการสื่อสาร สายการสื่อสารจะดีขึ้นในบางครั้ง แต่ความจำเป็นในการแก้ไขรหัสแทบไม่เคยหายไป: ข้อผิดพลาดคือดาวเทียมนิรันดร์ของกิจกรรมของมนุษย์


Like this post? Please share to your friends:
ใส่ความเห็น

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