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

การแปลงปัญหา

สมมติว่าเราได้ทำการเลือกลำดับการส่งวิดีโอแล้ว นิยาม

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 471241525
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:38 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}\,$ เป็นจำนวนบิตที่เราส่งโดยใช้ network link ตั้งแต่เวลา $0\,$ ถึงเวลา $t\,$

ยกตัวอย่างเช่น ถ้าค่า $b_{i}\,$ และ $t_{i}\,$ เป็นไปตามที่กำหนดในโจทย์ และเราตัดสินใจส่งวิดิโอที่ 1, 2, และ 3 ตามลำดับแล้ว เราจะได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 540906320
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:39 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{1}=2000\,$,

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 569610346
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:39 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{2}=5000\,$, $B_{3}=8000\,$, และ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 630099186
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:40 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{4}=10000\,$

ให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 584259190
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:40 GMT


Sensitive client information

IP address: 158.108.32.49

$T=\sum _{i=1}^{n}t_{i}\,$ เราได้ว่าเราสามารถส่งวิดีโอต่างๆ ผ่าน network link โดยสอดคล้องกับกฎ (*) ถ้าหาก

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 554996121
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:41 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}\leq rt\,$ สำหรับ $t\,$ ทุกๆ ค่าที่ $1\leq t\leq T\,$ หรือกล่าวอีกอย่างหนึ่งคือ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 467014316
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:42 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}/t\leq r\,$ สำหรับ $t\,$ ทุกค่า

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 554996140
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:43 GMT


Sensitive client information

IP address: 158.108.32.49

$r\,$ แสดงว่าเราไม่สามารถส่งวิดีโอตามกฎ (*) ได้เลย

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

เราจะพิสูจน์ว่าลำดับการส่งที่ทำการส่งวิดีโอที่มีค่า $b_{i}/t_{i}\,$ น้อยกว่าก่อน (กล่าวคือนำวิดีโอมาเรียงตามค่า $b_{i}/t_{i}\,$ จากน้อยไปหามากแล้วส่งตามลำดับนั้น) จะทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

เราจะทำการพิสูจน์นี้ด้วย exchange argument ซึ่งเราจะแสดงว่าเราสามารถแปลงวิธีการส่งที่ทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ (ตั้งแต่บัดนี้เราจะเรียกมันว่า "วิธีการส่งที่ดีที่สุด") ไปเป็นการส่งที่ส่งตามลำดับค่า $b_{i}/t_{i}\,$ จากน้อยไปมาก โดยไม่ทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่ามากขึ้น

สมมติว่าวิธีการส่งที่ดีที่สุดไม่เหมือนกับวิธีการส่งตามลำดับ $b_{i}/t_{i}\,$ แสดงว่าจะต้องมีวิดีโอ $i\,$ และ $j\,$ ที่ $i\,$ ถูกส่งก่อน $j\,$ แต่ $b_{i}/t_{i}>b_{j}/t_{j}\,$ นอกจากนี้เรายังสามารถสมมติเพิ่มเติมได้อีกว่าวิดีโอ $j\,$ เป็นวิดีโอที่ถูกส่งถัดจากวิดีโอ $i\,$ ด้วย เนื่องจากเรารู้ว่าถ้ามี inversion แล้วจะต้องมี inversion ที่ติดกันเสมอ

เราจะแสดงว่าเมื่อเราสลับเอาวิดีโอ $j\,$ ไปส่งก่อนวิดีโอ $i\,$ แล้ว ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ จะไม่เพิ่มขึ้นแต่อย่างใด

สมมติว่าเราเริ่มส่งวิดีโอ $i\,$ ณ เวลา $s\,$ เราจะได้ว่าเราจะส่งมันเสร็จที่เวลา $s+t_{i}\,$ ซึ่งเราจะเริ่มส่งวิดีโอ $j\,$ และเราจะส่งวิดีโอ $j\,$ ที่เวลา $s+t_{i}+t_{j}\,$ ดังนั้นในช่วงเวลาตั้งแต่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 548408967
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:51 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s\,$ ถึง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 449092366
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:51 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s+t_{i}\,$ ค่า $B_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ $b_{i}/t_{i}\,$ และในช่วงเวลาตั้งแต่ $t=s+t_{i}\,$ จนถึง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 455708345
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:52 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s+t_{i}+t_{j}\,$ ค่า $B_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 626039225
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:53 GMT


Sensitive client information

IP address: 158.108.32.49

$b_{j}/t_{j}\,$ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

$B_{t}={\begin{cases}B_{s}+(t-s){\frac {b_{i}}{t_{i}}},&s\leq t=<s+t_{i}\\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}}\,$

หลังจากสลับแล้วเราจะเริ่มส่งวิดีโอ $j\,$ ณ เวลา

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 626922503
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:54 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s\,$ และจะส่งเสร็จที่เวลา

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 574460371
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:54 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s+t_{j}\,$ ซึ่งในเวลาเดียวกันเราจะเริ่มส่งวิดีโอ $i\,$ และจะส่งมันเสร็จที่เวลา

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 567742803
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:55 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s+t_{j}+t_{i}=s+t_{i}+t_{j}\,$ ให้ $B'_{t}\,$ แทนจำนวนบิตที่ส่งผ่าน network link ตั้งแต่เวลา 0 ถึง $t\,$ หลังจากการสลับ เราจะได้ว่าตั้งแต่เวลา

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 631180597
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:56 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s\,$ ถึง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 599951188
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:56 GMT


Sensitive client information

IP address: 158.108.32.49

$t=t_{j}\,$ ค่า $B'_{t}\,$ จะมีค่าเพิ่มขึ้นวินาทีละ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 430710264
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:56 GMT


Sensitive client information

IP address: 158.108.32.49

$b_{j}/t_{j}\,$ ส่วนในเวลาตั้งแต่ $t=s+t_{j}\,$ ถึง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 477696189
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:57 GMT


Sensitive client information

IP address: 158.108.32.49

$t=s+t_{i}+t_{j}\,$ ค่า $B'_{t}\,$ จะเพิ่มขึ้นวินาทีละ $b_{i}/t_{i}\,$ ซึ่งเราสามารถเขียนสรุปเป็นสัญลักษณ์ได้ดังต่อไปนี้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 427888841
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:58 GMT


Sensitive client information

IP address: 158.108.32.49

$B'_{t}={\begin{cases}B_{s}+(t-s){\frac {b_{j}}{t_{j}}},&s\leq t<s+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}}\,$

เป้าหมายต่อไปของเราคือการพิสูจน์ lemma ต่อไปนี้

lemma 1: สำหรับจำนวนเต็ม $t\,$ ทุกตัวที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 582719715
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:58 GMT


Sensitive client information

IP address: 158.108.32.49

$s\leq t\leq s+t_{i}+t_{j}\,$ เราได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 507451577
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:58 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}\geq B'_{t}\,$

โดยที่หาก lemma นี้เป็นจริง เราจะได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 549327965
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:59 GMT


Sensitive client information

IP address: 158.108.32.49

$\max _{s\leq t\leq s+t_{i}+t_{j}}B_{t}/t\geq \max _{s\leq t\leq s+t_{i}+t_{j}}B'_{t}/t\,$ เนื่องจาก สมมติให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 610473943
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:59 GMT


Sensitive client information

IP address: 158.108.32.49

$\max _{s\leq t\leq s+t_{i}+t_{j}}B'_{t}/t=B'_{u}/u\,$ โดยที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 498992899
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:59 GMT


Sensitive client information

IP address: 158.108.32.49

$u\,$ เป็นจำนวนเต็มตัวหนึ่งที่อยู่ในช่วง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 507844428
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:53:59 GMT


Sensitive client information

IP address: 158.108.32.49

$[s,s+t_{i}+t_{j}]\,$ แล้ว เราจะได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 589699535
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:00 GMT


Sensitive client information

IP address: 158.108.32.49

$B'_{u}/u\leq B_{u}/u\leq \max _{s\leq t\leq s+t_{i}+t_{j}}B_{t}/t\,$ ฉะนั้นเราจึงสามารถสรุปได้ว่าหลังจากสลับแล้ว $\max _{1\leq t\leq T}B_{t}/t\,$ จะมีค่าไม่เพิ่มขึ้น และการส่งวิดีโอตามลำดับ $b_{i}/t_{i}\,$ จากมากไปน้อยทำให้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ ต่ำที่สุดเท่าที่จะเป็นไปได้

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

พิสูจน์: สำหรับจำนวนเต็ม $t\,$ ที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 430545579
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:01 GMT


Sensitive client information

IP address: 158.108.32.49

$s\leq t\leq s+t_{i}+t_{j}\,$นิยามค่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 547230480
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:01 GMT


Sensitive client information

IP address: 158.108.32.49

$B''_{t}=B_{s}+(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}\,$

เราจะแสดงว่า สำหรับ $t\,$ ทุกค่าที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 533566027
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:02 GMT


Sensitive client information

IP address: 158.108.32.49

$s\leq t\leq s+t_{i}+t_{j}\,$

1. 

   Error

   Too many requests (f061ab2)

   If you report this error to the Wikimedia System Administrators, please include the details below.

   Request served via cp5021 cp5021, Varnish XID 566661996
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:02 GMT


   Sensitive client information

   IP address: 158.108.32.49

   $B_{t}\geq B''_{t}\,$
2. 

   Error

   Too many requests (f061ab2)

   If you report this error to the Wikimedia System Administrators, please include the details below.

   Request served via cp5021 cp5021, Varnish XID 576394813
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:02 GMT


   Sensitive client information

   IP address: 158.108.32.49

   $B''_{t}\geq B'_{t}\,$

หากสามารถทำเช่นนี้ได้ เราก็จะสามารถสรุปได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 515510717
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:03 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}\geq B'_{t}\,$ สำหรับ $t\,$ ทุกค่า

การพิสูจน์ข้อวามทั้งสองข้อข้างบนนี้จะใช้ความจริงที่ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 521999473
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:03 GMT


Sensitive client information

IP address: 158.108.32.49

${\frac {b_{i}}{t_{i}}}>{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}>{\frac {b_{j}}{t_{j}}}\,$ หลายครั้ง เราจะพิสูจน์ข้อความนี้เป็น lemma 2 หลังจากพิสูจน์ lemma 1

(ข้อความที่ 1) เราจะได้ว่า ถ้า $s\leq t<s+t_{i}\,$ แล้ว

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 567580218
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:04 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}=B_{s}+(t-s){\frac {b_{i}}{t_{i}}}>B_{s}+(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}=B''_{t}\,$

ถ้า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 535893084
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:04 GMT


Sensitive client information

IP address: 158.108.32.49

$s+t_{i}\leq t\leq s+t_{i}+t_{j}\,$ แล้ว

Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 444083515 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:04 GMT Sensitive client information IP address: 158.108.32.49 $B_{t}-B''_{t}\,$	$=\,$	Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 625707635 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:05 GMT Sensitive client information IP address: 158.108.32.49 $b_{i}+(t-s-t_{i}){\frac {b_{j}}{t_{j}}}-(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}=t_{i}{\frac {b_{i}}{t_{i}}}+(t-t_{i}){\frac {b_{j}}{t_{j}}}-(t-s){\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}\,$
$\,$	$=\,$	Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 603724340 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:06 GMT Sensitive client information IP address: 158.108.32.49 $b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-(t-s){\bigg (}{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}-{\frac {b_{j}}{t_{j}}}{\bigg )}\,$
$\,$	$\geq \,$	Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 413177052 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:07 GMT Sensitive client information IP address: 158.108.32.49 $b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-(t_{i}+t_{j}){\bigg (}{\frac {b_{i}+b_{j}}{t_{i}+t_{j}}}-{\frac {b_{j}}{t_{j}}}{\bigg )}\,$
$\,$	$=\,$	Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 549525046 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:07 GMT Sensitive client information IP address: 158.108.32.49 $b_{i}-t_{i}{\frac {b_{j}}{t_{j}}}-b_{i}-b_{j}+t_{i}{\frac {b_{j}}{t_{j}}}+b_{j}\,$
$\,$	$=\,$	$0\,$

ดังนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 536875014
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:08 GMT


Sensitive client information

IP address: 158.108.32.49

$B_{t}\geq B''_{t}\,$ ในกรณีนี้เช่นกัน

(ข้อความที่ 2) การพิสูจน์คล้ายๆ กับข้อความที่ 1 เราละให้นิสิตทำเป็นแบบฝึกหัด (จบการพิสูจน์ lemma 1)

lemma 2: ถ้า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 530451254
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:09 GMT


Sensitive client information

IP address: 158.108.32.49

$a,b,c,d\,$ เป็นจำนวนที่มีค่าไม่เป็นลบโดยที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 630459855
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:09 GMT


Sensitive client information

IP address: 158.108.32.49

${\frac {a}{b}}>{\frac {c}{d}}\,$ แล้ว

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 591664198
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:09 GMT


Sensitive client information

IP address: 158.108.32.49

${\frac {a}{b}}>{\frac {a+c}{b+d}}>{\frac {c}{d}}\,$

พิสูจน์: เนื่องจาก ${\frac {a}{c}}>{\frac {b}{d}}\,$ เราจะได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 575542014
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:10 GMT


Sensitive client information

IP address: 158.108.32.49

$ad>bc\,$ ฉะนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 485204318
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:10 GMT


Sensitive client information

IP address: 158.108.32.49

$ab+ad>ab+bc\,$ ซึ่งหมายความว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 457446292
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:34 GMT


Sensitive client information

IP address: 158.108.32.49

$a(b+d)>b(a+c)\,$ ฉะนั้น

การพิสูจน์ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 443586148
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:36 GMT


Sensitive client information

IP address: 158.108.32.49

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

การหาค่า $\max _{1\leq t\leq T}B_{t}/t\,$

เราทราบว่าการส่งวิดีโอโดยเรียงลำดับตาม จะทำให้่ีค่า $\max _{1\leq t\leq T}B_{t}/t\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้ แต่ด้วยความรู้เพียงแค่นี้เราไม่สามารถตัดสินได้ว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่ เนื่องจากเราไม่ร้ค่า $\max _{1\leq t\leq T}B_{t}/t\,$ เราจึงจำเป็นต้องออกแบบอัลกอริทึมเพื่อหาค่าดังกล่าว

อย่างไรก็ดีค่า เราสามารถหาค่า $\max _{1\leq t\leq T}B_{t}/t\,$ เมื่อเราเรียงวิดีโอตาม $b_{i}/t_{i}\,$ ได้ง่ายมาก เราจะพิสูจน์ว่าค่านั้นคือ ซึ่งมีค่าเท่ากับจำนวนบิตที่ส่งทั้งหมดหารด้วยเวลาส่งทั้งหมด

lemma 3: ถ้าเราเรียงวิดีโอให้ แล้ว สำหรับค่า ทุกค่าที่ $1\leq t\leq T\,$ เราจะได้ว่า นอกจากนี้ ถ้าในช่วงเวลาตั้งแต่ ถึงเวลา $t\,$ เราทำการส่งวิีดีโด แล้วเราจะได้ว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i}}{t_{i}}}\,$

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

(Base Case) ในกรณีนี้ เราได้ว่าในวินาทีแรกเราจะส่งข้อมูล

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 581277525
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:13 GMT


Sensitive client information

IP address: 158.108.32.49

$b_{1}/t_{1}\,$ บิตในเวลา 1 วินาที ดังนั้น ตามต้องการ

(Induction Case) สมมติให้ lemma เป็นจริงสำหรับ บางค่า พิจารณาเหตุการณ์ที่เกิดขึ้น ณ ช่วงเลาตั้งแต่ $t\,$ ถึง $t+1\,$ และสมมติว่าในช่วงเวลานี้เราทำการส่งวิดีโอ $i\,$ ผ่าน network link กล่าวคือในวินาทีนั้นเราส่งข้อมูลจำนวน บิต ในกรณีนี้มีความเป็นไปได้อยู่สองกรณี

กรณีแรกคือ เราเริ่มส่งวิดีโอ $i\,$ ตั้งแต่ก่อนเวลา $t\,$ อยู่แล้ว ในกรณีนี้สมมติฐานของ induction บอกเราว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i}}{t_{i}}}={\frac {b_{i}/t_{i}}{1}}\,$ ฉะนั้นจาำก lemma 2 เราได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 608863542
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:14 GMT


Sensitive client information

IP address: 158.108.32.49

${\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}}}\,$ เนื่องจาก ${\frac {B_{t+1}}{t+1}}={\frac {B_{t}+b_{i}/t_{i}}{t+1}}\,$ เราจึงได้ว่า ด้วย

กรณีที่สองคือ เราเริ่มส่งวิดีโอ ณ เวลา พอดี กล่าวคือในช่วงเวลาตั้งแต่ ถึง เราำกำลังส่งวิดีโอ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 453285037
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:15 GMT


Sensitive client information

IP address: 158.108.32.49

$i-1\,$ อยู่ ในกรณีนี้สมมติฐานของ indunction บอกเราว่า ${\frac {B_{t}}{t}}\leq {\frac {b_{i-1}}{t_{i-1}}}\leq {\frac {b_{i}}{t_{i}}}\,$ และเราสามารถใช้เหตุผลในกรณีที่แล้วพิสูจน์ว่า lemma เป็นจริงสำหรับ ด้วยเช่นกัน

จาก lemma 3 เราได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 609359405
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:16 GMT


Sensitive client information

IP address: 158.108.32.49

$\max _{1\leq t\leq T}B_{t}/t=B_{T}/T\,$

ฉะนั้นการหาว่าเราสามารถส่งวิดีโอตามกฎ (*) ได้หรือไม่สามารถทำได้โดยการหาผลรวม $B_{T}=\sum _{i=1}^{n}b_{i}\,$ และ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 629773966
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Mon, 27 Apr 2026 23:54:17 GMT


Sensitive client information

IP address: 158.108.32.49

$T=\sum _{i=1}^{n}t_{i}\,$ แล้วตรวจสอบว่า $B_{T}/T\,$ มากกว่า หรือไม่ เห็นได้อย่างชัดเจนว่าอัลกอริทึมนี้ทำงานในเวลา