การพิสูจน์ความเป็นไปไม่ได้
1.
มีตารางขนาด 8 x 8 ช่อง (รวม 64 ช่อง)
ตัดช่องบนซ้าย กับช่องล่างขวาออกไป (เหลือ 62 ช่อง)
จงหาวิธีวางโดมิโนขนาด 2x1 ช่อง ให้คลุมทั้งตาราง ไม่ให้มีช่องเหลือ
โดยห้ามวางโดมิโนซ้อนกัน หรือตัดมิโนออกเป็นสองส่วน หรือวางออกนอกตาราง
2.
มีเหรียญอยู่ 7 เหรียญ
เหรียญแต่ละเหรียญมี 2 ด้าน คือด้านหัว และก้อย
ในเริ่มแรก เหรียญทั้ง 7 เหรียญวางด้านหัวหมด
จงหาวิธีทำให้เหรียญทั้ง 7 เหรียญเป็นด้านก้อย โดยให้เลือกเหรียญขึ้นมาทีละ 4 เหรียญ แล้วสลับด้าน (คือ หัว -> ก้อย , ก้อย -> หัว) ทำไปเรื่อยๆ จนกว่าจะได้
3.
มี บ้าน 3 หลัง
มี ถังน้ำ, ถังแก๊ส, โรงไฟฟ้า
จงหาวิธีเชื่อมท่อ ให้แต่ละบ้านได้รับท่อน้ำ ท่อแก๊ส ท่อไฟฟ้า โดยห้ามไม่ให้ท่อทั้ง 3 ประเภทวางตัดกัน
อธิบายรูป
ถ้ามีบ้าน 2 หลัง, มี ถังน้ำ กับ ถังแก๊ส
เราจะเชื่อมท่อได้ตามรูปขวา (รูปซ้ายผิด เพราะวางท่อตัดกัน/ทับกัน)
------------------------
เฉลย
ข้อ 1.
พิสูจน์ด้วยการระบายสีขาว กับ สีดำ สลับกันลงในตาราง (เหมือนตารางหมากฮอส)
ตารางขนาด 8 x 8 มี 64 ช่อง จะมีช่องที่เป็นสีขาว 32 ช่อง และสีดำ 32 ช่อง
ให้ช่องบนซ้ายเป็นสีขาว ดังนั้นช่องล่างขวาก็ต้องเป็นสีขาว
ถ้าเราตัดช่อง 2 ช่องนี้ออกไป ตารางจะเหลือสีขาว 30 ช่อง สีดำ 32 ช่อง
สังเกตว่าโดมิโนแต่ละชิ้นที่วางลงไป จะปิดช่องสีขาว และช่องสีดำอย่างละ 1 ช่อง
เมื่อจำนวนช่องสีขาวกับสีดำไม่เท่ากัน เราจึงไม่มีทางใช้โดมิโนคลุมตารางได้
ข้อ 2.
สมมติให้เรามีเหรียญด้านก้อยอยู่เป็นจำนวนคู่ ไม่ว่าเราจะเลือกเหรียญ4เหรียญใดมาสลับ เหรียญด้านก้อยก็ยังเป็นจำนวนคู่อยู่ (เพราะอะไร?)
ในตอนเริ่มต้น เรามีเหรียญก้อยอยู่เป็นจำนวนคู่ (ก็คือ 0 เหรียญ) จากการอุปนัย จะได้ว่า จำนวนเหรียญด้านก้อยจะเป็นจำนวนคู่เสมอ ดังนั้น จึงไม่มีทางทำให้จำนวนเหรียญด้านก้อยเท่ากับ 7 ได้
ข้อ 3.
ช้อนี้พิสูจน์ด้วยการใช้ทฤษฎีกราฟ เรื่องกราฟเชิงระนาบ (planar graph)
กราฟเชิงระนาบ คือ กราฟที่สามารถวาดในระนาบได้ โดยไม่มีเส้นเชื่อมตัดกัน
(ดูเพิ่มเติม : //th.wikipedia.org/wiki/กราฟเชิงระนาบ)
K3,3
เราแทนบ้านแต่ละหลังเป็น vertex (จุดยอด)
และแทนท่อต่อละท่อเป็น edge (เส้นเชื่อม)
เราจะแบ่ง vertex ได้เป็น 2 กลุ่ม คือ {บ้าน1, บ้าน2, บ้าน3} กับ {น้ำ, แก๊ส, ไฟฟ้า}
เมื่อเราเชื่อมท่อตามที่โจทย์กำหนดได้
เราจะได้ edge ดังนี้
(บ้าน1,น้ำ) , (บ้าน1,แก๊ส) , (บ้าน1,ไฟฟ้า) ,
(บ้าน2,น้ำ) , (บ้าน2,แก๊ส) , (บ้าน2,ไฟฟ้า) ,
(บ้าน3,น้ำ) , (บ้าน3,แก๊ส) , (บ้าน3,ไฟฟ้า)
สังเกตว่าไม่มี edge ที่เชื่อมโยง vertex ที่อยู่ในกลุ่มเดียวกัน (คือไม่มี edge ที่เชื่อม บ้าน 1 ไปยัง บ้าน2)
และ vertex แต่ละ vertex จะมี edge เชื่อมโยงไปยังทุก vertex ที่อยู่ในอีกกลุ่ม
เราเรียกว่ากราฟลักษณะนี้ว่า กราฟสองส่วนบริบูรณ์ (complete bipartite graph)
ในกรณีนี้ เราจะแทนกราฟด้วย K3,3
เราจะพิสูจน์ว่า K3,3 ไม่ใช่กราฟเชิงระนาบ
จาก Euler's formula
ถ้า G เป็นกราฟเชิงระนาบเชื่อมโยง (connected planar graph) แล้วจะได้
v - e + f = 2
เมื่อ v=จำนวน vertex, e=จำนวน edge, f=จำนวน face
(face คือพื้นที่ที่ถูกล้อมรอบด้วย edge (ซึ่งรวมถึงพื้นที่ด้านนอกที่มีขนาดไม่จำกัดด้วย))
(พิสูจน์ได้ด้วยการอุปนัย)
กราฟ K3,3 มี v=6, e=9 ดังนั้น f=5
โดยปกติ face แต่ละ faceในกราฟเชิงระนาบ จะต้องมี edge ล้อมรอบอย่างน้อย 3 edge
แต่เนื่องจาก cycle ใน bipartite graph จะมี vertex อยู่บน cycle นั้นเป็นจำนวนคู่เสมอ (เพราะอะไร?)
ดังนั้น face แต่ละ face จึงต้องมี edge อย่างน้อย 4 edge ล้อมรอบ
เราจึงต้องใช้ edge อย่างน้อย = (4 x f) / 2 = 10 edge
(หาร 2 เพราะ edge แต่ละ edge จะถูกใช้ร่วมกันอย่างมาก 2 face)
แต่เรามี edge เพียง 9 edge ซึ่งไม่เพียงพอ
ดังนั้น K3,3 จึงไม่ใช่กราฟเชิงระนาบ
เราจึงเชื่อมท่อตามที่โจทย์กำหนดไม่ได้
| Create Date : 06 สิงหาคม 2548 |
| Last Update : 2 กันยายน 2549 9:27:00 น. |
|
7 comments
|
| Counter : 4066 Pageviews. |
 |
|
|
ผมเข้าใจแล้ว่า ผมไม่รู้เรื่องง่ะ...
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 1 คน [
ทายมะถูกเลย....