Toán 9 · Cận trên theo cửa sổ liên tiếp, cấu trúc tuần hoàn và nguyên lý Dirichlet: chia khối, dựng cực trị, đếm tập cực đại và hai ràng buộc qua 7 phòng thí nghiệm tương tác
Bài khái niệm Toán 9 học sinh giỏi về bài toán chọn nhiều số nhất từ 1 đến N sao cho trong w số liên tiếp có không quá k số: cận trên bằng cách chia dãy…
TOÁN 9 · HỌC SINH GIỎI · BÀI GIẢNG KHÁI NIỆM
Cận trên theo cửa sổ liên tiếp, cấu trúc tuần hoàn và nguyên lý Dirichlet
Chọn nhiều số nhất có thể từ 1, 2, …, N sao cho trong bất kỳ w số liên tiếp có không quá k số được chọn. Bài toán này có cấu trúc rất gọn: cận trên đến từ việc chia dãy thành các khối và dùng nguyên lý Dirichlet, còn cận dưới đến từ một cách xếp tuần hoàn theo chu kỳ w. Hai cận khớp nhau, nên đáp số là một công thức chính xác. Bảy phòng thí nghiệm giúp bạn tự bấm chọn, tự tìm cửa sổ vi phạm, thử các cách xếp tuần hoàn khác, đếm mọi tập cực đại và xem điều gì xảy ra khi hai ràng buộc cùng tồn tại.
7 phòng thí nghiệm tương tác tự bấm chọn tập số 8 hiểu lầm được phản biện 14 câu kiểm tra khái niệm không giải đề
1 Cửa sổ 2 Chia khối 3 Dirichlet 4 Tuần hoàn 5 Mật độ 6 Cực trị 7 Hai ràng buộc 8 Atlas 9 Kiểm tra ★ Tổng kết
1 Cửa sổ trượt và tập “thưa”
Cho các số nguyên dương N, w và k với k ≤ w. Một cửa sổ là w số nguyên liên tiếp, và ta chỉ xét các cửa sổ nằm hoàn toàn trong {1, 2, …, N}: có N − w + 1 cửa sổ như thế khi N ≥ w. Một tập S ⊆ {1, …, N} gọi là (w, k)-thưa nếu mọi cửa sổ chứa không quá k phần tử của S. Gọi M(N) là số phần tử lớn nhất của một tập (w, k)-thưa. Ví dụ quen thuộc: “trong bất kỳ 7 số liên tiếp có tối đa 2 số được chọn” là trường hợp w = 7, k = 2.
Hai nhận xét nhỏ nhưng quan trọng. Thứ nhất, nếu S thưa thì mọi tập con của S cũng thưa: ràng buộc là “không quá k”, không phải “đúng k”. Thứ hai, nếu N < w thì không có cửa sổ nào , ràng buộc trống rỗng và ta chọn được cả N số. Mọi công thức ở các phần sau chỉ dùng cho N ≥ w.
Lab 1 · Tự bấm chọn và tìm cửa sổ vi phạm
Bấm vào các ô để chọn hoặc bỏ chọn số. Ô viền đỏ nằm trong một cửa sổ có hơn k số được chọn. Nút “Tham lam” thêm số từ trái sang phải khi chưa vi phạm; nút “Mẫu tuần hoàn” chọn các số có chỉ số dư 1, …, k theo mod w.
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
N = –
số đã chọn |S|
cận M(N) = k·⌊N/w⌋ + min(k, N mod w)
số lớn nhất trong một cửa sổ
trạng thái
2 Cận trên: chia dãy thành các khối
Viết N = q·w + r với q = ⌊N/w⌋ và 0 ≤ r < w. Chia dãy thành q khối đầu, mỗi khối w số liên tiếp, và một khối cuối gồm r số còn lại. Mỗi khối đầu là một cửa sổ, nên chứa không quá k số được chọn. Khối cuối chứa không quá r số vì chỉ có r số, và cũng không quá k số vì nó nằm trong cửa sổ w số cuối cùng của dãy (có thể mở rộng khối cuối sang trái cho đủ w số khi N ≥ w). Cộng lại,
M(N) ≤ k·q + min(k, r).
Phép chia khối là một cách đếm : ta không cần biết tập S trông thế nào, chỉ cần biết mỗi khối bị chặn. Cận này có đúng không, tức là có tập nào đạt được nó không? Phòng thí nghiệm dưới đây tính M(N) bằng quy hoạch động, độc lập với công thức, rồi đặt cạnh cận khối.
Lab 2 · Chia khối và so với đáp số chính xác
Các khối xanh là q cửa sổ đầu, khối cam nét đứt là phần dư r số. Số trên mỗi khối là cận của khối. Chấm sáng là tập tuần hoàn của phần 4. Máy tính M(N) bằng quy hoạch động trên mọi tập hợp lệ rồi so với k·q + min(k, r).
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
N = –
q · r
cận khối k·q + min(k, r)
M(N) tính bằng quy hoạch động
so sánh
3 Nguyên lý Dirichlet: vượt cận là phải vi phạm
Đảo lại cận trên, ta có một khẳng định có thể kiểm tra: nếu |S| > k·q + min(k, r) thì S chắc chắn chứa một cửa sổ có ít nhất k + 1 phần tử. Chứng minh bằng nguyên lý Dirichlet cho các khối: nếu mọi khối đầu có không quá k phần tử và phần dư có không quá min(k, r), thì |S| ≤ k·q + min(k, r), mâu thuẫn. Vậy hoặc một khối đầu có ≥ k + 1 phần tử, hoặc phần dư có ≥ k + 1 phần tử. Trong trường hợp sau, các phần tử đó nằm trong cửa sổ w số cuối cùng, nên cửa sổ ấy vi phạm.
Điểm tinh tế: khối cuối ngắn hơn w nhưng không vô dụng. Khi r ≤ k, nó không thể vi phạm một mình (chỉ có r ≤ k số), và đó chính là lý do cận có dạng k·q + r thay vì k·q + k. Khi r > k, nó có thể chứa k + 1 số, và những số ấy nằm gọn trong cửa sổ cuối.
Lab 3 · Chọn nhiều hơn cận, để máy tìm cửa sổ vi phạm
Máy chọn ngẫu nhiên một tập kích thước bạn muốn, rồi tìm khối hoặc cửa sổ vi phạm theo đúng lập luận trên. Với kích thước vượt cận, máy luôn tìm được. Với đúng cận hoặc ít hơn, không có gì đảm bảo.
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
N = –
đã chọn |S| · cận B
khối vi phạm (đầu tiên)
cửa sổ vi phạm
số phần tử trong cửa sổ đó
4 Cận dưới: cách xếp tuần hoàn
Xét tập S₀ gồm các số i có chỉ số dư ((i − 1) mod w) + 1 nằm trong {1, …, k} ; nói cách khác, ta chọn k số đầu của mỗi chu kỳ w. Mọi cửa sổ w số liên tiếp chứa đúng một số từ mỗi lớp dư theo mod w, nên chứa đúng k phần tử của S₀: tập này thưa. Đếm trong {1, …, N}: mỗi khối đầu cho k phần tử, phần dư r số cho min(k, r) phần tử, tổng k·q + min(k, r), đúng bằng cận trên. Vậy với N ≥ w,
M(N) = k·⌊N/w⌋ + min(k, N mod w).
Còn một câu hỏi hợp lý: có phải mọi k lớp dư đều cho đáp số tối ưu? Với N chia hết cho w thì đúng, vì mọi lựa chọn đều cho k·q. Nhưng với các N khác thì phần dư quyết định: chỉ khi các lớp dư được chọn là {1, …, k} thì phần dư r luôn cho min(k, r) phần tử. Phòng thí nghiệm này cho bạn tự chọn các lớp dư.
Lab 4 · Chọn các lớp dư theo mod w
Bấm các nút lớp dư để chọn bộ R. Mỗi cửa sổ luôn chứa đúng |R| phần tử, nên hợp lệ khi |R| ≤ k. Máy đếm số phần tử trong {1, …, N} và so với cận M(N), rồi kiểm tra bộ R có tối ưu với mọi N từ w đến 6w hay không.
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
N = –
Lớp dư (chỉ số 1, …, w):
|R| và cửa sổ lớn nhất
số phần tử trong {1, …, N} · M(N)
tối ưu với N này?
tối ưu với mọi N từ w đến 6w?
5 Mật độ k/w và phần dư vượt trội
Trong dài hạn mỗi cửa sổ chứa tối đa k trên w số, nên ta mong M(N) ≈ k·N/w. Đúng là M(N) ≥ k·N/w với mọi N ≥ w, vì min(k, r) ≥ k·r/w khi 0 ≤ r < w. Phần vượt trội là
M(N) − k·N/w = min(k, r) − k·r/w,
một hàm tuần hoàn theo r, tăng đến r = k rồi giảm về 0 ở r = w. Giá trị lớn nhất là k·(w − k)/w, đạt đúng khi N chia w dư k. Vì vậy cận “làm tròn” như ⌈k·N/w⌉ có thể thấp hơn đáp số thật: với w = 7, k = 2, N = 9 ta có ⌈18/7⌉ = 3 nhưng M(9) = 4. Biểu đồ dưới cho thấy răng cưa này.
Lab 5 · M(N), đường k·N/w và độ vượt trội
Biểu đồ trên: bậc thang M(N) (chấm vàng) so với đường thẳng k·N/w. Biểu đồ dưới: phần vượt trội M(N) − k·N/w, tuần hoàn theo chu kỳ w, lớn nhất tại N ≡ k (mod w).
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
Chấm vàng: M(N). Đường xanh: k·N/w. Đường tím: bậc thang nối. Trên màn hình hẹp, vuốt ngang để xem hết hình.
Phần vượt trội. Đường vàng nét đứt: giá trị lớn nhất k·(w − k)/w.
max M(N) − kN/w trên N từ w đến 60
k·(w − k)/w
N đạt max đầu tiên
M(N) ≥ k·N/w mọi N?
6 Tập cực đại có duy nhất không?
Tập S₀ đạt cận, nhưng nó có phải tập cực đại duy nhất? Thường là không. Với N = w, mọi tập k phần tử đều hợp lệ và cực đại: có C(w, k) tập. Khi N tăng từ w, số tập cực đại lúc đầu giảm mạnh (với w = 7, k = 2: 21, 6, 1 tập) nhưng không giảm mãi: nó tăng trở lại khi N rời khỏi dư k. Quan sát bằng quy hoạch động với w ≤ 7 và 1 ≤ k < w: tập cực đại là duy nhất đúng khi N chia w dư k . Khi đó M(N) = k·q + k, mỗi khối đầu phải đầy k phần tử và phần dư cũng đầy, nên hầu như không còn chỗ xê dịch.
Lab này đếm chính xác số tập cực đại, kể cả khi con số rất lớn, và liệt kê một số tập. Chú ý dòng nào là tập tuần hoàn S₀ và dòng nào không.
Lab 6 · Đếm và liệt kê tập cực đại
Ô đậm là số được chọn. Máy đếm mọi tập hợp lệ có đúng M(N) phần tử bằng quy hoạch động và liệt kê tối đa 10 tập.
w (độ dài cửa sổ)
k (tối đa trong một cửa sổ)
N = –
M(N)
số tập cực đại
N mod w so với k
duy nhất?
7 Hai ràng buộc cùng lúc: cận nhỏ nhất chưa chắc đạt
Giả sử đồng thời có hai ràng buộc: trong w₁ số liên tiếp có tối đa k₁, và trong w₂ số liên tiếp có tối đa k₂. Mỗi ràng buộc riêng cho một cận B₁, B₂, nên M ≤ min(B₁, B₂). Câu hỏi tự nhiên: cận nhỏ hơn có luôn đạt được không? Không. Có cặp ràng buộc mà hai cận riêng cùng bằng 6 nhưng tập hợp lệ lớn nhất chỉ có 5 phần tử, vì hai cách xếp tuần hoàn tối ưu của hai ràng buộc không tương thích nhau. Cũng có cặp mà cận nhỏ nhất đạt đủ: khi cách xếp tối ưu của ràng buộc chặt hơn tình cờ thỏa luôn ràng buộc kia.
Lab 7 · Hai ràng buộc, hai cận, một đáp số
Chọn một cặp ràng buộc. Biểu đồ so sánh min(B₁, B₂) với giá trị chính xác từ quy hoạch động theo N: đường vàng thấp hơn đường xanh ở những N có “khe hở”.
N = –
Xanh: min(B₁, B₂). Vàng: giá trị chính xác. Đường dọc trắng nét đứt: N hiện tại. Trên màn hình hẹp, vuốt ngang để xem hết hình.
B₁ · B₂ · min
giá trị chính xác (DP)
khe hở
một tập cực đại
8 Atlas hiểu lầm · tám ngộ nhận và lời phản biện
Bấm vào từng thẻ để mở.
1 · “Công thức k·⌊N/w⌋ + min(k, N mod w) đúng với mọi N”
Chỉ đúng khi N ≥ w. Nếu N < w thì không có cửa sổ nào, ràng buộc trống, và ta chọn được cả N số. Với w = 7, k = 2, N = 5 công thức cho min(2, 5) = 2 nhưng thực ra chọn cả 5 số vẫn hợp lệ. Phép chia khối cũng đòi hỏi N ≥ w để “khối cuối” nằm trong một cửa sổ.
2 · “Cận là làm tròn lên của k·N/w”
Sai ở N = 9 với w = 7, k = 2: ⌈2·9/7⌉ = ⌈2,57⌉ = 3 nhưng tập {1, 2, 8, 9} có 4 phần tử và vẫn thưa (cửa sổ 3–9 chứa 8, 9; cửa sổ 2–8 chứa 2, 8). Vì M(N) − k·N/w có thể đạt tới k·(w − k)/w = 10/7 ≈ 1,43, phép làm tròn không đủ. Phải chia khối và tính phần dư.
3 · “Mỗi cửa sổ phải chứa đúng k số được chọn”
Điều kiện chỉ là không quá k. Bỏ một phần tử khỏi tập thưa thì vẫn thưa. Tập tuần hoàn S₀ thì “vừa khít” (mọi cửa sổ có đúng k), nhưng đó là tính chất của tập cực đại tuần hoàn, không phải điều kiện bắt buộc. Tập rỗng cũng thưa.
4 · “Chọn k lớp dư bất kỳ đều cho đáp số tối ưu”
Mọi bộ k lớp dư đều tối ưu chỉ khi N chia hết cho w; với các N khác, tối ưu hay không còn tùy bộ lớp dư. Với w = 7, k = 2 và chọn các số i có i mod 7 ∈ {3, 4}: N = 8 chỉ có 2 phần tử (3 và 4), trong khi M(8) = 3. Duyệt mọi cặp lớp dư và mọi N từ 7 đến 60: chỉ cặp {1, 2} tối ưu với mọi N.
5 · “Tập cực đại luôn duy nhất” hoặc “luôn có nhiều tập”
Cả hai đều sai. Với w = 7, k = 2: N = 7 có 21 tập cực đại (mọi cặp), N = 8 có 6 tập, N = 9 chỉ có một tập là {1, 2, 8, 9}, N = 10 lại có 6 tập. Quan sát bằng máy với w ≤ 7 và 1 ≤ k < w: tập cực đại duy nhất đúng khi N chia w dư k.
6 · “Khối cuối ngắn hơn w nên không dùng được nguyên lý Dirichlet”
Dùng được, với một lập luận bổ sung: nếu r ≤ k thì khối cuối không vi phạm một mình, và cận cộng r thay vì k. Nếu r > k mà khối cuối có k + 1 số, các số ấy nằm trong cửa sổ w số cuối cùng của dãy (mở rộng khối sang trái), nên cửa sổ đó vi phạm. Lab 3 minh họa cả hai trường hợp.
7 · “Mỗi ràng buộc đạt cận thì hai ràng buộc cùng đạt cận nhỏ nhất”
Sai. Với (w₁, k₁) = (5, 2) và (w₂, k₂) = (7, 3), N = 12: B₁ = 2·2 + min(2, 2) = 6 và B₂ = 3·1 + min(3, 5) = 6, nhưng tập hợp lệ lớn nhất chỉ có 5 phần tử (quy hoạch động). Hai cách xếp tuần hoàn tối ưu không cùng tồn tại. Cặp (3, 1) và (5, 2) thì đạt min với mọi N đã kiểm tra.
8 · “Thêm một số vào dãy (N tăng 1) thì M(N) luôn tăng 1”
M(N) tăng 1 khi N mod w nằm trong 1, …, k (thêm phần tử tuần hoàn mới) và giữ nguyên các lần khác. Với w = 7, k = 2: M(7), M(8), …, M(15) = 2, 3, 4, 4, 4, 4, 4, 4, 5. Có năm lần liên tiếp N tăng mà đáp số đứng yên: M(9) = M(10) = … = M(14) = 4 (tổng quát là w − k lần).
9 Kiểm tra khái niệm
Sáu câu trắc nghiệm và hai nhóm đúng–sai. Mỗi đáp án đều có giải thích ngắn.
Điểm của bạn: 0 / 0
Làm hết các câu để thấy tổng kết.
★ Tổng kết · bảy điều phải nhớ
1. Tập S ⊆ {1, …, N} là (w, k)-thưa nếu mọi cửa sổ w số liên tiếp (nằm trong dãy) có không quá k phần tử của S. Nếu N < w thì không có cửa sổ và chọn được cả N số.
2. Cận trên: viết N = q·w + r, chia thành q khối w số và khối dư r số. Mỗi khối đầu có ≤ k, khối dư có ≤ min(k, r). Vậy M(N) ≤ k·q + min(k, r) khi N ≥ w.
3. Nguyên lý Dirichlet cho thấy cận trên cũng là một thuật toán: tập có hơn k·q + min(k, r) phần tử chắc chắn chứa một khối hoặc cửa sổ cuối có ≥ k + 1 phần tử.
4. Cận dưới: chọn các số có chỉ số dư 1, …, k theo mod w. Mọi cửa sổ có đúng k phần tử và tổng số phần tử là k·q + min(k, r). Hai cận khớp nhau: M(N) = k·⌊N/w⌋ + min(k, N mod w).
5. Không phải bộ k lớp dư nào cũng tối ưu: mọi bộ chỉ tối ưu đồng loạt khi w chia hết N, còn để tối ưu với mọi N thì chỉ có {1, …, k}. Làm tròn k·N/w cũng không thay được công thức, vì phần vượt trội M(N) − k·N/w lớn nhất bằng k·(w − k)/w tại N ≡ k (mod w).
6. Tập cực đại thường không duy nhất (N = w có C(w, k) tập). Quan sát bằng máy với w ≤ 7: duy nhất đúng khi N chia w dư k.