คำตอบของทีม
ไม่ได้ส่งคำตอบ
ไม่ได้ส่งคำตอบ
คะแนน + โบนัสทำเร็ว
0.0
0.0
แชร์
ไม่ได้ส่งคำตอบ 
พิจารณาเซต U = {1, 2, 3, …, N} ที่มีสมาชิก N ตัว เราสามารถเรียงลำดับสับเซตของเซตดังกล่าว (ที่มีจำนวน 2N สับเซต) โดยพิจารณาลำดับของสับเซตสองสับเซต A และ B ที่แตกต่างกันดังนี้ เราจะไล่พิจารณาสมาชิกของเซตจาก 1 ถึง N ตามลำดับ ถ้ามีสมาชิก i ที่มีค่าน้อยที่สุดที่อยู่ในหนึ่งสับเซตแต่ไม่อยู่ในอีกหนึ่งสับเซต เราจะต้องเรียงลำดับให้สับเซตที่มี i อยู่ มาก่อน เงื่อนไขนี้เพียงพอที่จะใช้เรียงลำดับสับเซตทั้งหมดของ U
พิจารณาตัวอย่างที่ N = 3 ดังนี้ เราสนใจเซต U = {1,2,3} เราจะเรียงสับเซตทั้งหมด 8 สับเซต ได้ดังนี้
$\quad${1,2,3}$\quad${1,2}$\quad${1,3}$\quad${1}$\quad${2,3}$\quad${2}$\quad${3}$\quad${}
สังเกตว่าสับเซตที่มี 1 เป็นสมาชิกจะอยู่ด้านหน้า และในบรรดาสับเซตที่มี 1 เป็นสมาชิก สับเซตที่มี 2 จะมาก่อน และเซตว่า {} จะมาเป็นอันดับสุดท้ายเสมอ ในตัวอย่างนี้ สับเซตที่อยู่ในลำดับที่ 5 คือ {2,3} และมีสมาชิก 2 ตัว
ให้พิจารณากรณีที่ U = {1,2,3,…,20} ให้หาว่าสับเซตที่อยู่ในลำดับที่ 256,200 มีสมาชิกกี่ตัว (ในการตอบให้ตอบจำนวนโดยตรง ไม่ต้องใส่เครื่องหมายลูกน้ำ)
พิจารณาตัวอย่างที่ N = 3 ดังนี้ เราสนใจเซต U = {1,2,3} เราจะเรียงสับเซตทั้งหมด 8 สับเซต ได้ดังนี้
$\quad${1,2,3}$\quad${1,2}$\quad${1,3}$\quad${1}$\quad${2,3}$\quad${2}$\quad${3}$\quad${}
สังเกตว่าสับเซตที่มี 1 เป็นสมาชิกจะอยู่ด้านหน้า และในบรรดาสับเซตที่มี 1 เป็นสมาชิก สับเซตที่มี 2 จะมาก่อน และเซตว่า {} จะมาเป็นอันดับสุดท้ายเสมอ ในตัวอย่างนี้ สับเซตที่อยู่ในลำดับที่ 5 คือ {2,3} และมีสมาชิก 2 ตัว
ให้พิจารณากรณีที่ U = {1,2,3,…,20} ให้หาว่าสับเซตที่อยู่ในลำดับที่ 256,200 มีสมาชิกกี่ตัว (ในการตอบให้ตอบจำนวนโดยตรง ไม่ต้องใส่เครื่องหมายลูกน้ำ)
เฉลย
ตอบ 9
แนวคิด
เซตที่อยู่ในลำดับดังกล่าวคือ {1, 2, 8, 10, 11, 12, 15, 16, 17} สามารถทำได้อย่างน้อยสองวิธี
วิธีที่ 1. สามารถเขียนโปรแกรมเพื่อจัดเรียงสับเซตและหาคำตอบโดยตรง (วิธีนี้ถ้า N มีขนาดใหญ่ เช่น มากกว่า 30 จะใช้เวลาการทำงานนานมาก)
วิธีที่ 2. สังเกตว่า ถ้าเราเขียนสับเซตให้อยู่ในรูปของเลขฐานสอง โดยพิจารณาการมีอยู่หรือไม่มีสมาชิกแต่ละตัว ดังตัวอย่างที่ N=3 ดังตัวอย่างด้านล่าง เช่น
{1,2,3} เขียนเป็น 111 {1,2} เขียนเป็น 110 และ {2,3} เขียนเป็น 011
เราจะพบว่าการเรียงลำดับจะเป็นการเรียงเลขฐานสองจากมากไปหาน้อย ดังนี้
{1,2,3} 111
{1,2} 110
{1,3} 101
{1} 100
{2,3} 011
{2} 010
{3} 001
{} 000
ดังนั้นเมื่อพิจารณากรณีที่ N = 20 แต่ละสับเซตจะเป็นจำนวนเลขฐานสองที่มี 20 หลัก มีจำนวน 220 = 1,048,576 สับเซต
สับเซตแรกจะเป็น 11111111111111111111 แทนเซต U สังเกตว่าเป็นเต็มที่มีค่าเท่ากับ 1,048,575
สับเซตสุดท้าย (ลำดับที่ 1,048,576) เป็น 00000000000000000000 แทนเซต {}
สังเกตว่าเป็นจำนวนเต็มที่มีค่าเท่ากับ 0
ในการหาคำตอบ เราจะหาเซตลำดับที่ 256,200 เมื่อเทียบจะพบว่าเป็นค่าจำนวนเต็มที่มีค่าเท่ากับ 1,048,576 - 256,200 = 792,376 เมื่อแปลงเป็นเลขฐานสอง 30 หลักจะได้เป็น
11000 00101 11001 11000 เทียบเท่ากับสับเซต {1, 2, 8, 10, 11, 12, 15, 16, 17} ที่มีสมาชิกจำนวน 9 ตัว