ไฟสลับแบบผสมผสาน

Question

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

ในขณะที่มินิเกมที่คุณเคยเห็นมักประกอบด้วยสวิตช์และไฟ 3 ถึง 5 ตัว แต่คราวนี้เป็นคำถามทั่วไป มี$S$ สวิตช์และ $L$ไฟตรงหน้าคุณภายใต้สถานะ "เปิด" และ "ปิด" ผสมกัน คุณได้รับแจ้งว่ามีสวิตช์หลายชุดที่สามารถเปิดไฟได้ทั้งหมด (วิธีแก้ปัญหาไม่จำเป็นต้องมีลักษณะเฉพาะ) คุณต้องการขั้นตอน (พลิกสวิตช์) กี่ขั้น$S$ และ $L$เพื่อรับประกันว่าคุณสามารถเปิดไฟทั้งหมดได้ (ถึงสถานะ "แก้ไขแล้ว" ไม่ใช่แค่ค้นหาวิธีแก้ปัญหา)?

Answer 1

คุณต้องการ

มากที่สุดS + นาที (S, L) - 1ครั้ง

อันดับแรกสิ่งสำคัญที่ควรทราบ:

การพลิกคือการสับเปลี่ยน: การพลิกสวิตช์ 1 จากนั้นสลับ 2 เหมือนกับการพลิกสวิตช์ 2 จากนั้นเปลี่ยน 1 ดังนั้นสิ่งเดียวที่สำคัญคือสวิตช์ที่เปิดและปิดไม่ใช่ลำดับที่คุณพลิกมัน

และคุณยัง เพียงแค่ต้องพลิกสวิตช์แต่ละครั้งให้มากที่สุด - ถ้าคุณพลิกสองครั้งก็เหมือนกับไม่ได้พลิกเลย

ถ้าS≤L:

กำหนดหมายเลขสวิตช์ตามลำดับที่ผู้เล่นลองใช้ (หากผู้เล่นลองใช้ลำดับอื่นคุณสามารถเปลี่ยนหมายเลขสวิตช์ใหม่ได้) หากS≤Lอาจเป็นไปได้ว่า: - สวิตช์แรกที่คุณลองควบคุมแสง 1
- สวิตช์ที่สองที่คุณลองควบคุมแสง 2
- สวิตช์ที่สามที่คุณลองควบคุมแสง 3
- [... ] - สวิตช์ (S-1) ที่คุณลองควบคุมแสง S-1
- สวิตช์สุดท้ายที่คุณพยายามควบคุมไฟทั้งหมด
จากนั้นเพียงสลับ$S$จะต้องพลิก จากนั้นคุณต้องพลิกสวิตช์ 2S-1 เป็นอย่างน้อยไม่ว่าคุณจะใช้กลยุทธ์ใด: คุณจะต้องเปิดสวิตช์ทั้งหมดก่อนที่คุณจะพบสวิตช์ที่จะแก้ปัญหาให้คุณได้จากนั้นคุณจะต้องย้อนกลับและปิด คนอื่น ๆ

และคุณสามารถแก้ปัญหาได้ใน 2S-1พลิกทั้งหมด: พลิกทั้งหมดบันทึกว่าสิ่งใดมีผลต่ออะไรจากนั้นพลิกสิ่งที่คุณต้องการทั้งหมดเพื่อพลิกออก (เนื่องจากมีการกำหนดค่าที่แก้ไขได้คุณสามารถทำได้ในการพลิก S มากที่สุดและคุณไม่จำเป็นต้องพลิกทั้งหมดออกเพราะจะได้รับการแก้ไขตั้งแต่เริ่มต้น)

ถ้าS≥L:

เป็นไปได้ว่าสิ่งเดียวกันจะเกิดขึ้น - แต่คราวนี้สวิตช์ (SL) ตัวแรกที่คุณไม่พยายามทำอะไรเลยและสวิตช์ L ที่เหลือจะถูกตั้งค่าเหมือนเดิม ดังนั้นคุณต้องพลิกสวิตช์ S ทั้งหมดเพื่อค้นหาสวิตช์ที่คุณต้องการจากนั้นปิดสวิตช์ L-1

นี่แสดงให้เห็นว่าเป็นไปได้ที่จะมีการกำหนดค่าสวิตช์ที่บังคับให้ S + L-1 เคลื่อนที่ - แต่เราสามารถบังคับให้ทำมากกว่านี้ได้หรือไม่? คำตอบคือไม่: การกำหนดค่าทั้งหมดจะต้องใช้การเคลื่อนไหว L มากที่สุดเพื่อไปยังสถานการณ์เป้าหมายเมื่อคุณทราบว่าสวิตช์ทำอะไรและพลิกทั้งหมด (อธิบายได้โดยใช้พีชคณิตเชิงเส้นเหนือ𝔽₂ฉันจะพยายามอธิบายสำหรับคนที่ไม่มีพื้นฐานทางคณิตศาสตร์หากคุณรู้แล้วว่า "พีชคณิตเชิงเส้นทับ𝔽₂" หมายถึงอะไรคุณสามารถข้ามไปยังบล็อกที่มีข้อความ สิ่งนี้บอกเราหรือไม่ ".)

ถึงเวลาคิดเลข!

การตั้งค่า:

สร้างแผนภูมิขนาดใหญ่ว่าสวิตช์ใดมีผลต่อไฟใด ตัวอย่างเช่นคุณอาจมีสถานการณ์นี้โดยมีสวิตช์ 8 ตัวและไฟ 5 ดวง

ฉันเขียนเป้าหมายของแต่ละไฟให้ถูกต้องไม่ว่าจะเป็น "คู่" หรือ "คี่" สิ่งที่สำคัญคือไฟอยู่ในสถานะที่ถูกต้องหรือไม่เมื่อเริ่มต้น : หากอยู่ในสถานะที่ถูกต้องเราต้องการเปลี่ยนเป็นจำนวนครั้งเท่ากัน หากอยู่ในสถานะที่ไม่ถูกต้องเราต้องการเปลี่ยนเป็นจำนวนคี่ เราไม่สนใจว่าจะเปิดอยู่และเราต้องการเปิดหรือปิดและเราต้องการให้ปิดทั้งสองอย่างคือ "พลิกจำนวนครั้งเป็นคู่"

ดังนั้น 'ชัยชนะ' มาจากการเลือกคอลัมน์บางคอลัมน์เพื่อเปิดใช้งานนั่นคือสวิตช์บางส่วนเพื่อพลิกเพื่อให้จำนวน X ทั้งหมดในแต่ละแถวตรงกับเป้าหมาย

นี่คือตัวอย่างหนึ่งของชัยชนะ: เราได้เปลี่ยนไฟ 1, 2, 4 และ 5 จำนวน X ในแต่ละแถวนั้นตรงกับเงื่อนไขทางด้านขวาดังนั้นเราจึงชนะ L₁มีการพลิกหนึ่งครั้งซึ่งแปลก L₂มีสองพลิกซึ่งก็คือ; และอื่น ๆ ...

(เป็นกรณีที่ 'คี่ทั้งหมดคือ 1 และทั้งหมด' เป็น 2 แต่ไม่จำเป็นพวกมันอาจเป็นเลขคู่หรือเลขคี่ก็ได้)

สิ่งสำคัญ:

ตอนนี้เรามาดูชุดสวิตช์ มีคำถามที่น่าสนใจที่เราสามารถถามคือถ้าเราเพียงแค่มีสวิทช์เหล่านั้นหลายวิธีการกำหนดค่าที่เราสามารถเข้าถึง?

ความคิดแรกของคุณคือ "ถ้าเรามี n สวิตช์เราสามารถเข้าถึงการกำหนดค่าได้2ⁿเสมอ" แต่นี่ไม่เป็นความจริง: สมมติว่าเราเพิ่งเข้าถึงสวิตช์ 2, 3 และ 8 การ

พลิก 2 และ 3 ด้วยกันจะเหมือนกับการพลิก 8! ผลลัพธ์ทั้งสองจะเปิดเพียงไฟ 3 และ 4 ใน

ทำนองเดียวกันการพลิก 2 และ 8 พร้อมกันจะเหมือนกับการพลิก 3 การพลิก 3 และ 8 จะเหมือนกับการพลิก 2 และการพลิกทั้งสามจะเหมือนกับการทำ ไม่มีไรเลย.

ดังนั้นแม้ว่าดูเหมือนว่าเราสามารถเข้าถึงสวิตช์ 3 ตัว แต่เราก็สามารถเข้าถึงได้เพียง 2 อย่างมีประสิทธิภาพเท่านั้นเราสามารถนำสวิตช์เหล่านี้ออกโดยไม่ต้องเปลี่ยนแปลงสิ่งที่เราทำได้

เราบอกว่าชุดสวิตช์นั้นเป็นอิสระหากไม่มีความซ้ำซ้อนเช่นนี้ ยศของบางชุดเป็นจำนวน "ประสิทธิภาพ" ของสวิทช์ที่เรามี

ตอนนี้ความจริงที่สำคัญ: อันดับของชุดสวิตช์ต้องไม่เกินจำนวนไฟที่ส่งผลกระทบ (โน้มน้าวตัวเองโดยใช้ตัวอย่าง: หากคุณสามารถหาสวิตช์ที่แตกต่างกัน 6 ตัวจากชุดนี้ซึ่งทั้งหมดทำงานอย่างอิสระคุณจะได้รับการกำหนดค่าไฟที่แตกต่างกัน 64 แบบจากสวิตช์เหล่านั้น - แต่มีไฟเพียง 5 ดวงเท่านั้น คุณจะได้รับการกำหนดค่าทั้งหมด 32 แบบเท่านั้น!)

---

แล้วสิ่งนี้บอกอะไรเรา?

เรามีสวิตช์ "ที่มีประสิทธิภาพ" มากที่สุดLเท่านั้น ซึ่งหมายความว่ามีชุดบางส่วนของสวิทช์ L ที่สามารถให้เราอยู่รวมกันเช่นเดียวกับที่ทั้งหมดของสวิทช์สามารถให้เรา (คุณอาจไม่จำเป็นต้องใช้สวิตช์ L เพราะสวิตช์อาจไม่ได้ให้รูปแบบที่เป็นไปได้ทั้งหมด 2 ^ L แต่คุณสามารถเพิ่มสวิตช์ที่ไร้ประโยชน์เพิ่มเติมเพื่อสร้างชุด L ที่จะให้คุณได้ทุกชุดที่เป็นไปได้) ขอเรียกสิ่งนี้ว่า " ชุดขยาย ".

สมมติว่าเราพลิกทั้งหมดยกเว้นสวิตช์สุดท้าย มีสองทางเลือก:
- หากเราสามารถแก้ไขปัญหาได้ด้วยสวิตช์ที่เรามีเราสามารถทำได้ เราจะต้องพลิกสวิตช์ L ส่วนใหญ่เท่านั้น ดังนั้นหลังจากการพลิก S-1 ครั้งแรกเราต้องการ L มากที่สุด
- หากเราไม่สามารถเข้าถึงโซลูชันด้วยสวิตช์ที่เรามีได้นั่นหมายความว่าเราไม่พบชุดสแปน ดังนั้นสวิตช์สุดท้ายจะต้องอยู่ในชุดการขยายที่เป็นไปได้ทั้งหมด! เมื่อเราพลิกสวิตช์สุดท้ายเราจะพบชุดสแปน: จะรวมสวิตช์สุดท้ายและสวิตช์อื่น ๆ ของ L-1 เราไม่จำเป็นต้อง reflip สวิตช์สุดท้ายหรือเราจะสามารถหาทางแก้ไขได้ก่อนที่จะพลิกครั้งแรก ดังนั้นเราต้องกังวลเกี่ยวกับ L-1 อื่น ๆ เท่านั้น ดังนั้นหลังจากการพลิก S ครั้งแรกเราต้องการ L-1 มากที่สุด

และไม่ว่าจะด้วยวิธีใดเราสามารถทำได้ใน S + L-1 พลิกทั้งหมด!