Trò chơi Dobble: một đề thi hsg toán ở Pháp 2015

Vào ngày 18/03/2015 ở Pháp đã diễn ra cuộc thi hsg toán “Olympiades Académiques de Mathématiques”.  Chữ “académique” ở đây hiểu là “sở giáo dục” — mỗi sở giáo dục của một vùng (như kiểu một tỉnh) của Pháp gọi là một academia. Nhưng kỳ thi này không chỉ là cấp vùng, mà cũng là cấp toàn quốc luôn. Mỗi đề thi gồm có 4 bài, trong đó 2 bài chung cho toàn quốc, và 2 bài riêng của vùng.

Ỏ đây tôi muốn giới thiệu một bài của cuộc thi này, vừa thú vị nhưng lại vừa rất sơ cấp, học sinh tiểu học cũng có thể hiểu và có thể làm được nếu suy luận tốt. Đó là bài Số 3 trong đề thi ở Toulouse.  Bài này là về một trò chơi với các quân bài, gọi là Dobble, xuất hiện từ năm 2009 và có bán ở các cửa hàng đồ chơi ở Pháp.

Một bộ quân bài Dobble gồm các quân bài, mà trên mỗi quân bài có vẽ N hình gì đó khác nhau (xem hình vẽ minh họa), trong đó N là một số tự nhiên (trong bộ bài Dobble chuẩn thì N=8 và có 55 quân bài, nhưng cũng có bộ bài với N=6, và về nguyên tắc thì N bằng bao nhiêu cũng được).
Các hình vẽ trên các quân bài thỏa mãn các điều kiện sau đây: cứ 2 quân bài bất kỳ trong bộ bài thì có đúng 1 hình trùng nhau, và không có hình nào xuất hiện trên toàn bộ các quân bài. (Hình ở đây có thể là bất cứ một vật gì: con chim, chìa khóa, tàu thủy, chữ O, v.v.). Xem các hình minh họa đính kèm.

Có nhiều kiểu chơi Dobble (luật chơi) khác nhau, nhưng đều có chung một nguyên tắc như nhau: tại mỗi vòng chơi, người chơi nào mà tìm được đầu tiên cái hình trùng nhau giữa hai quân bài nào đó, thì là người thắng vòng đó. Ví dụ, một trong các kiểu chơi là kiểu “cái giếng” (puits). Theo kiểu này, rút 1 quân bài đặt ngửa giữa bàn, còn 54 quân còn lại chia đều cho những người chơi (chia có dư thì bỏ đi phần dư).
Ở mỗi vòng, mỗi người phải rút ra 1 quân bài trong số các quân bài mình giữ, rồi xem xem nó có hình gì trùng với quân bài nằm giữa bàn. Ai mà tìm ra trước thì phải hô hình đó lên, và được đặt quân bài của mình vào giữa bàn lên trên quân bài cũ nằm ở giữa. (Đến vòng sau người này phải rút một quân bài mới từ tệp bài của mình, còn những người còn lại có thể giữ quân bài cũ). ai cho được hết số quân bài của mình vào chỗ giữa trước là thắng.

Đề bài.

Chúng ta giả sử rằng mọi bộ bài Dobble đều thỏa mãn các điều kiện phía trên: cứ 2 quân bài bất kỳ trong bộ bài thì có đúng 1 hình trùng nhau, và không có hình nào xuất hiện trên toàn bộ các quân bài.  Để đơn giản, ta sẽ gọi các hình của bộ bà là A, B, C, … Bài toán có 3 phần 1, 2, 3 các câu hỏi sau, xếp tho thứ tự từ dễ đến khó.

1) Trường hợp N=2 (tức là trên mỗi quân bài chỉ có 2 hình)
a) Hãy tạo một bộ bài với 3 quân bài khi N=2 (tức là nói xem các quân bài có các hình gì).
b) Tại sao không thể thêm một quân bài vào bộ bài cho thành bộ 4 quân bài?

2) Trường hợp N=3:
a) Giả sử A là một trong các hình của bộ bài. CMR có ít nhất 1 quân bài không có hình A, và nhiều nhất 3 quân bài có hình A.
b) Hãy làm 1 bộ bài mà mỗi hình của bộ bài xuất hiện trên đúng 2 quân bài.
c) Giả sử hình A xuất hiện trên 3 quân bài. CMR có ít nhất 7 hình khác nhau trong bộ bài. Hãy xây dựng 1 bộ bài với 7 quân bài mà có A xuất hiện trên 3 quân. Có thể thêm 1 quân vào bộ bài được không ?

3) Trường hợp N=8.
a) Hình A có thể xuất hiện trên nhiều nhất là bao nhiêu quân bài?
b) CMR bộ bài có không quá 57 quân bài.
c) Nếu bộ bài có đúng 57 quân, thì phải có ít nhất là bao nhiêu hình khác nhau trong đó ?

Ghi chú. Có thể làm bộ bài với Dobble với 57 quân với $N=8$. Nhưng bộ bài bán ở cửa hàng chỉ có 55 quân thay vì 57 quân, có lẽ tại vì con số 55 hấp dẫn khách hàng hơn là 57.

Lời giải

1) N=2 . Gọi quân bài với 2 hình A,B là [A,B]

1a) Một bộ bài với 3 quân là: [A,B], [A,C] và [B,C]

1b) Không thể có đến 4 quân bài được. Thật vậy, lấy 2 quân bài. hai quân đó có đúng 1 hình trùng nhau, ta gọi hình đó là A. Hình còn lại trên quân thứ nhất gọi là B, và trên quân thứ hai gọi là C. (B và C khác nhau, vì hai quân bài chỉ có chung đúng  một hình). Vì không có hình nào có trên tất cả các quân bài, nên có (ít nhất) một quân bài không có hình A. Ta coi đó là quân bài thứ ba. Quân bài thứ ba khi đó phải có hình B, vì phải có chung một hình với quân bài thứ nhất. Và nó cũng phải có hình C vì phải có trùng một hình với quân bài thứ hai. Như vậy quân bài thứ ba có cả B và C, và vì nó chỉ có đúng 2 hình, nên quân bài thứ ba chính là [B,C]. Bây giờ giả sử có thêm một quân bài thứ tư nào đó. Nếu quân bài thứ tư không có hình nào mới ngoài ba hình A,B,C, thì nó phải là [A,B], [A,C] hoặc [B,C], nhưng trong cả ba trường hợp này nó đều trung với một trong 3 quân bài đầu tiên tức là có hai hình chung với quân bài đó, mâu thuẫn với giả thiết của Dobble. Giả sử bây giờ quân bài thứ 4 có một hình mới, gọi nó là D. Hình còn lại của quân bài thứ 4 phải là A hoặc B, vì phải có chung một hình với quân bài [A,B]. Nếu hình đó là A, thì quân bài thứ tư là [D,A] chẳng có hình nào chung với quân bài [B,C]. còn nếu nó là B thì cũng tương tự như vậy, quân bài thứ tư là [D,B] chẳng có hình nào chung với quân bài [A,C]. Mọi trường hợp đều dẫn đến mâu thuẫn. Như vậy không thể có quân bài thứ tư.

 

2) N=3.

2a) Phải có ít nhất 1 quân bài không có hình A, vì nếu không tất cả các quân bài sẽ đều có hình A, trái ngược với gả thuyết ban đầu của Dobble. Có nhiều nhất là 3 quân bài có hình A, vì nếu không ta có thể giả sử là có 4 quân bài kiểu [A,B,C], [A,D,E], [A;F,G], [A,H,I] (từng đôi một có chung đúng một hình là hình A), trong đó B,C,D,E,F,G, là các hình khác nhau. Phải có thêm ít nhất một quân bài số 5 mà không chứa hình A (vì nếu không tất cả các quâ bài đều có chung hình A). Quân bài số 5 đó phải chứa một trong hai hình B & C (để có hình chung với quân bài thứ nhất), một trong hai hình D & F, một trong hai hình F & G,  và một trong hai hình I & J . Nhưng để có thể như vậy, thì nó phải chứa ít nhất 4 hình (một trong các hình là B hoặc C, v.v.), mâu thuẫn với giả thiết N=3.

2b) Một ví dụ bộ bài là: [A,B,C],  [A,D,E], [B,D,F], [C,E,F], với 6 hình khác nhau.  (Tổng số hình trên tất cả các quân bài là 4 nhân 3 bằng 12, và vì mỗi hình hiện đúng 2 lần nên có 12/2 = 6 hình khác nhau). Có thể suy luận vì sao một bộ bài với N=2 mà mỗi hình hiện trên đúng 2 quân bài phải  có đúng 4 quân bài. Thật vậy, gọi quân bài đầu là [A,B,C], thì trong các quân còn lại còn tổng cộng đúng 1 hình A, đúng 1 hình B, đúng 1 hình C, và mỗi quân còn lại chứa đúng 1 trong 3 hình này. Vì có đúng 3 hình nên cũng có đúng 3 quân còn lại.

2c) Giả sử hình A hiện trên đúng 3 quân bài. Các hình còn lại trên 3 quân bài đó phải khác nhau  (có thể gọi tên thành [A,B,C], [A,D,E], [A,F,G]), vì nếu không sẽ có 2 trong số 3 quân bài đó có 2 hình trùng nhau: A và thêm một hình nữa. Như vậy có ít nhất 7 hình khác nhau trên các quân bài: A,B,C,D,E,F,G. Một ví dụ bộ bài với 7 quân là:

[A,B,C], [A,D,E], [A,F,G], [B,D,F], [B,E,G] , [C,D,G], [C,E,F]

(Quân bài thứ 4 có dạng [B,D,F] vì nó phải có một hình từ quân thứ nhất, một hình từ quân thứ hai, một hình từ quân thứ 3, và các hình đó đều khác A. Quân thứ 5 tương tự như vậy, và giữa hai quân phải có đúng một hình chung, ta có thể giả sử hình đó là B. Tương tự với cá quân thứ 6 và thứ 7)

Chú ý là trong bộ trên, mỗi hình xuất hiện đúng 3 lần. Tổng số hình trên các quân bài là 3 nhân 7 bằng 21, ứng với 7 hình xuất hiện 3 lần, và 7 quân bài có 3 hình.

Khộng thể có đến 8 quân bài hoặc nhiều hơn, vì nếu có thêm quân bài thứ 8 thì nó cũng phải chứa các hình trên thôi (một trong hai hình B,C; một trong hai hình D,E, một trong hai hình FG, để còn có hình chung với 3 quân bài đầu) Nhưng mà như thế thì chỉ có 7 hình khác nhau, mà tổng số hình ít nhất là 8 lần 3 lớn hơn 7 lần 3, suy ra có hình xuất hiện ít nhất 4 lần, mâu thuẫn với câu a.

3) N=8 (là trường hợp thông dụng, được bán ở cửa hàng)

3a) Giả sử hình A là hình xuất hiện nhiều lần nhất trong số các hình trong bộ bài, và gọi số lần đó là k

Khi đó k quân bài chứa hình A có thể được ký hiệu như sau:

[A,B1,C1,D1,E1,F1,G1,H1], [A,B2,C2,D2,E2,F2,G2,H2], …, [A,Bk,Ck,Dk,Ek,Fk,Gk,Hk],

trong đó tất cả các hình B1,C1,D1,E1,F1,G1,H1, B2,C2,D2,E2,F2,G2,H2, …, Bk,Ck,Dk,Ek,Fk,Gk,Hk là khác nhau, vì hai quân bài bất kỳ trong số các quân bài trên chỉ chung nhau một hình là hình A.

Lấy quân bài thứ k+1. Nó không chứa hình A. Nên nó sẽ phải chứa một trong các hình B1,C1,D1,E1,F1,G1,H1 (để có chung hình với quân bài thứ nhất), rồi một trong các hình B2,C2,D2,E2,F2,G2,H2, v.v. rồi một trong các hình Bk,Ck,Dk,Ek,Fk,Gk,Hk. Như vậy nó đã phải chứa ít nhất k hình khác nhau, nằm trong k nhóm khác nhau đó. Vì nó chỉ có tổng cộng 8 hình, nên suy ra k nhỏ hơn hoặc bằng 8.

3b) Giả sử mỗi hình xuất hiện không quá k lần trong tập bài. lấy một quân bài đầu tiên [A,B,C,D,E,F,G,H]. Chia các quân bài còn là thành 8 nhóm a,b,c,d,e,f,g,h: Nhóm a là nhóm có chung hình A với quân bài thứ nhất, nhóm b là nhóm có chung hình B với quân bài thứ nhất, v.v. Quân bài nào cũng nằm trong đúng một trong các nhóm này, vì có chung đúng 1 hình với quân bài thứ nhất. Các quân bài ở nhóm a đều có hình A, và thêm quân bài thứ nhất có hình A nữa, mà tổng cộng chỉ có không quá k hình A, nên nhóm a không thể có quá k-1 quân bài. Các nhóm kia cũng vậy. Do đó tổng số quân bài ở các nhóm không quá 8 x (k-1). Thêm vào quân bài thứ nhất, ta có tổng số quân bài của bộ bài không quá 8 (k-1) + 1.  Vì ta biết răng k \leq 8 nên tổng số quân bài của bộ bài không vượt quá 8 (8-1) + 1 = 57.

 

Print Friendly

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.