หาบอลคี่ออกมา $18$ ลูกบอลที่ไหน $17$ มีน้ำหนักเท่ากัน
ปัญหานี้มีหลายรูปแบบ สิ่งที่ฉันกำลังทำงานด้วยคือ
มี $17$ ลูกบอลที่มีน้ำหนักเท่ากันและ $1$ลูกที่อาจมีน้ำหนักทั้งหนักหรือเบากว่าที่อื่น ๆ$17$. คุณต้องชั่งน้ำหนักกี่ชั่งในการหาค่าที่แปลกและหนักกว่าหรือเบากว่า
กรณีที่ง่ายกว่าที่คุณทราบว่าลูกบอลคี่หนักกว่าหรือเบากว่านั้นสามารถพบได้ใน $3$มีน้ำหนัก แนวคิดคือการแบ่งไฟล์$18$ ลูกบอลออกเป็นกลุ่ม $6$, พูด, $6A$, $6B$, $6C$. ชั่งน้ำหนัก$6A$ และ $6B$ในระดับ หากพวกเขาสร้างสมดุลซึ่งกันและกันแล้วล่ะก็$6C$มีสิ่งที่แปลกออกไป หากพวกเขาไม่สร้างสมดุลซึ่งกันและกันและ$6A$ จะต่ำกว่าสเกลแล้ว $6A$ มีลูกบอลที่หนักกว่าและคล้ายกันสำหรับ $6B$. ดังนั้นจึงใช้เวลาสูงสุด$1$ ชั่งน้ำหนักเพื่อกำหนดกลุ่มของ $6$กับลูกที่หนักกว่า จากนั้นคุณสามารถแบ่งกลุ่ม$6$ เป็น $3$ กลุ่มของ $2$และด้วยแนวคิดเดียวกันคุณจะพบกลุ่มคี่ของ $2$ ออกด้วยค่าสูงสุด $1$ชั่งน้ำหนัก. จากนั้นคุณจะเหลือเพียงกลุ่ม$2$ และใช้เวลา $1$ชั่งน้ำหนักเพื่อกำหนดลูกที่หนักกว่า โดยรวมแล้วคุณต้องการ$3$ ชั่งน้ำหนักสำหรับกรณีนี้
แต่ตัวแปรที่ยากกว่าของปัญหานี้คือคุณไม่รู้ว่าลูกบอลคี่หนักกว่าหรือเบากว่า ในกรณีนี้ฉันพบว่าคุณต้องการจำนวนสูงสุด$5$ พยายามหาค่าที่แปลกและดูว่ามันหนักกว่าหรือเบากว่า แต่ฉันไม่รู้ว่ามันถูกต้องหรือไม่หรือจะพิสูจน์ได้อย่างไรว่านี่คือจำนวนครั้งต่ำสุดของจำนวนครั้งสูงสุด
ความคิดคล้ายกับปัญหาก่อนหน้านี้ หาร$18$ ลูกบอลเข้าไป $6A$, $6B$, $6C$. เวลานี้ใช้เวลาสูงสุด$2$ พยายามค้นหากลุ่มของ $6$. เช่นชั่งน้ำหนัก$6A$ และ $6B$ ในระดับหนึ่งถ้ามันตรงกัน $6C$คือกลุ่มที่แปลกออกไป ถ้า$6A$ และ $6B$ไม่ตรงกันเราจึงต้องมีการชั่งน้ำหนักเพิ่มเติมเพื่อหาค่าที่แปลกออกไป ดังนั้น$2$ พยายาม
ตอนนี้เมื่อเราพบกลุ่มแปลก ๆ ของ $6$เราใช้แนวคิดเดียวกันซึ่งต้องใช้ความคิดอื่น $2$พยายาม (สูงสุด) จากนั้นเราจะเหลือกลุ่ม$2$. ใช้เวลาอย่างแน่นอน$1$ ชั่งเพราะคุณรับได้ $1$ ลูกจากกลุ่ม $2$ และชั่งน้ำหนักด้วยอีกอันหนึ่ง $16$ลูกบอลที่เรารู้จักคือ ถ้าลูกนี้เหมือนกันลูกที่เหลือจะเป็นลูกคี่ออกมา ดังนั้นจึงใช้เวลาสูงสุด$2+2+1 = 5$พยายามหาลูกบอลที่แปลกออกไป เราไม่จำเป็นต้องชั่งน้ำหนักเพิ่มเติมเพื่อตรวจสอบว่าลูกบอลที่เหลือนี้หนักกว่าหรือเบากว่า
เนื่องจากเมื่อเราพบกลุ่มของ $6$และกลุ่มที่ตามมาของ $2$เรารับค่าสูงสุดของ $2$พยายาม ถ้าต้องใช้$2$ พยายามค้นหากลุ่มคี่ของ $6$ นั่นหมายถึงการชั่งน้ำหนักครั้งที่ 2 ของ $2$ ความพยายามช่วยให้เราตรวจสอบได้ว่าลูกบอลที่แปลกออกไปนี้หนักกว่าหรือเบากว่า
ตัวอย่างเช่นพิจารณา $6A$, $6B$, $6C$อีกครั้ง. สมมติว่าเราชั่งน้ำหนักก่อน$6A$ และ $6B$และพบว่าน้ำหนักไม่เท่ากัน จากนั้นเราก็ชั่งน้ำหนัก$6C$ ด้วยอย่างใดอย่างหนึ่ง $6A$ หรือ $6B$. ถ้าเราชั่ง$6A$ ด้วย $6C$ และพบว่า $6A$ ไม่ตรงกัน $6C$แล้ว $6A$ เป็นสิ่งที่แปลกออกไป แต่ถ้า $6A < 6C (6A > 6C)$แล้วเราก็รู้ $6A$ มีลูกบอลที่มีน้ำหนักน้อยกว่า (มาก)
นี่เป็นแนวทางที่เหมาะสมที่สุดหรือมีวิธีการที่ใช้เพียง $4$ชั่งน้ำหนัก? ลำไส้ของฉันกำลังบอกฉันว่าควรมี$4$ วิธีการชั่งน้ำหนัก
$12$-ball ตัวแปรของปัญหาและวิธีแก้ปัญหาถูกโพสต์ในรูปแบบ http://www.mytechinterviews.com/12-identical-balls-problem. คุณจะเห็นได้ว่าพวกเขาใช้แนวทางที่คล้ายคลึงกันโดยการทำลายไฟล์$12$ ลูกบอลเข้าไป $3$ กลุ่มของ $4$แต่พวกเขาใช้การผสมผสานและการจับคู่ที่น่าสนใจเพื่อค้นหาสิ่งที่แปลกออกไปเท่านั้น $3$ การเคลื่อนไหว
คำตอบ
ฉันไม่ได้ตรวจสอบโซลูชันสำหรับคลาสสิก $12$ ลูกรุ่น http://www.mytechinterviews.com/12-identical-balls-problem. แต่ถ้ามันใช้งานได้มันจะนำไปสู่ไฟล์$4$ โซลูชันการชั่งน้ำหนักสำหรับ $18$ ลูกกรณี
จริงๆแล้วคลาสสิกมีงานพิเศษให้ทำน้อยมาก!
ก่อนอื่นคุณชั่งน้ำหนัก $3A$ เทียบกับ $3B$. หากไม่สมดุลให้พูด$3A > 3B$คุณสามารถค้นหาด้วย $3A$ เทียบกับ $3C$ (ทั้งหมด $3C$ดี) ไม่ว่าลูกเสียจะหนักกว่าหรือเบากว่า จากนั้นคุณจะพบผู้กระทำผิดในกลุ่ม$3$ด้วยการชั่งน้ำหนักอีกครั้ง รวม$3$ การชั่งน้ำหนัก
และถ้า $3A = 3B$จากนั้นคุณจะถูกลดความคลาสสิก $12$- ปัญหาลูกที่สามารถแก้ไขได้ด้วย $3$ การชั่งน้ำหนักเพิ่มเติมรวมเป็น $4$.
ความคิดเพิ่มเติม: ในความเป็นจริง $4$ การชั่งน้ำหนักสามารถแก้ปัญหาได้ $30$ ลูกไม่เพียง $18$.
ในข้างต้นไฟล์ $3A \neq 3B$ สาขานำไปสู่เสมอ $3$การชั่งน้ำหนักรวมซึ่งเป็นการสิ้นเปลือง ลองนึกภาพคุณมี$9+9+12 = 30$ลูกบอล. การชั่งน้ำหนักครั้งแรกสามารถ$9A$ เทียบกับ $9B$. หากไม่สมดุลอีกวินาที$9A$ เทียบกับ $9C$ (ดีทั้งหมด) จะบอกคุณว่าสิ่งที่ไม่ดีนั้นหนักหรือเบาจากนั้นคุณสามารถใช้ได้ $2$ มีน้ำหนักมากขึ้นเพื่อค้นหาผู้ร้ายในหมู่ $9$ (การค้นหา tri-nary) รวมเป็น $4$ การชั่งน้ำหนัก
เมื่อหลายปีก่อนฉันได้ไขคดี (ส่วนขยายไปสู่คลาสสิก) โดยที่ $13$ ลูก (ไม่รู้จักหนัก / เบา) สามารถแก้ไขได้ด้วย $3$ การชั่งน้ำหนักหากคุณสามารถเข้าถึงลูกบอลพิเศษที่ทราบว่าดี - IIRC ที่คุณต้องการ $2$สิ่งพิเศษที่ดีเช่นนี้ ซึ่งหมายความว่า$9+9+13 = 31$ สามารถแก้ไขได้ด้วย $4$ การชั่งน้ำหนักเพราะใน $9A=9B$ กรณีที่คุณเหลืออยู่แน่นอน $13$ สงสัย แต่ลูกบอลพิเศษหลายลูกที่รู้ว่าดี
ฉันสงสัยว่า $31$ ไม่ใช่ขีด จำกัด (สำหรับ $4$การชั่งน้ำหนัก). เมื่อคุณชั่งน้ำหนัก$9A$ เทียบกับ $9C$ผลลัพธ์สามารถเกิดขึ้นได้เพียงสองอย่าง (ตั้งแต่ $9A > 9B$). สิ่งนี้ไร้ประสิทธิภาพมากและอาจมีการแสวงหาผลประโยชน์เพิ่มเติมได้ ...
คุณคงรู้จักความคลาสสิกที่ผูกพันกับ $n$ การชั่งน้ำหนักมีเพียง $3^n$ ผลลัพธ์ที่เป็นไปได้ด้วย $n=4, 3^n = 81$คุณไม่สามารถแก้ปัญหาได้ $\ge 41$ ลูกบอล ($\ge 82$ผลลัพธ์) ฉันไม่ได้พูด$40$ ทำได้ แต่มีช่องว่างระหว่าง $31$ และ $40$...
การชั่งน้ำหนัก 1 : ชั่งน้ำหนัก$1$-$6$ เทียบกับ $7$-$12$. หากผลลัพธ์สมดุลเราก็จะรู้ว่าบอลคี่อยู่ในเซต$13$-$18$ซึ่ง (แน่นอน) ใช้เวลา $3$วัดได้มากขึ้นสำหรับการชั่งน้ำหนักทั้งหมด4ครั้ง
หากการชั่งน้ำหนักครั้งแรกไม่สมดุลให้สมมติว่าไม่มีความชัดเจน$1$-$6$ หนักกว่า $7$-$12$. จากนั้นทำการ ...
การชั่งน้ำหนัก 2 : การชั่งน้ำหนัก$1$-$3$ เทียบกับ $7$-$9$. หากผลการแข่งขันสมดุลลูกบอลคี่อยู่ใน$\{ 4, 5, 6, 10, 11, 12 \}$ซึ่งใช้เวลาอย่างแท้จริง $3$ชั่งน้ำหนักได้มากขึ้นสำหรับการชั่งน้ำหนักทั้งหมด5ครั้ง
หากผลลัพธ์ไม่สมดุลแทนให้สมมติว่าไม่มีการสูญเสียโดยทั่วไปว่า$1$-$3$ หนักกว่า $7$-$9$. จากนั้นเราก็รู้ว่าลูกบอลคี่อยู่ในชุดหกลูกซึ่งต้องชั่งเพิ่มอีกสองลูกสำหรับการชั่งน้ำหนักทั้งหมด5ลูก