418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 6

ข้อย่อย 1

ก่อนอื่นเราจะนิยามฟังก์ชัน min และ max สำหรับค่าสองค่าก่อน ดังนี้

$\mathrm {min2} (a,b)={\begin{cases}a,&a\leq b\\b,&a>b\end{cases}}$

และ

$\mathrm {max2} (a,b)={\begin{cases}a,&a>b\\b,&a\leq b\end{cases}}$

จากนั้นเราจึงนิยามฟังก์ชัน min และ max สำหรับค่า n ค่าใดๆ ดังต่อไปนี้

$\min(a_{1},a_{2},\ldots ,a_{n})={\begin{cases}a_{1},&n=1\\\mathrm {min2} (\min(a_{1},a_{2},\ldots ,a_{n-1}),a_{n}),&n>1\end{cases}}$

และ

$\max(a_{1},a_{2},\ldots ,a_{n})={\begin{cases}a_{1},&n=1\\\mathrm {max2} (\max(a_{1},a_{2},\ldots ,a_{n-1}),a_{n}),&n>1\end{cases}}$

ข้อย่อย 2

ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน

lemma 1: ให้ $a\,$ และ $b\,$ เป็นจำนวนจริงใดๆ แล้ว $\mathrm {max2} (-a,-b)=-\mathrm {min2} (a,b)\,$

พิสูจน์ (lemma 1): การพิสูจน์แบ่งออกเป็นสองกรณี

1. $a>b\,$ เราได้ว่า $-a<-b\,$ ดังนั้น $\mathrm {max2} (-a,-b)=-b=-\mathrm {min2} (a,b)\,$
2. $a\leq b\,$ เราได้ว่า $-a\geq -b\,$ ดังนั้น $\mathrm {max2} (-a,-b)=-a=-\mathrm {min2} (a,b)\,$

พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร $n\,$

(Base Case) $n=1\,$ เราจะได้ว่า $\max(-a_{1})=-a_{1}=-\min(a_{1})\,$

(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้ $\max(-a_{1},-a_{2},\ldots ,-a_{n})=-\min(a_{1},a_{2},\ldots ,a_{n})$

ให้ $a_{1},a_{2},\ldots ,a_{n+1}$ เป็นจำนวนจริงใดๆ เราได้ว่า

$\max(-a_{1},a_{2},\ldots ,-a_{n+1})\,$	$=\,$	$\mathrm {max2} (\max(-a_{1},-a_{2},\ldots ,-a_{n}),-a_{n+1})\,$
	$=\,$	$\mathrm {max2} (-\min(a_{1},a_{2},\ldots ,a_{n}),-a_{n+1})\,$
	$=\,$	$-\mathrm {min2} (\min(a_{1},a_{2},\ldots ,a_{n}),a_{n+1})\,$	(ใช้ lemma 1)
	$=\,$	$-\min(a_{1},a_{2},\ldots ,a_{n+1})\,$

ดังนั้นเราสามารถสรุปได้ว่า $\max(-a_{1},-a_{2},\ldots ,-a_{n})=-\min(a_{1},a_{2},\ldots ,a_{n})$ สำหรับจำนวนจริง $a_{1},a_{2},\ldots ,a_{n}$ ใดๆ

ข้อย่อย 3

ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน

lemma 2: ให้ $a_{1},a_{2}\,$ และ $b_{1},b_{2}\,$ เป็นจำนวนจริงใดๆ แล้ว $\mathrm {max2} (a_{1}+b_{1},a_{2}+b_{2})\leq \mathrm {max2} (a_{1},a_{2})+\mathrm {max2} (b_{1},b_{2})\,$

พิสูจน์ (lemma 2): ให้ $A=\mathrm {max2} (a_{1},a_{2})\,$ และให้ เราได้ว่า $a_{1}\leq A,a_{2}\leq A,b_{1}\leq B,$ และ $b_{2}\leq B\,$ ฉะนั้น $a_{1}+b_{1}\leq A+B\,$ และ $a_{2}+b_{2}\leq A+B\,$

เนื่องจาก $\mathrm {max2} (a_{1}+b_{1},a_{2}+b_{2})\,$ มีค่าเท่ากับ $a_{1}+b_{1}\,$ หรือไม่ก็ $a_{2}+b_{2}\,$ เราจึงได้ว่า $\mathrm {max2} (a_{1}+b_{1},a_{2}+b_{2})\leq A+B=\mathrm {max2} (a_{1},a_{2})+\mathrm {max2} (b_{1},b_{2})\,$

พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร $n\,$

(Base Case) $n=1\,$ เราจะได้ว่า $\max(a_{1}+b_{1})\leq a_{1}+b_{1}=\max(a_{1})+\max(b_{1})\,$

(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้ $\max(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n})\leq \max(a_{1},a_{2},\ldots ,a_{n})+\max(b_{1},b_{2},\ldots ,b_{n})\,$

ให้ $a_{1},a_{2},\ldots ,a_{n+1},b_{1},b_{2},\ldots ,b_{n+1}$ เป็นจำนวนจริงใดๆ เราได้ว่า

$\max(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n+1}+b_{n+1})\,$	$=\,$	$\mathrm {max2} (\max(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n}),a_{n+1}+b_{n+1})\,$
	$\leq \,$	$\mathrm {max2} (\max(a_{1},a_{2},\ldots ,a_{n})+\max(b_{1},b_{2},\ldots ,b_{n}),a_{n+1}+b_{n+1})\,$	(สมมติฐาน)
	$\leq \,$	$\mathrm {max2} (\max(a_{1},a_{2},\ldots ,a_{n}),a_{n+1})+\mathrm {max2} (\max(b_{1},b_{2},\ldots ,b_{n}),b_{n+1})\,$	(ใช้ lemma 2)
	$=\,$	$\max(a_{1},a_{2},\ldots ,a_{n+1})+\max(b_{1},b_{2},\ldots ,b_{n+1})\,$

ดังนั้นเราสามารถสรุปได้ว่า $\max(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n})\leq \max(a_{1},a_{2},\ldots ,a_{n})+\max(b_{1},b_{2},\ldots ,b_{n})$ สำหรับจำนวนจริง $a_{1},a_{2},\ldots ,a_{n}$ ใดๆ

ข้อย่อย 4

ก่อนเราจะพิสูจน์ข้อความในโจทยฺ์ เราจะพิสูจน์ lemma ต่อไปนี้ก่อน

lemma 3: ให้ $a_{1},a_{2}\,$ และ $b_{1},b_{2}\,$ เป็นจำนวนจริงใดๆ แล้ว $\mathrm {min2} (a_{1}+b_{1},a_{2}+b_{2})\geq \mathrm {min2} (a_{1},a_{2})+\mathrm {min2} (b_{1},b_{2})\,$

พิสูจน์ (lemma 3): ให้ $\alpha =\mathrm {min2} (a_{1},a_{2})\,$ และให้ เราได้ว่า $a_{1}\geq \alpha ,a_{2}\geq \alpha ,b_{1}\geq \beta ,$ และ $b_{2}\geq \beta \,$ ฉะนั้น $a_{1}+b_{1}\geq \alpha +\beta \,$ และ $a_{2}+b_{2}\geq \alpha +\beta \,$

เนื่องจาก $\mathrm {min2} (a_{1}+b_{1},a_{2}+b_{2})\,$ มีค่าเท่ากับ $a_{1}+b_{1}\,$ หรือไม่ก็ $a_{2}+b_{2}\,$ เราจึงได้ว่า $\mathrm {min2} (a_{1}+b_{1},a_{2}+b_{2})\geq \alpha +\beta =\mathrm {min2} (a_{1},a_{2})+\mathrm {min2} (b_{1},b_{2})\,$

พิสูจน์ (โจทย์): เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร $n\,$

(Base Case) $n=1\,$ เราจะได้ว่า $\min(a_{1}+b_{1})\leq a_{1}+b_{1}=\min(a_{1})+\min(b_{1})\,$

(Induction Case) ให้ n เป็นจำนวนเต็มบวกและสมมติให้ $\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})\,$

ให้ $a_{1},a_{2},\ldots ,a_{n+1},b_{1},b_{2},\ldots ,b_{n+1}$ เป็นจำนวนจริงใดๆ เราได้ว่า

$\min(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n+1}+b_{n+1})\,$	$=\,$	$\mathrm {min2} (\min(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n}),a_{n+1}+b_{n+1})\,$
	$\geq \,$	$\mathrm {min2} (\min(a_{1},a_{2},\ldots ,a_{n})+\min(b_{1},b_{2},\ldots ,b_{n}),a_{n+1}+b_{n+1})\,$	(สมมติฐาน)
	$\geq \,$	$\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})\,$	(ใช้ lemma 3)
	$=\,$	$\min(a_{1},a_{2},\ldots ,a_{n+1})+\min(b_{1},b_{2},\ldots ,b_{n+1})\,$

ดังนั้นเราสามารถสรุปได้ว่า $\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})$ สำหรับจำนวนจริง $a_{1},a_{2},\ldots ,a_{n}$ ใดๆ