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 4 trên 4: Bỏ đi rồi chèn lại vv
Bước trướcBước tiếp
deg⁡−(v)≤28, deg⁡+(v)≤28  ⟹  v has≤56 neighbours\deg^-(v)\le28,\ \deg^+(v)\le28 \implies v \text{ has} \le56 \text{ neighbours}
Phân tích chi tiết

Bỏ vv đi; theo giả thiết quy nạp, phần đồ thị còn lại chia được thành nhiều nhất 5757 nhóm hợp lệ. Đỉnh vv có bậc vào và bậc ra mỗi loại nhiều nhất 2828 trong đồ thị gốc, nên nó kề với nhiều nhất 5656 đỉnh khác, chiếm nhiều nhất 5656 trong số 5757 nhóm. Do đó có một nhóm không chứa láng giềng nào của nó, và vv có thể đặt vào đó, hoàn tất quy nạp. Vậy 5757 nhóm luôn đủ, nên k=57k=57.