Đến nội dung

Hình ảnh

Một Quốc hội có n thượng nghị sĩ, chia thành 10 đảng và 10 uỷ ban. Mỗi nghị sĩ thuộc về đúng một đảng và đúng một uỷ ban. Giả sử tên gọi các đảng là P₁,..., P10 và các uỷ ban là C1, ...,C1


  • Please log in to reply
Chủ đề này có 1 trả lời

#1
Giabao209

Giabao209

    Binh nhất

  • Thành viên mới
  • 43 Bài viết

Một Quốc hội có n thượng nghị sĩ, chia thành 10 đảng và 10 uỷ ban. Mỗi nghị sĩ thuộc về đúng một đảng và đúng một uỷ ban. Giả sử tên gọi các đảng là P₁,..., P10 và các uỷ ban là C1, ...,C10. Tìm số bé nhất n sao cho có ít nhất 11 nghị sĩ mà mỗi người trong nhóm này thuộc về một đảng và một uỷ ban có cùng chỉ số .



#2
Kii Yashiro

Kii Yashiro

    Binh nhất

  • Thành viên mới
  • 20 Bài viết

Một Quốc hội có n thượng nghị sĩ, chia thành 10 đảng và 10 uỷ ban. Mỗi nghị sĩ thuộc về đúng một đảng và đúng một uỷ ban. Giả sử tên gọi các đảng là P₁,..., P10 và các uỷ ban là C1, ...,C10. Tìm số bé nhất n sao cho có ít nhất 11 nghị sĩ mà mỗi người trong nhóm này thuộc về một đảng và một uỷ ban có cùng chỉ số .

Không biết đúng hay không cơ mà cứ thử :v

Ta nhận thấy có 100 bộ P_k C_n khác nhau với k, n là các số nguyên trong khoảng [1, 10].

Vậy trong trường hợp xấu nhất thì có 1000 tns và một bộ P_k C_n bất kì có đúng 10 người.

Bây giờ nhét 1 người vô nữa thì chắc chắn có 11 người chung đảng và uỷ ban.

Vậy n = 1001






2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh