การศึกษาการแลกเปลี่ยนข่าวสารจำนวน 2n คน โดย n เป็นสมาชิก I+ โดยใช้จำนวนครั้งน้อยที่สุด

ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์

กฤตเมธ แก้วชื่น, พชร วิชาดี, สัตยวรรณ ขวัญเมือง

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์

ศุภมิตร วิริยกุลโอภาศ, กิตติพงษ์ ไหลภาภรณ์

โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนวิทยาศาสตร์จุฬาภรณราชวิทยาลัย นครศรีธรรมราช

ปีที่จัดทำโครงงานวิทยาศาสตร์

พ.ศ. 2561

บทคัดย่อโครงงานวิทยาศาสตร์

โครงงานคณิตศาสตร์เรื่อง การศึกษาการแลกเปลี่ยนข่าวสารจำนวน 2n คน เมื่อ n∈I+ โดยใช้จำนวนครั้งที่น้อยที่สุด เพื่อหาจำนวนครั้งและวิธีการหาจำนวนครั้งที่แลกเปลี่ยนข่าวสารกันน้อยที่สุด ซึ่งแต่ละคนมีข่าวคนละ 1 ข่าว แบ่งจำนวนคนเป็น 2 กลุ่มกลุ่มละ n คน คือ ให้สมาชิกในกลุ่มที่ 1 แทนด้วย a1 , a2, … , an จับคู่แลกเปลี่ยนข่าวสารกับกลุ่ม 2 ซึ่งแทนด้วย b1 , b2 , … , bn ในแต่ละครั้งสามารถจับคู่แลกเปลี่ยนข่าวสารกันได้ n คู่พร้อมกันและแต่ละคนสามารถบอกข่าวที่ตัวเองมีทั้งหมดได้เช่นกัน การจับคู่แลกเปลี่ยนข่าวสารโดยต้องไม่มีข่าวซ้ำกันหรือมีข่าวซ้ำกันแค่ครั้งสุดท้าย และนำมาเขียนเป็นลำดับ

จากการศึกษาเรื่องลำดับการนับและคอมบินาทอริก เมื่อทำการจับคู่แลกเปลี่ยนข่าวสารกันโดยต้องไม่มีข่าวซ้ำกันหรือมีข่าวซ้ำกันแค่ครั้งสุดท้าย พบว่าการแลกเปลี่ยนข่าวสาร 2n คน เกิดขึ้นทั้งหมด y ครั้ง เมื่อ y=⌈2n ⌉ ซึ่งการจับคู่แลกเปลี่ยนข่าวสารครั้งที่ 1 เป็น ai-bi ( ai-bi หมายถึง คนที่ i ของกลุ่มที่ 1 จับคู่กับคนที่ i ของกลุ่มที่ 2 ) ครั้งที่ 2 เป็น ai-bi+1 ครั้งที่ 3 เป็น ai-bi+3 โดยมีรูปแบบจากการแลกเปลี่ยนข่าวสารคือ ai-bi+2k-1-1 ให้ k แทนครั้งที่แลกเปลี่ยนข่าวสาร ซึ่งการจับคู่แลกเปลี่ยนข่าวสาร พิจารณาจากข่าวเดิมของ ai ที่จะจับคู่กับ bi ต้องไม่ซ้ำกัน แต่ในการจับคู่ครั้งที่ k ข่าวเดิมของ ai อาจซ้ำกับ bi ได้โดยai รู้ข่าว ai , bi , ai+1, bi+1 , ai+2 , bi+2,…,ai+j , bi+j ; j = 2k-1-1 และ bi รู้ข่าว ai , bi , ai-1 , bi-1 , ai-2 , bi-2 ,…, ai-j , bi-j ; j = 2k-1-1 ทำให้รู้ข่าวซ้ำของ ai และ bi จากรูปแบบการจับคู่เห็นว่า ai ข้ามไปจับคู่กับ bi ที่ข่าวเดิมไม่ซ้ำกัน และ bi ที่ถูก ai ข้ามการจับคู่ เพราะว่ามีข่าวเดิมซ้ำของทั้งคู่คือ ai+2k-2-1 และ bi+2k-2-1

ดังนั้นการจับคู่แลกเปลี่ยนข่าวสารแบบ ai-bi+2k-1-1 มีทั้งหมด ⌈2n ⌉ ครั้ง ซึ่งเป็นจำนวนครั้งที่น้อยที่สุด