MathLabs

Bài 4

Đất nước Dreamland gồm 20162016 thành phố. Hãng hàng không Starways muốn thiết lập một số chuyến bay một chiều giữa các cặp thành phố sao cho mỗi thành phố có đúng một chuyến bay xuất phát từ nó. Tìm số nguyên dương nhỏ nhất kk sao cho dù Starways thiết lập các chuyến bay như thế nào, các thành phố luôn có thể được chia thành kk nhóm sao cho từ một thành phố bất kỳ không thể đến một thành phố khác trong cùng nhóm bằng cách dùng nhiều nhất 2828 chuyến bay.
Bước 3 trên 4: Bổ đề, theo quy nạp trên số đỉnh
Bước trướcBước tiếp
n≥1, deg⁡+≤28  ⟹  split into 57 groups, no internal edgen\ge1,\ \deg^+\le28 \implies \text{split into } 57 \text{ groups, no internal edge}
Phân tích chi tiết

Bổ đề: mọi đồ thị có hướng trên n≥1n\ge1 đỉnh với bậc ra nhiều nhất 2828 tại mọi đỉnh đều có thể chia thành 5757 nhóm sao cho không có cạnh nào bên trong một nhóm. Chứng minh bằng quy nạp trên nn: trường hợp cơ sở n=1n=1 là hiển nhiên. Với n>1n>1, tổng số cạnh nhiều nhất là 28n28n, nên có một đỉnh vv với bậc vào nhiều nhất 2828 (nếu không, mọi đỉnh sẽ có bậc vào ít nhất 2929, cho hơn 28n28n cạnh).