418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 6 - ประวัติรุ่นแก้ไข

Cardcaptor: /* การหาค่า \max_{1 \leq t \leq T} B_t/t \, */

2009-09-18T15:06:51Z

การหาค่า \max_{1 \leq t \leq T} B_t/t \,

158.108.183.136: /* การพิสูจน์ Lemma 1 */

2009-09-18T14:34:39Z

การพิสูจน์ Lemma 1

158.108.183.136: /* ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด */

2009-09-18T14:33:30Z

ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด

158.108.183.136: /* ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด */

2009-09-18T14:32:15Z

ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด

Cardcaptor เมื่อ 13:00, 18 กันยายน 2552

2009-09-18T13:00:48Z

Cardcaptor เมื่อ 12:53, 18 กันยายน 2552

2009-09-18T12:53:20Z

Cardcaptor: /* ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด */

2009-09-18T12:47:24Z

ลำดับการส่งที่ทำให้ค่า \max_{1 \leq t \leq T} B_t/t \, มีค่าน้อยที่สุด

Cardcaptor เมื่อ 12:39, 18 กันยายน 2552

2009-09-18T12:39:23Z

Cardcaptor: หน้าที่ถูกสร้างด้วย '== การแปลงปัญหา == สมมติว่าเราได้ทำการเลือกลำดับกา…'

2009-09-18T11:25:13Z

หน้าที่ถูกสร้างด้วย '== การแปลงปัญหา == สมมติว่าเราได้ทำการเลือกลำดับกา…'

หน้าใหม่

== การแปลงปัญหา ==
สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม <math>B_t \,</math> เป็นจำนวนบิตที่เราส่งโดยใช้ network link ตั้งแต่เวลา <math>0 \,</math> ถึงเวลา <math>t \,</math>

ยกตัวอย่างเช่น ถ้าค่า <math>b_i \,</math> และ <math>t_i \,</math> เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า <math>B_1 = 2000 \,</math>, <math>B_2 = 5000 \,</math>, <math>B_3 = 8000 \,</math>, และ <math>B_4 = 10000 \,</math>

ให้ <math>T = \sum_{i=1}^n t_i \,</math> เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก <math>B_t \leq rt \,</math> สำหรับ <math>t \,</math> ทุกๆ ค่าที่ <math>1 \leq t \leq T \,</math> หรือกล่าวอีกอย่างหนึ่งคือ <math>B_t / t \leq r \,</math> สำหรับ <math>t \,</math> ทุกค่า

ดังนั้นเราสามารถแก้ปัญหาในโจทย์ได้อีกแบบหนึ่งดังต่อไปนี้: เราหาลำดับการส่งวิดีโอที่ทำให้ค่า <math>B_t/t \,</math> ที่มากที่สุด (กล่าวคือ <math>\max_{1 \leq t \leq T} B_t/t \,</math>) มีค่าน้อยที่สุดเท่าที่เป็นไปได้ ถ้าค่านี้มีค่ามากกว่า <math>r \,</math> แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย

== ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==
เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:06, 18 กันยายน 2552
แถว 95:		แถว 95:

	== การหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> ==		== การหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> ==
		+	เราทราบว่าการส่งวิดีโอโดยเรียงลำดับตาม <math>b_i/t_i \,</math> จะทำให้่ีค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ แต่ด้วยความรู้เพียงแค่นี้เราไม่สามารถตัดสินได้ว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่ เนื่องจากเราไม่ร้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> เราจึงจำเป็นต้องออกแบบอัลกอริทึมเพื่อหาค่าดังกล่าว
		+
		+	อย่างไรก็ดีค่า เราสามารถหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> เมื่อเราเรียงวิดีโอตาม <math>b_i/t_i \,</math> ได้ง่ายมาก เราจะพิสูจน์ว่าค่านั้นคือ <math>B_T / T \,</math> ซึ่งมีค่าเท่ากับจำนวนบิตที่ส่งทั้งหมดหารด้วยเวลาส่งทั้งหมด
		+
		+	'''lemma 3''': ถ้าเราเรียงวิดีโอให้ <math>\frac{b_1}{t_1} \leq \frac{b_2}{t_2} \leq \dotsb \leq \frac{b_n}{t_n} \,</math> แล้ว สำหรับค่า <math>t \,</math> ทุกค่าที่ <math>1 \leq t \leq T \,</math> เราจะได้ว่า <math>\frac{B_1}{1} \leq \frac{B_2}{2} \leq \frac{B_3}{3} \leq \dotsb \leq \frac{B_t}{t} \,</math> นอกจากนี้ ถ้าในช่วงเวลาตั้งแต่ <math>t-1 \,</math> ถึงเวลา <math>t \,</math> เราทำการส่งวิีดีโด <math>i \,</math> แล้วเราจะได้ว่า <math>\frac{B_t}{t} \leq \frac{b_i}{t_i} \,</math>
		+
		+	'''พิสูจน์:''' เราจะทำการพิสูจน์โดยใช้ induction บนตัวแปร <math>t \,</math>
		+
		+	(Base Case) ในกรณีนี้ <math>t = 1 \,</math> เราได้ว่าในวินาทีแรกเราจะส่งข้อมูล <math>b_1/t_1 \,</math> บิตในเวลา 1 วินาที ดังนั้น <math>\frac{B_1}{1} \leq \frac{b_1}{t_1} \,</math> ตามต้องการ
		+
		+	(Induction Case) สมมติให้ lemma เป็นจริงสำหรับ <math>t \geq 1 \,</math> บางค่า พิจารณาเหตุการณ์ที่เกิดขึ้น ณ ช่วงเลาตั้งแต่ <math>t \,</math> ถึง <math>t+1 \,</math> และสมมติว่าในช่วงเวลานี้เราทำการส่งวิดีโอ <math>i \,</math> ผ่าน network link กล่าวคือในวินาทีนั้นเราส่งข้อมูลจำนวน <math>\frac{b_i}{t_i} \,</math> บิต ในกรณีนี้มีความเป็นไปได้อยู่สองกรณี
		+
		+	กรณีแรกคือ เราเริ่มส่งวิดีโอ <math>i \,</math> ตั้งแต่ก่อนเวลา <math>t \,</math> อยู่แล้ว ในกรณีนี้สมมติฐานของ induction บอกเราว่า <math>\frac{B_t}{t} \leq \frac{b_i}{t_i} = \frac{b_i/t_i}{1} \,</math> ฉะนั้นจาำก lemma 2 เราได้ว่า <math>\frac{B_t}{t} \leq \frac{B_t + b_i/t_i}{t+1} \leq \frac{b_i/t_i}{1} = \frac{b_i}{t_i} \,</math> เนื่องจาก <math>\frac{B_{t+1}}{t+1} = \frac{B_t + b_i/t_i}{t+1} \,</math> เราจึงได้ว่า <math>\frac{B_t}{t} \leq \frac{B_{t+1}}{t+1} \,</math> ด้วย
		+
		+	กรณีที่สองคือ เราเริ่มส่งวิดีโอ <math>i \,</math> ณ เวลา <math>t \,</math> พอดี กล่าวคือในช่วงเวลาตั้งแต่ <math>t-1 \,</math> ถึง <math>t \,</math> เราำกำลังส่งวิดีโอ <math>i-1 \,</math> อยู่ ในกรณีนี้สมมติฐานของ indunction บอกเราว่า <math>\frac{B_t}{t} \leq \frac{b_{i-1}}{t_{i-1}} \leq \frac{b_i}{t_i} \,</math> และเราสามารถใช้เหตุผลในกรณีที่แล้วพิสูจน์ว่า lemma เป็นจริงสำหรับ <math>t+1 \,</math> ด้วยเช่นกัน
		+
		+
		+	จาก lemma 3 เราได้ว่า <math>\max_{1 \leq t \leq T} B_t/t = B_T/T \,</math>
		+
		+	ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม <math>B_T = \sum_{i=1}^n b_i \,</math> และ <math>T = \sum_{i=1}^n t_i \,</math> แล้วตรวจสอบว่า <math>B_T/T \,</math> มากกว่า <math>r \,</math> หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา <math>O(n) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:34, 18 กันยายน 2552
แถว 93:		แถว 93:

	การพิสูจน์ว่า <math>\frac{a+c}{b+d} > \frac{c}{d} \,</math> ก็สามารถทำได้โดยการใช้เหตุผลแบบเดียวกันกับย่อหน้าที่แล้ว เราจึงละให้นิสิตทำเป็นแบบฝึกหัดไว้อีกโอกาสหนึ่ง (จบการพิสูจน์ lemma 2)		การพิสูจน์ว่า <math>\frac{a+c}{b+d} > \frac{c}{d} \,</math> ก็สามารถทำได้โดยการใช้เหตุผลแบบเดียวกันกับย่อหน้าที่แล้ว เราจึงละให้นิสิตทำเป็นแบบฝึกหัดไว้อีกโอกาสหนึ่ง (จบการพิสูจน์ lemma 2)
		+
		+	== การหาค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> ==

@@ แถว 28: / แถว 28: @@
 \,</math>
-'''lemma:''' สำหรับจำนวนเต็ม <math>t \,</math> ทุกตัวที่ <math>s \leq t \leq s+t_i+t_j \,</math> เราได้ว่า  <math>B_t \geq B'_t \,</math>
+: '''lemma 1:''' สำหรับจำนวนเต็ม <math>t \,</math> ทุกตัวที่ <math>s \leq t \leq s+t_i+t_j \,</math> เราได้ว่า  <math>B_t \geq B'_t \,</math>
 '''พิสูจน์:''' สำหรับจำนวนเต็ม <math>t \,</math> ที่ <math>s \leq t \leq s+t_i+t_j \,</math>นิยามค่า <math>B''_t = B_s + (t - s)\frac{b_i + b_j}{t_i + t_j} \,</math>
@@ แถว 38: / แถว 42: @@
 หากสามารถทำเช่นนี้ได้ เราก็จะสามารถสรุปได้ว่า <math>B_t \geq B'_t \,</math> สำหรับ <math>t \,</math> ทุกค่า
-(ข้อความที่ 1) พิจารณาค่า <math>B_t - B''_t \,</math> เราจะได้ว่า ถ้า <math>s \leq t \leq s+t_i \,</math> แล้ว
+การพิสูจน์ข้อวามทั้งสองข้อข้างบนนี้จะใช้ความจริงที่ว่า <math>\frac{b_i}{t_i} > \frac{b_i+b_j}{t_i + t_j} > \frac{b_j}{t_j} \,</math> หลายครั้ง เราจะพิสูจน์ข้อความนี้เป็น lemma 2 หลังจากพิสูจน์ lemma 1
-: <math>B_t - B''_t = (t-s)\frac{b_i}{t_i} - (t-s)\frac{b_i + b_j}{t_i + t_j} = (t-s)\bigg( \frac{b_i}{t_i} - \frac{b_i + b_j}{t_i + t_j} \bigg) = (t-s)\bigg( \frac{b_it_i + b_it_j - b_it_i - b_i t_j}{t_i (t_i+t_j)} \bigg) \,</math>
-เนื่องจาก <math>b_i/t_i > b_j/t_j \,</math> หรือ <math>b_i \,</math> เราจะได้ว่า
+'''(ข้อความที่ 1)''' เราจะได้ว่า ถ้า <math>s \leq t < s+t_i \,</math> แล้ว

@@ แถว 2: / แถว 2: @@
 เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้
-เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า <math>b_i / t_i \,</math> จากน้อยไปมาก โดยไม่ทำให้ค่า <math>\max_{1\leq t \leq T} B_t/t \,</math> มีค่ามากกขึ้น
+เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า <math>b_i / t_i \,</math> จากน้อยไปมาก โดยไม่ทำให้ค่า <math>\max_{1\leq t \leq T} B_t/t \,</math> มีค่ามากขึ้น
 สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ <math>b_i/t_i \,</math> แสดงว่าจะต้องมีวิดีโอ <math>i \,</math> และ <math>j \,</math> ที่ <math>i \,</math> ถูกส่งก่อน <math>j \,</math> แต่ <math>b_i/t_i > b_j/t_j \,</math> นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ <math>j \,</math> เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ <math>i \,</math> ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ
@@ แถว 39: / แถว 39: @@
 (ข้อความที่ 1) พิจารณาค่า <math>B_t - B''_t \,</math> เราจะได้ว่า ถ้า <math>s \leq t \leq s+t_i \,</math> แล้ว
-: <math>B_t - B''_t = (t-s)\frac{b_i}{t_i} - (t-s)\frac{b_i + b_j}{t_i + t_j} = (t-s)\bigg( frac{b_i}{t_i} - \frac{b_i + b_j}{t_i + t_j} \bigg) \,</math>
+: <math>B_t - B''_t = (t-s)\frac{b_i}{t_i} - (t-s)\frac{b_i + b_j}{t_i + t_j} = (t-s)\bigg( \frac{b_i}{t_i} - \frac{b_i + b_j}{t_i + t_j} \bigg) = (t-s)\bigg( \frac{b_it_i + b_it_j - b_it_i - b_i t_j}{t_i (t_i+t_j)} \bigg) \,</math>
 เนื่องจาก <math>b_i/t_i > b_j/t_j \,</math> หรือ <math>b_i \,</math> เราจะได้ว่า

@@ แถว 1: / แถว 1: @@
 == ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==
 เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้
@@ แถว 47: / แถว 38: @@
 หากสามารถทำเช่นนี้ได้ เราก็จะสามารถสรุปได้ว่า <math>B_t \geq B'_t \,</math> สำหรับ <math>t \,</math> ทุกค่า
-(ข้อความที่ 1)
+(ข้อความที่ 1) พิจารณาค่า <math>B_t - B''_t \,</math> เราจะได้ว่า ถ้า <math>s \leq t \leq s+t_i \,</math> แล้ว

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:33, 18 กันยายน 2552
แถว 1:		แถว 1:
		+	== การแปลงปัญหา ==
		+	สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม <math>B_t \,</math> เป็นจำนวนบิตที่เราส่งโดยใช้ network link ตั้งแต่เวลา <math>0 \,</math> ถึงเวลา <math>t \,</math>
		+
		+	ยกตัวอย่างเช่น ถ้าค่า <math>b_i \,</math> และ <math>t_i \,</math> เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า <math>B_1 = 2000 \,</math>, <math>B_2 = 5000 \,</math>, <math>B_3 = 8000 \,</math>, และ <math>B_4 = 10000 \,</math>
		+
		+	ให้ <math>T = \sum_{i=1}^n t_i \,</math> เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก <math>B_t \leq rt \,</math> สำหรับ <math>t \,</math> ทุกๆ ค่าที่ <math>1 \leq t \leq T \,</math> หรือกล่าวอีกอย่างหนึ่งคือ <math>B_t / t \leq r \,</math> สำหรับ <math>t \,</math> ทุกค่า
		+
		+	ดังนั้นเราสามารถแก้ปัญหาในโจทย์ได้อีกแบบหนึ่งดังต่อไปนี้: เราหาลำดับการส่งวิดีโอที่ทำให้ค่า <math>B_t/t \,</math> ที่มากที่สุด (กล่าวคือ <math>\max_{1 \leq t \leq T} B_t/t \,</math>) มีค่าน้อยที่สุดเท่าที่เป็นไปได้ ถ้าค่านี้มีค่ามากกว่า <math>r \,</math> แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย
		+
	== ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==		== ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==
	เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้		เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

@@ แถว 22: / แถว 22: @@
      B_t =
      \begin{cases}
-         B_s + k \frac{b_i}{t_i}, & t = s+k < s+t_i \\
+         B_s + (t-s) \frac{b_i}{t_i}, & s \leq t = < s+t_i \\
-         B_s + b_i + k \frac{b_j}{t_j} & t = s+t_i+k \leq s+t_i+t_j
+         B_s + b_i + (t-s-t_i) \frac{b_j}{t_j} & s+t_i \leq t \leq s+t_i+t_j
      \end{cases}
 \,</math>
@@ แถว 32: / แถว 32: @@
      B'_t =
      \begin{cases}
-         B_s + k \frac{b_j}{t_j}, & t = s+k < s+t_j \\
+         B_s + (t-s) \frac{b_j}{t_j}, & s \leq t < s+t_j \\
-         B_s + b_j + k \frac{b_i}{t_i} & t = s+t_j+k \leq s+t_i+t_j
+         B_s + b_j + (t-s-t_j) \frac{b_i}{t_i} & s+t_j \leq t \leq s+t_i+t_j
      \end{cases}
 \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:39, 18 กันยายน 2552
แถว 10:		แถว 10:
	== ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==		== ลำดับการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุด ==
	เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้		เราจะพิสูจน์ว่าลำดับการส่งที่'''ทำการส่งวิดีโอที่มีค่า <math>b_i / t_i \,</math> น้อยกว่าก่อน''' (กล่าวคือนำวิดีโอมาเรียงตามค่า <math>b_i/t_i \,</math> จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้
		+
		+	เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า <math>b_i / t_i \,</math> จากน้อยไปมาก โดยไม่ทำให้ค่า <math>\max_{1\leq t \leq T} B_t/t \,</math> มีค่ามากกขึ้น
		+
		+	สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ <math>b_i/t_i \,</math> แสดงว่าจะต้องมีวิดีโอ <math>i \,</math> และ <math>j \,</math> ที่ <math>i \,</math> ถูกส่งก่อน <math>j \,</math> แต่ <math>b_i/t_i > b_j/t_j \,</math> นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ <math>j \,</math> เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ <math>i \,</math> ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ
		+
		+	เราจะแสดงว่าเมื่อเราสลับเอาวิดีโอ <math>j \,</math> ไปส่งก่อนวิดีโอ <math>i \,</math> แล้ว ค่า <math>\max_{1 \leq t \leq T} B_t/t \,</math> จะไม่เพิ่มขึ้นแต่อย่างใด
		+
		+	สมมติว่าเราเริ่มส่งวิดีโอ <math>i \,</math> ณ เวลา <math>s \,</math> เราจะได้ว่าเราจะส่งมันเสร็จที่เวลา <math>s + t_i \,</math> ซึ่งเราจะเริ่มส่งวิดีโอ <math>j \,</math> และเราจะส่งวิดีโอ <math>j \,</math> ที่เวลา <math>s + t_i + t_j \,</math> ดังนั้นในช่วงเวลาตั้งแต่ <math>t = s \,</math> ถึง <math>t = s+t_i \,</math> ค่า <math>B_t \,</math> จะมีค่าเพิ่มขึ้นวินาทีละ <math>b_i/t_i \,</math> และในช่วงเวลาตั้งแต่ <math>t = s+t_i \,</math> จนถึง <math>t = s+t_i+t_j \,</math> ค่า <math>B_t \,</math> จะมีค่าเพิ่มขึ้นวินาทีละ <math>b_j/t_j \,</math> ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้
		+
		+	: <math>
		+	B_t =
		+	\begin{cases}
		+	B_s + k \frac{b_i}{t_i}, & t = s+k < s+t_i \\
		+	B_s + b_i + k \frac{b_j}{t_j} & t = s+t_i+k \leq s+t_i+t_j
		+	\end{cases}
		+	\,</math>
		+
		+	หลังจากสลับแล้วเราจะเริ่มส่งวิดีโอ <math>j \,</math> ณ เวลา <math>t = s \,</math> และจะส่งเสร็จที่เวลา <math>t = s+t_j \,</math> ซึ่งในเวลาเดียวกันเราจะเริ่มส่งวิดีโอ <math>i \,</math> และจะส่งมันเสร็จที่เวลา <math>t = s+t_j+t_i = s+t_i+t_j \,</math> ให้ <math>B'_t \,</math> แทนจำนวนบิตที่ส่งผ่าน network link ตั้งแต่เวลา 0 ถึง <math>t \,</math> หลังจากการสลับ เราจะได้ว่าตั้งแต่เวลา <math>t = s \,</math> ถึง <math>t = t_j \,</math> ค่า <math>B'_t \,</math> จะมีค่าเพิ่มขึ้นวินาทีละ <math>b_j/t_j \,</math> ส่วนในเวลาตั้งแต่ <math>t = s+t_j \,</math> ถึง <math>t = s+t_i+t_j \,</math> ค่า <math>B'_t \,</math> จะเพิ่มขึ้นวินาทีละ <math>b_i/t_i \,</math> ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้
		+
		+	: <math>
		+	B'_t =
		+	\begin{cases}
		+	B_s + k \frac{b_j}{t_j}, & t = s+k < s+t_j \\
		+	B_s + b_j + k \frac{b_i}{t_i} & t = s+t_j+k \leq s+t_i+t_j
		+	\end{cases}
		+	\,</math>