PANTIP.COM : X4922557 ปริศนาขับรถหาโรงแรม [คณิตศาสตร์]

ความคิดเห็นที่ 20

มีคนคิดข้อนี้เยอะครับ
แต่ส่วนใหญ่ไม่ได้เข้ามาตอบ

สำหรับคนที่ยังคิดอยู่อย่าเพิ่งสนใจเฉลยนะครับ

นี่ครับเฉลยตามคำขอ

สมมติให้ H1,H2,H3 ถึง HN แทนโรงแรมที่มีราคาต่ำสุดถึงโรงแรมที่มีราคาสูงสุด

กลยุทธ์เราสำรวจ x% ของโรงแรม N หลัง

ถ้า H1 อยู่ในกลุ่มสำรวจ x% นั้นก็จบนะครับ
เราไม่ประสบความสำเร็จแน่นอน
(เพราะโรงแรมหลังจากกลุ่มสำรวจจะไม่มีราคาถูกกว่า H1)

ถ้า H2 อยู่ในกลุ่มสำรวจและ H1 ไม่อยู่
เราประสบความสำเร็จ
ลองหาโอกาสที่ H2 อยู่ในกลุ่มสำรวจ x%
สมมติมีโรงแรม 100 หลัง
เลือกมา x หลัง เลือกได้ C100,x วิธี = A
กำหนดให้ 1 หลังใน x หลังคือ H2
ดังนั้นเราต้องเลือกมาอีก x-1 หลังจาก 99 หลัง
สามารถเลือกได้ C99,x-1 วิธี = B
นั่นคือโอกาสที่ H2 อยู่ในกลุ่มสำรวจ x% คือ = B/A
B/A = (99!/(x-1)!(100-x)!)/(100!/(x!)(100-x)!) = x/100

สรุปโอกาสที่ H2 อยู่ในกลุ่มสำรวจ x%= x/100
โอกาสที่ H1 อยู่ในกลุ่มสำรวจ x% = x/100
โอกาสที่ H1 ไม่อยู่ในกลุ่มสำรวจ x% = 1- (x/100)
โอกาสที่ H2 อยู่ในกลุ่มสำรวจแต่ H1 ไม่อยู่ประมาณเท่ากับ (x/100)(1-(x/100)) อันนี้เป็นแค่ค่าประมาณนะครับเพราะที่ถูกต้อง เราต้องคิดความน่าจะเป็นแบบ sampling without replacement คือจริงๆแล้วมีโรงแรมให้ H1 ลงได้อีกเพียง N-1 หลัง เพราะ H2 จองไปแล้ว 1 หลังในกลุ่มสำรวจ x% แต่ถ้า N มีค่ามากๆโอกาสที่ H1 ไม่อยู่ในกลุ่มสำรวจ x% เมื่อ H2 อยู่ในกลุ่มจะใกล้เคียงกับที่ประมาณไปข้างต้น

กำหนดตัวแปรใหม่ให้ดูง่าย
ให้ y = x/100

โอกาสที่ H2 อยู่ในกลุ่มสำรวจแต่ H1 ไม่อยู่ประมาณเท่ากับ y(1-y) พูดอีกมุมหนึ่งโอกาสนี้ก็คือโอกาสประสบความสำเร็จด้วยกลยุทธ์นี้ของกรณีนี้

ต่อไปมาดูกรณี H3 อยู่ในกลุ่มสำรวจ x% แต่ H2 และ H1 ไม่อยู่ (คิดสัก 3 กรณีที่เหลือคง induce ได้)

โอกาสที่ H3 อยู่ในกลุ่มสำรวจ = y
โอกาสที่ H2 ไม่อยู่ในกลุ่มสำรวจ = 1-y
โอกาสที่ H1 ไม่อยู่ในกลุ่มสำรวจ = 1-y
โอกาสที่ H3 อยู่ในกลุ่มสำรวจโดย H2 และ H1 ไม่อยู่ทั้งคู่เท่ากับ y(1-y)(1-y)

แต่โอกาสนี้ไม่เท่ากับโอกาสประสบความสำเร็จของกรณีนี้นะครับเพราะ H1 กับ H2 มันยังสลับกันได้ ถ้าเราเจอ H1 ก่อน ก็สำเร็จ แต่ถ้าเราเจอ H2 ก่อน ก็ล้มเหลว ดังนั้นโอกาสสำเร็จเท่ากับ y(1-y)(1-y)/2

โอกาสที่ H4 อยู่ในกลุ่มสำรวจโดย H3 H2 H1 ไม่อยู่ในกลุ่มเท่ากับ y(1-y)(1-y)(1-y)

โอกาสประสบความสำเร็จในกรณีนี้เท่ากับ y(1-y)(1-y)(1-y)/3

หาร 3 เพราะมีโอกาส 1 ใน 3 ที่ H1 จะอยู่ก่อน H2 และ H3

คงเห็นภาพนะครับ

สรุปโอกาสประสบความสำเร็จของทุกๆกรณีคือ
y(1-y) + y(1-y)(1-y)/2 + y(1-y)(1-y)(1-y)/3 +...
เป็นอนุกรมอนันต์
(---เข้ามาแก้ไขรอบ 2 ไม่เป็นอนุกรมอนันต์นะครับ เพราะค่า N มีจำกัด ตะกี้รอบแรกตอนพิมพ์เพลินไปนิด แต่สุดท้ายเราก็จับอนุกรมจำกัดประมาณด้วยอนุกรมอนันต์ เพราะอนุกรมแม็กเคลารีนเป็นอนุกรมอนันต์)

ลองจัดให้อยู่ในรูปของเครื่องหมาย sigma แล้วเอาสูตรอนุกรมแม็กเคลารีนที่ให้ในความเห็นที่ 2 เข้าไปจัดแต่งตัวนิดเดียว จะได้หน้าตาเปลี่ยนไปเป็น

-ylny

(ถ้าจัดรูปไม่ได้บอกนะครับ เดี๋ยวจะช่วย)

ความน่าจะเป็นที่จะประสบความสำเร็จคือ -ylny เราต้องการโอกาสประสบความสำเร็จสูงสุดก็หาอนุพันธ์

d(-ylny) = 0
-ydlny + lnyd-y = 0
-y/y - lny = 0
lny = -1
y = 1/e = x/100
x = 100/e = 100/2.7 = 37

นั่นคือคุณจะสำรวจราคาโรงแรม x% แรกของจำนวนโรงแรมทั้งหมด = สำรวจราคาโรงแรม 37% แรกของจำนวนโรงแรมทั้งหมด

แล้วโอกาสจะสำเร็จ = -ylny = -(1/e)ln(1/e) = 1/e = 0.37

มีโอกาสสำเร็จประมาณ 37%
แก้ไขเมื่อ 03 ธ.ค. 49 02:15:37

จากคุณ : ศล - [ 3 ธ.ค. 49 01:31:18 ]