ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 6"
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 115: | แถว 115: | ||
''พิสูจน์ (โจทย์):'' เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร <math>n \,</math> | ''พิสูจน์ (โจทย์):'' เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร <math>n \,</math> | ||
| − | (Base Case) <math>n = 1 \,</math> เราจะได้ว่า <math>\ | + | (Base Case) <math>n = 1 \,</math> เราจะได้ว่า <math>\min(a_1 + b_1) \leq a_1 + b_1 = \min(a_1) + \min(b_1) \,</math> |
| − | (Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้ <math>\ | + | (Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้ <math>\min(a_1 + b_1, a_2 + b_2, \ldots, a_n+b_n) \leq \min(a_1, a_2, \ldots, a_n) + \min(b_1, b_2, \ldots, b_n) \,</math> |
ให้ <math>a_1, a_2, \ldots, a_{n+1}, b_1, b_2, \ldots, b_{n+1}</math> เป็นจำนวนจริงใดๆ เราได้ว่า | ให้ <math>a_1, a_2, \ldots, a_{n+1}, b_1, b_2, \ldots, b_{n+1}</math> เป็นจำนวนจริงใดๆ เราได้ว่า | ||
| แถว 123: | แถว 123: | ||
<table cellpadding="5"> | <table cellpadding="5"> | ||
<tr> | <tr> | ||
| − | <td align="right"><math>\ | + | <td align="right"><math>\min(a_1 + b_1, a_2 + b_2, \ldots, a_{n+1}+b_{n+1}) \,</math></td> |
<td align="center"><math>= \,</math></td> | <td align="center"><math>= \,</math></td> | ||
| − | <td align="left"><math>\mathrm{ | + | <td align="left"><math>\mathrm{min2}(\min(a_1 + b_1, a_2 + b_2, \ldots, a_n+b_n), a_{n+1}+b_{n+1}) \,</math></td> |
<td align="left"></td> | <td align="left"></td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td align="right"></td> | <td align="right"></td> | ||
| − | <td align="center"><math>\ | + | <td align="center"><math>\geq \,</math></td> |
| − | <td align="left"><math>\mathrm{ | + | <td align="left"><math>\mathrm{min2}(\min(a_1, a_2, \ldots, a_n) + \min(b_1, b_2, \ldots, b_n), a_{n+1} + b_{n+1}) \,</math></td> |
<td align="left">(สมมติฐาน)</td> | <td align="left">(สมมติฐาน)</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td align="right"></td> | <td align="right"></td> | ||
| − | <td align="center"><math>\ | + | <td align="center"><math>\geq \,</math></td> |
| − | <td align="left"><math>\mathrm{ | + | <td align="left"><math>\mathrm{min2}(\min(a_1, a_2, \ldots, a_n), a_{n+1}) + \mathrm{min2}(\min(b_1, b_2, \ldots, b_n), b_{n+1}) \,</math></td> |
| − | <td align="left"> (ใช้ lemma | + | <td align="left"> (ใช้ lemma 3)</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td align="right"></td> | <td align="right"></td> | ||
<td align="center"><math>= \,</math></td> | <td align="center"><math>= \,</math></td> | ||
| − | <td align="left"><math>\ | + | <td align="left"><math>\min(a_1, a_2, \ldots, a_{n+1}) + \min(b_1, b_2, \ldots, b_{n+1})\,</math></td> |
<td align="left"></td> | <td align="left"></td> | ||
</tr> | </tr> | ||
</table> | </table> | ||
| − | ดังนั้นเราสามารถสรุปได้ว่า <math>\ | + | ดังนั้นเราสามารถสรุปได้ว่า <math>\min(a_1 + b_1, a_2 + b_2, \ldots, a_n+b_n) \leq \min(a_1, a_2, \ldots, a_n) + \min(b_1, b_2, \ldots, b_n) </math> สำหรับจำนวนจริง <math>a_1, a_2, \ldots, a_n</math> ใดๆ |
รุ่นแก้ไขปัจจุบันเมื่อ 12:04, 11 กรกฎาคม 2552
เนื้อหา
ข้อย่อย 1
ก่อนอื่นเราจะนิยามฟังก์ชัน min และ max สำหรับค่าสองค่าก่อน ดังนี้
และ
จากนั้นเราจึงนิยามฟังก์ชัน min และ max สำหรับค่า n ค่าใดๆ ดังต่อไปนี้
และ
ข้อย่อย 2
ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน
lemma 1: ให้ และ เป็นจำนวนจริงใดๆ แล้ว
พิสูจน์ (lemma 1): การพิสูจน์แบ่งออกเป็นสองกรณี
- เราได้ว่า ดังนั้น
- เราได้ว่า ดังนั้น
พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร
(Base Case) เราจะได้ว่า
(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้
ให้ เป็นจำนวนจริงใดๆ เราได้ว่า
| (ใช้ lemma 1) | |||
ดังนั้นเราสามารถสรุปได้ว่า สำหรับจำนวนจริง ใดๆ
ข้อย่อย 3
ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน
lemma 2: ให้ และ เป็นจำนวนจริงใดๆ แล้ว
พิสูจน์ (lemma 2): ให้ และให้ เราได้ว่า และ ฉะนั้น และ
เนื่องจาก มีค่าเท่ากับ หรือไม่ก็ เราจึงได้ว่า
พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร
(Base Case) เราจะได้ว่า
(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้
ให้ เป็นจำนวนจริงใดๆ เราได้ว่า
| (สมมติฐาน) | |||
| (ใช้ lemma 2) | |||
ดังนั้นเราสามารถสรุปได้ว่า สำหรับจำนวนจริง ใดๆ
ข้อย่อย 4
ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน
lemma 3: ให้ และ เป็นจำนวนจริงใดๆ แล้ว
พิสูจน์ (lemma 3): ให้ และให้ เราได้ว่า และ ฉะนั้น และ
เนื่องจาก มีค่าเท่ากับ หรือไม่ก็ เราจึงได้ว่า
พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร
(Base Case) เราจะได้ว่า
(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้
ให้ เป็นจำนวนจริงใดๆ เราได้ว่า
| (สมมติฐาน) | |||
| (ใช้ lemma 3) | |||
ดังนั้นเราสามารถสรุปได้ว่า สำหรับจำนวนจริง ใดๆ