Instant Insanity

1 Instant Insanity ศล ประมาณป ค.ศ. 1965 นาย Frank Armbruster ประด!ษฐ$ของเล)นกลปร!ศนา Instant Insanity ซ/0งม1 ยอดขายถ/ง 12 ล4านช!6นในช)วงป 1966-67 เกมของเขาเป;นแบบน16คร>บ ม1กล)องล?กบาศก$ 4 กล)อง แต)ละหน4า ของแต)ละกล)องเป;นส1ใดส1หน/0งใน 4 ส1 จEดหมายของเกมน16ตอ 4 งต)อซ4อนกล)องเป;นคอนโด 4 ช>น 6 ให4แต)ละด4าน ของคอนโดท>ง6 4 ด4าน ม1ส1แต)ละช>6นไม)ซ6Iาก>น (หน/0งส1ปรากฏได4แค)ช>6นใดช>น 6 หน/0งต)อหน/0งด4าน)

Frank Armbruster ด?ไม)ม1อะไรซ>บซ4อนเลยนะคร>บ พร4อมแล4วเราลองมาเล)นก>บ 4 กล)องน16ก>น

สIาหร>บปNญหาข4อน16ถ4าคEณข16เก1ยจลองผ!ดลองถ?ก คEณสามารถใช4กราฟช)วยแก4ปNญหา instant insanity ได4ง)าย ๆ โดยด?จากร?ปภาพคล1ก 0 ล)องแล4วนIามาเข1ยนกราฟ เร!0มจากแยกเข1ยนกล)องละกราฟ ม1 4 กล)องเข1ยน 4 กราฟ กIาหนดให4จEด (node) ของกราฟแสดงส1 4 ส1 (แต)ละกราฟจ/งม1 4 จEด) เส4นเชV0อมระหว)างจEด (edge) คVอ เส4นเชVอ 0 มระหว)างส1ของด4านตรงก>นข4าม ด>งร?ป

กล)องท10 1

กล)องท10 2

2

กล)องท10 3

กล)องท10 4

จากน>6นนIาท>6ง 4 กราฟมารวมก>นโดยใช4หมายเลข 1-4 เข1ยนกIาก>บบนเส4นเชVอ 0 มเพV0อใช4บ)งบอกกล)องท10 1-4 ตามลIาด>บ ได4กราฟรวมด>งร?ป

1 3, 4

4, 1, 2

3

4, 2

3, 1

2

กราฟของเรากราฟน16เชV0อมจEดส1ด4วยเส4นเชVอ 0 มม1ความหมายว)าจEดส1ของจEดท10เชVอ 0 มถ/งก>นน>6นเป;นด4านตรง ข4ามก>นของกล)องเด1ยวก>น เนV0องจากคอนโดท10เราต4องการม1ส10ด4าน ด>งน>6นเรากIาล>งมองหากราฟย)อยสองกราฟ (sub graph) ซ/0งกราฟย)อยแต)ละกราฟจะแทนด4านตรงข4ามก>นของคอนโดสองด4าน เท)าก>บบอกเราว)าแต)ละ กราฟย)อยต4องม1ครบท>6งส10จด E เส4นเชV0อมส1เ0 ส4น (แต)ละเส4นแทนแต)ละช>6นของคอนโดส10ช>6น) และหมายเลขครบท>6ง ส10หมายเลข (ต4องใช4ทง>6 4 กล)อง) โดยแต)ละจEดม1เส4นเชVอ 0 มสองเส4น (หากจEดใดม1เส4นเชV0อมมากกว)าสองเส4น จะ ทIาให4จด E ส1น>6นปรากฏซ6Iาด4านใดด4านหน/0งของคอนโด) และท>ง6 สองกราฟย)อยท10เลVอกมาน16ไม)ใช4เชVอ 0 มร)วมก>น แล4ว เราจะพบคIาตอบว)าได4แก)กราฟย)อยอ>นแรกเร1ยงกล)องส1ด4านหน4าด4านหล>ง ส)วนกราฟย)อยอ1กอ>นจะเป;นส1ดา4 น ซ4าย-ขวา เช)น

4

3

1

2 3

4 1

กราฟย)อยท10 1 กราฟย)อยท10 1: กราฟย)อยท10 2:

2

-4--1--3--2- -4--3--2--1-

กราฟย)อยท10 2

3 ได4ผลล>พธ$คVอ กล)อง กล)อง กล)อง กล)อง

1: 2: 3: 4:

- - - - - - - -

ลIาด>บ 4 ต>วในแต)ละกล)องน>6นอาจเร1ยง หน4า-หล>ง ซ4าย-ขวา ก^ได4คร>บ ขอเพ1ยงให4 2 ต>วแรก และ 2 ต>วหล>งเป;นด4านตรงข4ามก>นเท)าเป;นใช4ได4