Câu hỏi 22
Trong một khu rừng, mỗi loài động vật $n$ ($n \geqslant 3$) sống trong hang động riêng của mình và có chính xác một con đường riêng biệt giữa hai hang động bất kỳ. Trước cuộc bầu cử Vua Rừng, một số loài động vật thực hiện một chiến dịch bầu cử. Mỗi con vật thực hiện chiến dịch đến thăm mỗi hang động khác đúng một lần, chỉ sử dụng đường đi để di chuyển từ hang này sang hang khác, không bao giờ chuyển từ đường này sang đường khác giữa các hang và quay về hang riêng của mình khi kết thúc chiến dịch. Người ta cũng biết rằng không có con đường nào giữa hai hang động được sử dụng bởi nhiều hơn một động vật thực hiện chiến dịch.
a) Chứng minh rằng với bất kỳ $n$ nguyên tố nào, số lượng động vật thực hiện chiến dịch tối đa có thể là $\frac{n-1}{2}$;
b) Tìm số lượng động vật tạo chiến dịch tối đa cho $n=9$.
a) Chứng minh rằng với bất kỳ $n$ nguyên tố nào, số lượng động vật thực hiện chiến dịch tối đa có thể là $\frac{n-1}{2}$;
b) Tìm số lượng động vật tạo chiến dịch tối đa cho $n=9$.