By: Invisible Force 
on 16 November 2011 - 23:49
Tags:
Forums:
"ชาวนาคนหนึ่งมีก้อนหินก้อนหนึ่งหนัก 40 กิโลกรัมไว้สำหรับใช้ชั่งสิ่งของแบบตราชั่งสมดุล, วันหนึ่งหินก้อนนี้ถูกเพื่อนบ้านยืมไป และหลังจากนั้นไม่นานเพื่อนบ้านก็นำหินกลับมาคืน พร้อมกับกล่าวคำขอโทษที่ได้ทำหินแตกออกเป็น 4 ส่วนไปเสียแล้ว แต่ชาวนาได้บอกกลับไปว่าไม่ต้องขอโทษหรอก เพราะกลับดีเสียอีกที่ทำให้เขาสามารถชั่งสิ่งของได้ตั้งแต่ 1 กิโลกรัม, 2, 3, .. ไปจนถึง 40 กิโลกรัมได้เลย"
คำถามคือ หินทั้งสี่ก้อนนั้นมีน้ำหนักเท่าไร โดยที่แต่ละก้อนมีน้ำหนักเป็นเลขจำนวนเต็ม ?
(โจทย์คงไม่ได้ยากเกินไปนะครับ)
Get latest news from Blognone
Follow @twitterapi
นั่งคิดจนได้คำตอบแล้ว
ขออนุญาต share ต่อนะครับ(ขอยังไม่บอกคำตอบ เดี๋ยวคนมาทีหลังไม่ตื่นเต้น)
เย่ คิดออกแล้ว เกือบนอนไม่หลับ 55
สนุกดีครับ :)
ใบ้: 1 10 100 1000
May the Force Close be with you. || @nuttyi
แถมให้ข้อนึง
มีเหรียญอยู่ 8 เหรียญ มีเหรียญปลอมซึ่งน้ำหนักเบากว่า ผมมีตราชั่งเที่ยงตรง(สมดุล)ให้ อยากถามว่าต้องชั่งอย่างมากที่สุด น้อยสุดกี่ครั้งถึงจะรู้ว่าเหรียญปลอมคือเหรียญไหน
May the Force Close be with you. || @nuttyi
เหรียญปลอมมีเหรียญเดียวใช่ไหมครับ ถ้าเหรียญเดียวก็ =
ถ้ามีเหรียญปลอม 1 เหรียญ ผมคิดได้
น้อยที่สุด 2 ครั้ง , มากสุด 3 ครั้ง
เหรียญปลอม 1 เหรียญครับ
May the Force Close be with you. || @nuttyi
3 ครั้งใช่มั้ยฮะ
/2/2/2
มากสุด 2 ครั้ง น้อยสุดก็ 2 ครั้งครับ
ถูกครับ
วิธีคือแบ่งเหรียญเป็น 3 3 2
2.1 ถ้าหนักเท่ากัน แปลว่าเหรียญเบาอยู่ในกองสองเหรียญ เอามาชั่งครั้งที่่ 2 หาเหรียญเบากว่า
2.2 ถ้ากองสามเหรียญฝั่งไหนเบากว่า แปลว่าเหรียญปลอมอยู่ฝั่งนั้น หยิบสองเหรียญใดใดในกองเบามาชั่งครั้งที่ 2 เหรียญไหนเบากว่าเหรียญนั้นปลอม ถ้าเท่ากันเหรียญที่เหลือปลอม
May the Force Close be with you. || @nuttyi
ใช้วีธีแบ่ง 3 กลุ่ม: จะใช้จำนวนการชั่งเพียง 2 ครั้ง จะต้องเจอเหรียญที่เบากว่าแน่นอน
ใช้วีธีแยกสองฝั่งแล้วตัดออกทีละครึ่ง: จะใช้จำนวนการชั่ง 3 ครั้ง จะต้องเจอเหรียญที่เบากว่าแน่นอน
ใช้วีธีสุ่มจับคู่ เลือก วนที่ละเหรียญ: จะใช้จำนวนการชั่งไม่เกิน 7 ครั้ง จะต้องเจอเหรียญที่เบากว่าแน่นอน
(กรณีสุ่มจับคู่ โชคดีเจอ : ก็ใช้เพียง 1 ครั้งครับ)
2 ครั้ง
สูตรคือ ceil(log n / log 3)
หลักการคือ วัตถุจะถูกแบ่งเป็น 3 กอง คือ กองบนตาชั่งด้านซ้าย, ด้านขวาและส่วนที่เหลือ
และการชั่ง 2 ครั้งจะใช้กับวัตถุได้มากที่สุด 9 ชิ้นครับ
ผมมีเวอร์ชันยากกว่านั้นมาฝาก มี 12 เหรียญ เหรียญนึงเบา/หนักกว่าเหรียญอื่นๆ ใช้ตาชั่งได้ 3 ครั้ง 555+
เบา+หนัก = 2ปกติ รึเปล่าครับ = ='
May the Force Close be with you. || @nuttyi
ไม่ใช่ครับ ขอโทษที่ไม่กระจ่าง คือใน 12 เหรียญนั้น มี 1 เหรียญที่มันเบากว่าหรือหนักกว่า 11 เหรียญที่เหลือครับ
ใช้ 3 ครั้งครับ แต่ผมจะเขียนลุยแนวทางไปจนถึงครั้งที่2 ส่วนครั้งที่3ให้ลองพิจารณากันต่อกันนะครับ (เพราะว่าการเขียนอธิบายมันจะแตกซับซ้อนจนไม่น่าอ่าน)
My Solution
เนื่องจากตัวปัญหาไม่ทราบว่าหนักหรือเบากว่า จะตั้ง code ย่อดังนี้
@ชั่งครั้งที่1 (o4 : o4) นอกตาชั่ง o4
-> สมดุล => จะจัดกลุ่มได้ {o4 } { ก8}
-> ไม่สมดุล => จะจัดกลุ่มได้ {บ4, น4 } {ก4}
การเฉลยแบบละเอียดนะครับ เผื่อจะมีประโยชน์กับบางท่านครับ
ขอกำหนด code ย่อ สำหรับการแก้ไขปัญหานี้ดังนี้ครับ
@ชั่งครั้งที่1 ชั่ง (4ย กับ 4ย) เหลือไว้นอกตาชั่ง 4ย
-> สมดุล => แสดง 8 เหรียญที่ชั่งเป็นเหรียญจริง หรือสรุปเป็น code สั้นๆ => {4ย} {8จ}
-> ไม่สมดุล => สามารถสรุปเหรืยญได้เป็น {4บ, 4น } {4จ} ที่ไม่ได้ชั่งเป็นเหรียญจริง
.Answer
เป็นชาวนาที่เก่งคณิตศาตร์มาก ............. T[]T
ก็นะ .. ก็แบบประมาณว่า มีนาเป็น 1000 ไร่ อะคับ .. ก็เลยต้องคิดเลขเยอะหน่อย
ในเมืองไทยก็มีอยู่นะ แถว สุโขทัย
(อันนี้คำตอบ ขำๆ นะครับ)
เริ่มมีคนได้คำตอบในใจกันแล้วนะครับ .. (เก่งๆ กันหลายคน)
แต่เอ .. จะมีใครบ้างน๊า ที่จะมา solve ปัญหาด้วย programming บ้าง ?
If you can't Google it, it doesn't exist ;p
http://www.pasd.wednet.edu/school/mathwasl/hsg.htm
http://answers.yahoo.com/question/index?qid=20081113091352AA85vub
1 3 9 27 ?
คิดอยู่นานเลยทีเดียว
ช่ายๆ ผมได้เลขนี้เหมือนกันครับ https://docs.google.com/document/d/1bIl57n0ZxXMOrsxKIkvnBehbpPki0IpzwcqQCiur3DY/edit
ผมพิสูจน์ทางคณิตศาสตร์ให้ดูนะครับ คราวหน้าจะได้ไม่ต้องกระจายตารางให้เมื่อย ;)
สมมติ f(x1,x2,x3,...,xn) เป็นฟังก์ชันจากเลขจำนวนเต็มบวก ไปยังเลขจำนวนเต็มบวก คือฟังก์ชันน้ำหนักของสิ่งของที่สามารถชั่งได้บนตาชั่ง จากก้อนหินน้ำหนัก x1,x2,x3,...xn ที่นำไปวางถ่วงตาชั่ง
และสร้างสมการ w = l - r โดยที่ w คือน้ำหนักของ, l คือน้ำหนักหินด้านซ้าย, r คือน้ำหนักหินด้านขวา
สังเกตที่ f(1) จะได้ว่า
ดังนั้น เราจะได้ว่า f(1) span {1} (คำว่า span คือ f(1) สามารถก่อให้เกิดเหตุการณ์ใดได้บ้าง)
ต่อมาสังเกตที่ f(3) ได้ว่า f(3) span {3} เหตุผลง่ายๆ เหมือน f(1)
ทีนี้ถ้าเราลองหา f(1,3) เล่นๆ เราจะได้ว่า f(1,3) span {1,2,3,4} (ไม่เขียนให้ดูนะครับ)
==========
แต่ถ้าเราใช้วิธีนี้หา f(1,3,9) ด้วย จะค่อนข้างเสียเวลามาก ดังนั้น เราจะสมมติว่า f(1,3) สามารถสาร้างได้จาก f(1) และ f(3) ลองสังเกต
จากการสังเกตนี้ เราจะได้ว่า
span f(1,3) = ( f(3)-f(1) ) U ( f(3)+f(1) ) U f(1) U f(3) = {2} U {4} U {1} U {3} = {1,2,3,4}ตอนนี้ ถ้ามีประสปการณ์พอ จะบอกได้ว่ามันอยู่ในฟอร์มของการอุปนัย (induction) ซึ่งถ้าลองพิสูจน์หากรณีทั่วไปดู เราจะเขียนได้ว่า
==========
ถ้าลองหา f(1,3,9) จะได้ว่า
span f(1,3,9) = ( f(9)-f(1,3) ) U ( f(9)+f(1,3) ) U f(9) U f(1,3) = {5,6,7,8} U {10,11,12,13} U {9} U {1,2,3,4} = {1,2,3,4,...,12,13}และหา f(1,3,9,27) ได้
span f(27)-f(1,3,9) = {14,15,16,...,26} span f(27)+f(1,3,9) = {28,29,30,...,40} ดังนั้น span f(1,3,9,27) = {1,2,3,...,40}ซตพ.#
ปล.อันนี้ผมอธิบายอย่างง่ายๆ ซึ่งแบบไม่ถูกตามหลักคณิตศาสตร์ทั้งหมดเท่าไหร่นะครับ แฮะๆ เดี๋ยวจะขวัญกระเจิงไปซะก่อน
เข้าใจว่าที่เขากระจายตารางนั่นแค่พิสูจน์เฉยๆครับ
ตอนแรกผมก็คิดด้วยลำดับเหตุการณ์ว่าคงต้องมีหินหนัก 1
แต่พอคิดว่ามันมีความเป็นไปได้ที่ เราจะมีหินหนัก 8 กับ 9 แล้วเอาไปวางสองฝั่ง ก็ชั่ง 1 ได้เหมือนกัน ผมเลยต้องเปลี่ยนกลับไปคิดจาก 39 38
แต่พอคิดได้แล้ว ก็ต้องมานั่งคิดถึง 1 - 40 เหมือนกัน
นานมาแล้ว ผมก็ยังไม่เข้าใจว่าทำไมโจทย์พวกนี้ถึงเรียกว่าโจทย์ coding/programming เพราะว่ามันก็เป็นโจทย์ธรรมดาๆ...
หรือว่าเราขี้เกียจคิดคำตอบ ก็เลยต้องเขียนโปรแกรมมาวนลูปหาคำตอบที่ถูกต้อง :)
ในกรณีนี้ยังงัยมันก็ไม่มีทางเอาไปประโยชน์จริงๆได้อยู่แล้วครับ .. เป็นเพียงการฝึกแปลงความคิดให้เป็น flow หรือ ชุดคำสั่งทางคอมพิวเตอร์เท่านั้นหละครับ
ในกรณีชัดเจนนั้น คือเรื่อง Matrix ครับซึ่งหลายคนคงทราบอยู่แล้วว่า, ปกติการแก้สมการหลายตัวแปร เราก็แก้ด้วยมือก็ได้ครับ แต่ว่าถ้าจะแก้สมการตัวแปรเยอะๆ เราก็สามารถให้คอมพ์มันทำงานให้โดยอาศัย algorithm ของ Matrix โดยทำ operation กันแบบ Matrix มันก็จะ Generic ยืดหยุ่นรองรับการแก้ปัญหาหลายๆ ตัวแปรได้ครับ
ฝึก logic + เทคนิคการเขียนโปรแกรมครับ
ข้อดีของการดูโจทย์แบบนี้เพื่อหาเราสามารถเปลงโจทย์เดิม [A] ไปเป็นอีกโจทย์ที่ equivalent [B] กันได้
ถ้าเกิดเรามี solution ของปัญหา [B] เราก็เอาไปใช้กับ [A] ได้ นอกจากจะไม่ต้องคิดให้เหนื่อยแล้วประสิทธิภาพในการได้มาซึ่งคำตอบก็น่าจะดีที่สุดด้วย
ยกตัวอย่างแล้วกันคุณว่าปัญหา [B] Travelling saleman คุณรู้มั้ยมันเอามาใช้ทำอะไรบ้าง (มีอะไรที่เป็นปัญหา [A] จะแก้โดยใช้ Travelling saleman ได้)
{$user} was not an Imposter
ใช่ครับมันเป็นโจทย์เชาว์ธรรมดาๆ ที่ผมเล่นตั้งแต่เด็กๆ เลย(แน่นอนตอนนั้นไม่มีความรู้ทางโปรแกรมมิ่ง) แต่ผมเชื่อลึกๆ ว่าเด็กที่มี logic ดี เล่นเกมพวกนี้ได้ จะสามารถเขียนโปรแกรมที่ดีได้
May the Force Close be with you. || @nuttyi
มีคำถามเพิ่มเติมครับ
แล้วเราจะรู้ได้อย่างไรว่า มีเพียงคำตอบเดียว ครับ ?
โจทย์นี้ให้เขียนโปรแกรมแก้หรือคิดด้วยหัวเพียวๆ ครับเนี่ย -
มันไม่ง่ายเลยที่จะทำ GIF ให้มีขนาดน้อยกว่า 20kB
ตามแต่ถนัดเลยครับ .. เอาสนุกด้วยครับ
จริงๆ คิดเพียวๆ ถ้ามีพื้นคณิตศาสตร์มาแน่นๆ จะมองปุ๊ปตอบได้ปั๊ปเลยนะ ;)
อย่างงี้ต้องขอเชิญท่าน neizod เข้าสู่โจทย์ชาวนา ข้อถัดไปเลยครับ .. คือ comment กำลังว่างอยู่เลยครับช่วยจัดให้หน่อย