เลือกไม่ซ้ำ ให้ต่ำที่สุด SNS+ คลิสต์มาสหรรษา

     สวัสดีครับพี่น้อง หลายวันก่อน ผมลองกลับไปเล่นเกมบน Facebook แก้เซ็ง (จริงๆ แล้วก็ไม่รู้ว่าอะไรดลใจให้กลับไปดู) ก็เจอเข้ากับกิจกรรมหนึ่งของ SNS+ ค่ายผู้สร้าง แฮปปี้คนเลี้ยงหมู และเผ่าสนุกที่ติดอยู่พักนึง เป็นกิจกรรมต้อนรับเทศกาลวัน คริสต์มาส ที่ชื่อว่า “SNS+ คริสต์มาสหรรษา” ก็เป็นเรื่องที่ดีนะครับ มีอะไรให้เปลี่ยนบรรยากาศกันบ้าง กิจกรรมนี้ก็ จะมีการลุ้นรางวัล ทาง SNS+ จะมีสิ่งของมาเสนอให้ อันมีมูลค่าเป็นหมื่น และเงินในเกมอีกมูลค่ามากมาย เพื่อเป็นสิ่งจูงใจ สิ่งที่ผู้แข่งขันต้องทำก็คือ ใช้คูปอง ในการเสนอตัวเลขจำนวนเต็มบวกที่มีค่าตั้งแต่หนึ่งเป็นต้นไป มาหนึ่งตัว เพื่อหวังให้ตัวเลขนั้น มีค่าน้อยที่สุด และไม่ซ้ำกับคนอื่นๆ เราก็จะกลายเป็นผู้ชนะไป

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

    
มาพูดถึงประเด็นแรกกันก่อน ทางทฤษฏีเกม /graff

     ถ้าเราสมมุติให้ เกมนี้มีผู้แข่งขันกันสองคน A กับ B แข่งกันเสนอตัวเลขคนละตัว/hope ให้มีค่าน้อยที่สุดและไม่ซ้ำกัน

ทางเลือกและผลที่ A กับ B จะได้รับเป็น

	A เลือก
B เลือก		1	2	3	…
	1	(0,0)	(0,1)	(0,1)	(0,1)
	2	(1,0)	(0,0)	(0,1)	(0,1)
	…	(1,0)	(1,0)	(0,0)	(0,1)

/slow
     เกมนี้จะเห็น ดุลภาพได้ง่ายมาก โดยปรกติแล้ว A กับ B จะไม่ได้ติดต่อกัน แต่ถ้าสมมุติว่า A เกิดรู้ขึ้นมาว่า B จะเลือกเลข 1 ทางเลือกของ A จะเหลือเพียงให้ B ชนะ ไปหรือทั้งคู่เสมอกันด้วยการเลือก 1 ซึ่งไม่ว่าจะเป็นทางไหนถ้าทั้งสองคนหวังจะชนะ เขาต้องเลือก 1 ทั้งคู่ กลายเป็นสมดุลภาพขึ้นมาทันที ไม่ค่อยสนุกอะไร
 /ohn

     พอเปลี่ยนเกมนี้ขึ้นมาเป็นแบบเล่นกันสามคน เกมนี้จะหาสมดุลยภาพ ไม่ได้ขึ้นมาทันที ลองนึกภาพว่าถ้าหาก A มีแหล่งข่าวรู้มาว่า B จะเลือก 1 /whisper สิ่งใดที่ A ควรจะทำ เลือก 1 เพื่อให้ B ไม่ชนะอย่างเดินนะหรือ ถ้าทำเช่นนั้น ผลอาจจะส่งไปทำให้ C ที่เลือกเลขอื่น ชนะขึ้นมาทันที หรือจะเลือกเลขอื่นเพื่อหวังให้ C ใจดีเลือก 1 เหมือนกับ B ไป นอกจากนี้ลองนึกดูว่าถ้า A เกิดรู้เพิ่มขึ้นว่า C จะเลือก 2 /faill A ก็จะหมดโอกาสชนะขึ้นมาทันทีสิ่งที่ A ทำได้คือเพียงเป็นผู้ตัดสินใจว่า เกมนี้จะให้  หรือ C เป็นผู้ชนะกันแน่..
/bouaa

    มาพูดถึงเกมที่เล่นกัน n คน เมื่อเล่นเกม ผู้เล่นแต่ละคนก็จะต้องมีสิ่งทีเรียกกันว่าเป็นกลยุทธ์ ที่ไตรตรองมาแล้วว่าจะเลือกอย่างไงให้มีโอกาสชนะมากๆ สมมุติให้ผู้เล่น n-1 คนมีวิธีการเลือกตัวเลขเหมือนกัน โดยการประเมินจากความน่าจะเป็นแล้ว เป็น

โดยที่

 P_i   คือ ความน่าจะเป็นที่ผู้เล่นคิดแล้วว่า เลข i จะชนะ

ซึ่งแน่นอนว่า

/angel ทีนี้ลองมาคิดกันว่า คน n-1 คนสามารถเลือกเลขได้กี่แบบละอะไรบ้าง ผมขอแจกแจงเป็น

/iron ใช้ความรู้ตอนเรียนคอมบินิสนึง ยกตัวอย่างเช่นผู้แข่งขัน สองคน ซึ่งคิดกันแล้วว่าจะเลือกเลขไม่เกินเลข 3

     แต่ละพจน์ของการกระจายนั้นก็จะมีความหมาย เช่น พจน์ ก็หมายถึงความน่าจะเป็นที่ทังสองคนเลือกเลข 1 เหมือนกัน หรือ ก็คือความน่าจะเป็นคือ คนนึง เลือกเลข 2 อีกคนเลือกเลข 3 ซึ่งเมื่อสลับกันก็ได้สองแบบ พอดีกับ สปส. ข้างหน้าพจน์พอดี อิอิ  /wig

    /snooty ลองมานึกภาพว่า ถ้าเรามี Z₀ อยู่แล้วทำการกระจายมันออก ให้หมด แล้วจัดรูปมันใหม่ เราก็จะสามารถได้พหุนามที่มี P₁ เป็นตัวแปร และตัวอื่นเป็นสมประสิทธ์ได้เหมือนกัน

    /slow เรามามองพจน์ที่มี A₂ กันในทางความหมายคนครับ พจน์นั้นมีก็คือส่วนของกรณีที่มีคนเลือกเลข 1 เพียงคนเดียวทั้งเกม ถ้าเราต้องการเฉพาะพจน์นี้เราจะทำอย่างไรได้มากละ คำตอบก็คือแอบใช้ความรู้ แคลคูลัส เล็กน้อยลงไป

/eyefire จับดิฟเสร็จพจน์ที่มี A₂ จะไม่เหลือ P₁ เราก็แทน P₁ เดิมที่มีด้วย 0 ทำให้พจน์อื่นหายไปเหลือไว้แต่ A₂ ได้ดังนั้นแล้ว
เราก็จะสามารถหาอีกสิ่ง หนึ่งได้นั้นคือความน่าจะเป็นที่จะไม่มีใครชนะในเกมนี้ ที่เลข 1 ให้เป็น

และได้เช่นนั้นแล้วเราก็สามารถหา ความน่าจะเป็นที่จะไม่มีใครชนะได้ในเลข 2

แบบนี้แล้วเราก็จะเป็น รู้แบบเขียนได้เป็น

     /smile เอาเป็นว่าวันนี้จบลงไปเท่านี้ก่อน แล้วกันครับเก็บไว้เล่นกันต่อในวันหลังเรื่องราวนี้ยังอีกยาวไกล และมีที่ให้ได้งัดความรู้สารพัดสาขาวิชามาให้ใช้ได้อีกครับ ได้สนุกกันแน่ติดตามกันต่อแล้วกันครับ /x3 (แม้นว่าจริงแล้วก็ไม่รู้ ว่าจะต้องคิดไปอีกแค่ไหนกว่าจะจบ /yarr)