จงตรวจสอบการพิสูจน์

[kanji]

ช่วยตรวจสอบการพิสูจน์ให้หน่อยนะครับว่า"วัวทุกตัวมีสีเดียวกัน"
ใช่หรือไม่

ให้ P(k) แทนข้อความ " วัวทุก ๆ k ตัวมีสีเดียวกัน" เห็นได้ชัดว่า
P(1) เป็นจริง ต่อไปสมมติว่า P(k) เป็นจริง นั่นคือ วัวทุก ๆ k ตัวมีสีเดียวกัน เราจะแสดงว่า P(k+1) เป็นจริงด้วย พิจารณาวัว k+1 ตัวใด ๆ นำวัวตัวหนึ่งออกจากการพิจารณา ดังนั้น วัวที่เหลือจะเป็นวัวจำนวน k ตัว จากที่เราสมมติว่า วัวทุก ๆ kตัว มีสีเดียวกัน ดังนั้น วัว k ตัวนี้จึงมีสีเดียวกัน นำวัวที่ถูกแยกออกตอนแรกกลับเข้ามาและนำวัวอีกหนึ่งตัวอื่นออกไปแทน ในทำนองเดียวกันเราจะได้ว่า วัว k ตัวกลุ่มใหม่ นี้มีสีเดียวกัน นั่นคือวัวทั้งหมด k+1 ตัวจึงมีสีเดียวกัน หรือ P(k+1) เป็นจริงนั่นเอง

[gon]

ผมว่ามันแปลก ๆ ตรงที่อยู่ ๆ บอกว่าไป " มองวัวที่มี k + 1 ตัว แล้ว หยิบออกไป 1 ตัว "

ตรงนี้ผมคิดว่าไม่น่าจะถูกนะ. การพิสูจน์ P(k + 1) ว่าเป็นจริง มันน่าจะเป็น เราหยิบตัว 1 ตัวใด ๆ ไปรวมกับวัวที่มี k ตัว จึงกลายเป็น k + 1 ซึ่งข้อความนี้เป็นเท็จแน่นอน เพราะ มีโอกาสอยู่เกือบ 100% ที่จะได้วัวที่มีสีต่างกับเดิม

การไปมองวัวที่มีอยู่ k + 1 ตัว มันจะเหมือนกับการยอมรับไปแล้วว่า P(k + 1) เป็นจริง การหยิบออกไป 1 ตัว แล้วบอกว่า วัวที่เหลือ k ตัว จะต้องเป็นจริงด้วย จึงไม่น่าจะถูกต้อง

คนอื่นคิดเห็นอย่างไรครับ ?

[nooonuii]

จริงๆแล้วต้องพิสูจน์ P(2) ให้จริงก่อนครับ เพราะในขั้นอุปนัยเราเอาวัวอย่างน้อยสองตัวมาเปรียบเทียบกันซึ่งจะทำไม่ได้ถ้า P(2) ไม่เป็นจริง
แต่ P(2) จริงป่าวล่ะ ?

ยังไม่ว่างคิดเรื่องหวยเลย แต่ไม่เป็นไรขอแสดงความเห็นเรื่องนี้ก่อนละกัน

การพิสูจน์นี้มีปัญหาในส่วนของการ induction จาก p(k) ไปสู่ p(k+1) แต่คุณกรอาจมองวิธีพิสูจน์นี้ไม่เข้าใจ ผมขอเรียบเรียงให้ใหม่นะครับ

สมมติว่า p(k) จริง ดังนั้น "วัวทุกๆ k ตัวมีสีเดียวกัน"

สมมติเริ่มต้นเรามีวัวอยู่ k ตัว โดยข้อสมมติจะได้ว่า วัวทั้ง k ตัวนี้มีสีเดียวกัน
จากนั้นเราเพิ่มวัวอีก 1 ตัวมาเข้ากลุ่ม รวมเป็นวัว k+1 ตัว เราจะพิสูจน์ว่า วัวทั้ง k+1 ตัวนี้มีสีเดียวกันทั้งหมดด้วย

เนื่องจากเรารู้แล้วว่า วัวทั้ง k ตัวเดิมมีสีเดียวกันหมด เหลือเพียงวัวอีก 1 ตัวที่เพิ่มขึ้นมา ไม่แน่ว่าจะมีสีเดียวกันหรือไม่ ก็ให้เราเลือกวัว 1 ตัวออกจากกลุ่มวัว k ตัวที่มีสีเดียวกันหมด แล้วเอาวัวตัวใหม่ไปแทนที่ รวมเป็นวัวในกลุ่ม k ตัว กับวัวอีก 1 ตัวที่ถูกดึงออกจากกลุ่ม

โดยข้อสมมติที่ p(k) จริงหรือ "วัวทุกๆ k ตัวมีสีเดียวกัน" ดังนั้น วัวในกลุ่ม k ตัวนั้นจึงมีสีเดียวกันหมดด้วย แสดงว่าวัวตัวใหม่ของเราก็มีสีเดียวกับวัว k ตัวในตอนแรกด้วย ดังนั้น วัวทุกๆ k+1 ตัวมีสีเดียวกันจริง หรือ p(k+1) จริง

การพิสูจน์นี้มีปัญหาในส่วนของการ induction จาก p(k) ไปสู่ p(k+1) เพราะไม่ได้เป็นจริงสำหรับ จำนวนนับ k ใดๆ ทำไม

หากเราสังเกตให้ดีๆจะพบว่า ในการพิสูจน์นี้ต้องมีวัวอย่างน้อย 2 ตัวขึ้นไป (k >= 2) จึงจะทำได้ เพราะ

• ต้องมีวัวอย่างน้อย 1 ตัว เป็นวัวในกลุ่มที่ไม่ถูกดึงออกไป จะได้เป็นตัวเชื่อมโยงว่า สีของวัวกลุ่มเดิม กับวัวที่มาใหม่เป็นสีเดียวกัน
• มีวัว 1 ตัว สำหรับดึงออกจากกลุ่ม แล้วให้วัวตัวใหม่เข้ามาแทนที่

หรือจะ induction จาก p(k) ไปสู่ p(k+1) ได้ เมื่อ k >= 2 เท่านั้น ดังนั้นเงื่อนไขเริ่มต้นเพื่อให้ induction นี้สมบูรณ์ จึงต้องเริ่มจากพิสูจน์ให้ได้ว่า p(2) จริง มิใช่ p(1) จริง (เพราะเราไม่สามารถ induction จาก p(1) ==> p(2) ได้)

แต่มาคิดๆดูอีกที หากเราพิสูจน์ได้ว่า p(2) จริงหรือ "วัวทุกๆ 2 ตัวมีสีเดียวกัน" มันก็เห็นได้ชัดอยู่แล้วว่า "วัวทุกตัวมีสีเดียวกัน"

[PaoBunJin]

ผมก้อว่ามันแปลกๆตรงที่หยิบวัวออกมาเหมือนกันคับ เพราะเราอาจหยิบตัวเดิมออกไปก็ได้ แต่ถ้าบอกว่าเขียนหมายเลข 1 ถึง k+1 แล้วครั้งที่ 1 หยิบเลข 1 ไปเรื่อยๆ ถึง k+1 อย่างนี้คงเข้าใจได้ และถ้าเรายอมรับว่า p(1) จริงแล้วใช้วิธีนี้กับ p(2) ก็จะได้ว่า p(2) จริง เพราะ มีวัว 2 ตัว เอาออกไป 1 ตัว วัว 1 ตัวที่เหลือก้อมีสีเดียวกัน (ซึ่งจริงๆจะเห็นว่า p(2) เท็จแต่ถ้าพิสูจน์ด้วยวิธีนี้จะจริง ! ) แต่พอ p(3) เป็นต้นไปจะไม่จริง
ผมเห็นด้วยกับพี่กรนะครับ ว่ามันเหมือนกับการยอมรับว่า p(k+1) เป็นจริงไปก่อนแล้ว มันเลยดูเหมือนไม่ขัดแย้ง แต่ที่ คุณ kanji พิสูจน์คือ บอกว่า วัว k+1 ตัวหมายถึงวัวสีเดียวกัน k ตัวรวมกับวัว 1 ตัว เขียนเป็นสัญสักษณ์คือ p(k+1) = p(k)+1 ซึ่งจริงๆแล้วมันไม่เท่ากัน(คนละความหมาย)


* พี่กรคับเมื่อไรจะทำเสริมประสบการณ์เป็น E book อีกคับ แล้วหนังสือเขียนเกือบเสร็จยังคับ รออ่านอยู่นะคับ ^^ *

[gon]

อืม. เหตุผลข้างบนที่พี่ให้ไว้ ผิดถูกยังไง คงต้องพิจารณาดี ๆ อีกหลาย ๆ ครั้งครับ. พี่ก็แค่คิดเล่น ๆ ไปรอบเดียว ยังไม่ได้ทบทวนอีกครั้งเลย ก็เฉยไว้ก่อน เพราะเจ้าของกระทู้เขายังไม่กลับมาสงสัยเลย

สำหรับน้อง.PaoBunJin. E-Book เสริมประสบการณ์พี่ยังไม่เคยทำนะ มีแต่เนื้อหาบทที่ 17 (ตอนโน้น) เรื่อง ลำดับและอนุกรม บางส่วน ที่เขียนไว้ ตอนนี้ก็คงถูกลบออกไปจาก server ??? เรียบร้อยแล้ว มีใครอยากได้อีกไหม ? เอาไปอ่านเล่นแก้กลุ้มก่อน ถ้ามีสมาชิกสนใจลงชื่อไว้สัก 5 คน. เดี๋ยวผมจะทิ้งให้ Download อีกที สัก 3 วัน.

เออใช่. เคยทำ E-Book รวมเล่มเสริมประสบการณ์ ไว้ตอนปีใหม่ 2002 มั้ง เดี๋ยวปีใหม่นี้ทำอีกทีดีหรือเปล่า ถ้ามีสมาชิกลงชื่อสนใจถึง 20 คน จะทำให้แล้วกันนะครับ.

[alongkorn]

ผมคิดว่าน่าจะปรับโจทย์ใหม่ตรงที่สีเดียวกัน คือ สีอะไร ณ ที่นี้ให้เป็นสีน้ำตาล นั่นคือจงพิสูจน์ว่า วัว n ตัวมีสีน้ำตาล ทุก nฮN
การพิสูจน์ ให้ P(n) แทนข้อความ วัว n ตัวมีสีน้ำตาล
ขั้นแรกต้องใส่เบอร์ (label) ให้กับวัวทุกตัว ต้องพิสูจน์ให้ได้ว่า P(1) คือ วัวตัวที่ 1 มีสีน้ำตาล จริง ซึ่งไม่แน่ว่าจะจริงหรือไม่
ต่อมาสมมติว่า P(k) วัวตัวที่ k ตัวมีสีน้ำตาล ต้องพิสูจน์อีกว่าวัวตัวที่ k+1 มีสีน้ำตาล
จุดอ่อนของโจทย์ข้อนี้อีกประเด็นก็คือ การอุปนัยเชิงคณิตศาสตร์จะใช้สำหรับการพิสูจน์ที่ nฮN นั่นคือในโลกนี้มีวัวอนันต์ตัว แต่ในความเป็นจริงวัวมีจำนวนจำกัด ไม่จำเป็นต้องใช้อุปนัยครับ เช่น จงพิสูจน์ว่า x² - 16 ฃ 0 ทุก xฮ{1, 2, 3, 4} ไม่ต้องใช้อุปนัยครับ

[warut]

เพื่อความชัดเจนผมขอเขียนโจทย์ใหม่อีกครั้งนะครับ

ให้ P(n) แทนข้อความว่า
"ในกลุ่มของวัวจำนวน n ตัวใดๆ วัวทุกตัวในกลุ่มนั้นจะมีสีเดียวกันหมด"

เรารู้อยู่แก่ใจว่าข้อความที่ว่า "P(n) เป็นจริงสำหรับทุกจำนวนนับ n" นั้นเป็นเท็จ

แต่ข้างล่างนี้ผมจะแสดงการพิสูจน์โดยใช้การอุปนัยเชิงคณิตศาสตร์
เพื่อให้เห็นว่าข้อความ "P(n) เป็นจริงสำหรับทุกจำนวนนับ n" นั้นเป็นจริง
สิ่งที่โจทย์ถามก็คือให้หาที่ผิดของการพิสูจน์ต่อไปนี้นั่นเอง

แน่นอน P(1) เป็นจริง

ต่อไปผมจะแสดงว่าถ้า P(k) เป็นจริงแล้ว P(k+1) จะเป็นจริงด้วย (k เป็นจำนวนนับ)

ให้ W แทนวัวหนึ่งตัวและ W₁ W₂ W₃ ... W_k-1 W_k W_k+1 แทนกลุ่มของวัว k+1 ตัว

จะเห็นว่ากลุ่มของวัวที่อยู่ในวงเล็บ [ W₁ W₂ W₃ ... W_k-1 W_k ] W_k+1
จะมีสีเดียวกันหมดเพราะเป็นกลุ่มของวัวจำนวน k ตัว

ทำนองเดียวกันกลุ่มของวัวที่อยู่ในวงเล็บปีกกา W₁ { W₂ W₃ ... W_k-1 W_k W_k+1 }
ก็จะมีสีเดียวกันหมดเพราะเป็นกลุ่มของวัวจำนวน k ตัวเช่นกัน

แต่เนื่องจากกลุ่มของวัวขนาด k ตัวทั้งสองกลุ่มนั้นมีสมาชิกร่วมกันอยู่
ดังนั้นกลุ่มของวัวทั้งหมดซึ่งมีขนาด k+1 ตัวย่อมต้องมีสีเดียวกันด้วย!

ผมจะยังไม่เฉลยนะครับเผื่อคนที่เพิ่งจะเข้าใจโจทย์จะได้มีโอกาสคิดบ้าง

ตอนแรกผมนึกว่าจบแล้ว
มันผิดเพราะว่า P(2) ไม่จริงไงครับ
เพราะ เซต 2 เซตที่สร้างนั้นมันไม่มีสมาชิกร่วมกัน

[warut]

งงเหมือนกัน...ไม่เข้าใจว่าที่คุณงงเขียนว่า "ตอนแรกผมนึกว่าจบแล้ว" หมายความว่าอย่างไร
แต่คำตอบของคุณงงยังไม่ถูกต้องนะครับ จริงๆแล้วการพิสูจน์ผิดเพราะ P(1) ฎ P(2) ไม่เป็นจริง
ไม่ใช่เพราะ P(2) ไม่จริง การพิสูจน์ในโจทย์ไม่ได้พูดถึงค่าความจริงของ P(2) เลยครับ