Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Lê Phúc Lữ – Phạm Khánh Vĩnh

(Bài viết trích từ Tập san Star Education – Số 5)

Bài 1. (JBMO 1998)
Hỏi có tồn tại hay không $16$ số có ba chữ số tạo thành từ ba chữ số phân biệt cho trước mà không có hai số nào có cùng số dư khi chia cho $16$?

Lời giải

Câu trả lời là phủ định.
Giả sử tồn tại các số thỏa mãn đề bài thì vì chúng có số dư đôi một khác nhau nên sẽ có đầy đủ các số dư $0,1,2,3,\ldots ,15$. Điều này có nghĩa là trong đó, có $8$ số chẵn và $8$ số lẻ. Suy ra, ba chữ số $a,b,c$ để tạo thành các số đã cho không thể có cùng tính chẵn lẻ. Ta có hai trường hợp:

  • Trong các số $a,b,c$, có hai số chẵn là $a,b$ và số $c$ lẻ. Ta có tất cả $9$ số lẻ tạo thành từ các chữ số này là:
    $aac,abc,acc,bac,bbc,bcc,cac,cbc,ccc$.
    Gọi ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{9}}$ là số có hai chữ số tạo thành bằng cách xóa đi chữ số cuối từ dãy trên.
    Rõ ràng số $\overline{{{a}_{i}}k}$ và $\overline{{{a}_{j}}k}$ với $i\ne j$ khác số dư với nhau theo modulo $16$ nếu như hiệu của chúng không chia hết cho $16$, suy ra ${{a}_{i}}-{{a}_{j}}$ không chia hết cho $8.$ Tuy nhiên, ta lại có đến $9$ số nên điều này không thể xảy theo nguyên lý chuồng bồ câu.
  • Trong các số $a,b,c$, có hai số lẻ là $a,b$ và số $c$ chẵn: cũng dẫn đến mâu thuẫn tương tự.

Vậy không tồn tại các số thỏa mãn đề bài.

Bài 2: (JBMO 2000)

Trong một giải thi đấu tennis, số lượng nam gấp đôi số nữ. Mỗi cặp vận động viên thi đấu với nhau đúng một lần và không có trận hòa, chỉ có thắng – thua. Tỷ số giữa trận thắng của nữ và của nam là $\frac{7}{5}$. Hỏi có bao nhiêu vận động viên trong giải thi đấu?

 

Lời giải

Gọi số nam là $2n$, số nữ là $n$ và tổng số vận động viên là $3n.$ Tổng số trận đấu là

$\frac{3n(3n-1)}{2}.$ \medskip

 

Theo giả thiết thì số trận thắng bởi nam là $$\frac{5}{12}\cdot \frac{3n(3n-1)}{2}=\frac{5n(3n-1)}{8}.$$

Số trận đấu giữa các nam là $\frac{2n(2n-1)}{2}=n(2n-1)$ và rõ ràng số trận này không vượt quá số trận thắng của các nam.

Suy ra $$\frac{5n(3n-1)}{8}\ge n(2n-1)\Leftrightarrow n\le 3.$$ Mặt khác, $5n(3n-1)$ phải chia hết cho $8$ nên $n=3.$ Do đó, số vận động viên của giải đấu là $9.$

Bài 3: (JBMO 2006)

Xét bảng ô vuông kích thước $2n\times 2n$ với $n$ nguyên dương. Người ta xóa đi một số ô của bảng theo quy tắc sau đây:

 

  •  Nếu $1\le i\le n$ thì ở dòng thứ $i$, xóa $2(i-1)$ ô ở giữa.
  •  Nếu $n+1\le i\le 2n$ thì ở dòng thứ $i,$ xóa đi $2(2n-i)$ ô ở giữa.

Hỏi có thể phủ được bảng bởi tối đa bao nhiêu hình chữ nhật kích thước $2\times 1$ và $1\times 2$ (không nhất thiết phải phủ kín toàn bộ) sao cho không có hai hình chữ nhật nào chồng lên nhau?

 

Lời giải

Với mọi bảng kích thước $2n\times 2n,$ tổng số ô bị xóa đi là $$2\times 2\times (1+2+3+\cdots +n-1)=2n(n-1).$$

Bảng sẽ còn lại ${{(2n)}^{2}}-2n(n-1)=2n(n+1)$ ô, tức là phủ được tối đa $n(n+1)$ ô vuông.

Không có mô tả.

 

Với $n=1,2,3,4,$ ta có thể kiểm tra trực tiếp được rằng kết quả lần lượt sẽ là $2,6,12,20$ bởi khi đó ta có thể phủ kín toàn bộ bảng. Còn với $n\ge 4$, ta xét hai trường hợp:

 

  • Nếu $n$ lẻ, khi đó ta chia bảng $2n\times 2n$ đã cho thành $4$ hình vuông nhỏ thì rõ ràng, mỗi hình sẽ có $\frac{n(n+1)}{2}$ ô còn trống. Tiếp theo, ta tô màu theo dạng bàn cờ cho bảng này (ô ở góc thì tô đen), ta sẽ có tất cả $\frac{{{(n+1)}^{2}}}{4}$ ô đen và $\frac{{{n}^{2}}-1}{4}$ ô trắng. Rõ ràng mỗi hình chữ nhật khi đặt lên bảng sẽ chứa một ô đen và một ô trắng nên số cặp ô trắng – đen tối đa trong hình vuông con là $\frac{{{n}^{2}}-1}{4}$, và tương ứng sẽ có tối đa $$4\cdot \frac{{{n}^{2}}-1}{4}={{n}^{2}}-1$$ hình chữ nhật $1\times 2,2\times 1$ phủ được trên bảng.

Ngoài ra, giữa các hình vuông con cạnh nhau, ta còn có hai ô màu đen cạnh nhau nên ta có thể lát thêm vào đó tổng cộng $4$ hình chữ nhật nữa, tổng cộng là ${{n}^{2}}-1+4={{n}^{2}}+3$.

  •  Nếu $n$ chẵn, bằng cách tương tự trên, ta phủ được hình bởi tối đa ${{n}^{2}}+4$ ô.

Tóm lại,

  •  Với $n=1,2,3,4$, đáp số lần lượt là $2,6,12,20.$
  •  Với $n>4$ và $n$ lẻ thì đáp số là ${{n}^{2}}+3.$
  •  Với $n>4$ và $n$ chẵn thì đáp số là ${{n}^{2}}+4.$

Bài 4: (JBMO 2008)

Một bảng $4\times 4$ được chia thành $16$ ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau $n$ thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của $n.$

 

Lời giải

Ta thấy mỗi lần đổi màu không quá $5$ ô nên số lần đổi màu phải ít nhất là $4.$Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Không có mô tả.

Mặt khác, với $n$ chẵn lớn hơn $4$, ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp $n=4.$ \medskip

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Không có mô tả.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi ($1$ hoặc $3$) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư $2$ modulo $4.$

Ban đầu chênh lệch đó là $10$ và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là $-10$; tức là thay đổi $-20$, chia hết cho $4$. Điều này không thể xảy ra nên $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n\ge 4.$

Bài 5: (JBMO 2008)

Một bảng $4\times 4$ được chia thành $16$ ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau $n$ thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của $n.$

 

Lời giải

Ta thấy mỗi lần đổi màu không quá $5$ ô nên số lần đổi màu phải ít nhất là $4.$Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Mặt khác, với $n$ chẵn lớn hơn $4$, ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp $n=4.$ \medskip

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi ($1$ hoặc $3$) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư $2$ modulo $4.$

Ban đầu chênh lệch đó là $10$ và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là $-10$; tức là thay đổi $-20$, chia hết cho $4$. Điều này không thể xảy ra nên $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n\ge 4.$

Bài 6:

(JBMO 2010)

Một hình chữ nhật $9\times 7$ được lát bởi hai loại gạch như hình bên dưới: chữ $L$ và hình vuông.

 

Không có mô tả.

 

Tìm tất cả các giá trị có thể có của số lượng các viên gạch hình vuông đã được dùng.

 

Lời giải

Câu trả lời là $0$ hoặc $3.$

Gọi $x$ là số viên gạch chữ $L$ và $y$ là số viên gạch hình vuông $2\times 2.$ Đánh dấu chéo $20$ hình vuông của hình chữ nhật như sơ đồ bên dưới.

Không có mô tả.

Rõ ràng mỗi viên gạch sẽ chứa không quá một dấu chéo. Suy ra $x+y\ge 20.$

Ngoài ra ta cũng có $3x+4y=63.$

Từ đó suy ra $y\le 3$ và $y$ chia hết cho $3$, dựa theo điều kiện thứ hai.

Do đó $y=0$ hoặc $y=3.$ Dưới đây là các cách lát thỏa mãn điều kiện đó.

Không có mô tả.

Bài 7: (JBMO 2013)

Cho $n$ là một số nguyên dương. Có hai người chơi là Alice và Bob chơi một trò chơi như sau:

 

  •  Alice chọn $n$ số thực, không nhất thiết phân biệt.
  •  Alice viết tất cả các tổng theo cặp của tất cả các số lên giấy và đưa nó cho Bob (rõ ràng có tất cả $\frac{n(n-1)}{2}$ cặp và không nhất thiết phân biệt).
  •  Bob sẽ thắng nếu như có thể tìm lại được $n$ số ban đầu được chọn bởi Alice.

Hỏi Bob có thể có cách chắc chắn thắng hay không với

 

  •  $n=5?$
  •  $n=6?$
  •  $n=8?$

 

 

Lời giải

1) Câu trả lời là khẳng định.

 

Giả sử các số Alice đã chọn là $a\le b\le c\le d\le e$. Rõ ràng mỗi số xuất hiện trong các tổng đúng $4$ lần nên bằng cách cộng tất cả $10$ tổng và chia hết quả cho $4$, Bod sẽ thu được

$a+b+c+d+e.$

Trừ đi tổng lớn nhất và nhỏ nhất, Bob sẽ thu được số lớn thứ ba là $c.$ Tiếp tục trừ $c$ vào tổng lớn thứ nhì, chính là $c+e$ thì Bob thu được $e.$ Trừ $e$ vào tổng lớn nhất, Bob thu được $d$. Bằng cách tương tự, Bob sẽ tìm ra được các giá trị $a,b.$ \medskip

 

2) Câu trả lời là khẳng định. Giả sử các số Alice đã chọn là $a\le b\le c\le d\le e\le f.$ Tương tự trên, ta cũng tính được tổng $S$ các số của bộ. Trừ $S$ cho tổng lớn nhất và nhỏ nhất, ta thu được tổng $c+d.$ \medskip

 

Trừ $S$ cho tổng lớn nhì và tổng nhỏ nhất, ta được $c+e.$ Trừ $S$ cho tổng lớn nhất và tổng nhỏ nhì, ta được $b+d.$

Từ đây suy ra $a+c=S-(b+d)-(e+f)$, trong đó ta biết $e+f$ vì đó là tổng lớn nhất.

Lúc bấy giờ, Bob đã tìm được ba tổng $a+b,a+c,b+c$ nên sẽ tính được $T=a+b+c$ và dễ dàng tìm được $a,b,c.$ Tương tự, Bob có thể tìm được $d,e,f.$ \medskip

 

3) Câu trả lời là phủ định.

Ta thấy rằng có hai bộ tám số là $1,5,7,9,12,14,16,20$ và $2,4,6,10,11,15,17,19$ đều cho cùng $28$ tổng theo đôi một giống nhau nên chắc chắn rằng Bob không thể biết được bộ mà Alice đã chọn.

 

Bài 8: (JBMO 2014)

Với mỗi số nguyên dương $n$, hai người $A,B$ chơi một trò chơi như sau: Cho một đống có $s$ viên sỏi và hai người chơi thay phiên nhau chơi, $A$ đi trước. Ở mỗi lượt, người chơi được bốc hoặc $1$ viên sỏi, hoặc một số $p$ nguyên tố các viên sỏi, hoặc một bội của $n$ các viên sỏi. Người bốc được viên cuối cùng là chiến thắng. Giả sử hai người đều chơi với chiến thuật tối ưu, hỏi có bao nhiêu giá trị $s$ để người $B$ có chiến thuật thắng?

 

Lời giải

Ta gọi các giá trị $s$ để cho người $A$ có chiến thuật thắng là vị trí thắng và các vị trí còn lại là vị trí thua. Ta cần tìm số lượng vị trí thua.

Giả sử có $k$ vị trí thua thuộc tập hợp $$X=\{{{s}_{1}},{{s}_{2}},{{s}_{3}},\ldots ,{{s}_{k}}\}.$$

Trước hết, ta thấy rằng mỗi bội của $n$ là vị trí thắng (vì người $A$ có thể lấy tất cả các viên sỏi ở ngay lần đi đầu tiên). Khi đó, nếu có ${{s}_{i}}\equiv {{s}_{j}}(\bmod n)$ và ${{s}_{i}}>{{s}_{j}}$ thì ở lượt đi đầu tiên, $A$ bốc ${{s}_{i}}-{{s}_{j}}$ viên sỏi (vì số này chia hết cho $n$). Nhưng lúc đó, còn lại ${{s}_{j}}$ viên sỏi và đây là vị trí thua của $B$ nên sẽ là vị trí thắng của $A$, mâu thuẫn.

Do đó, tất cả các số trong $X$ đều không đồng dư với nhau theo modulo $n$ hay $k=\left| X \right|\le n-1.$ \medskip

 

Ta sẽ chứng minh rằng $k=n-1.$ Thật vậy,

Để có được điều đó, ta sẽ chỉ ra rằng ở mỗi lớp thặng dư khác $0$ của $n$, luôn có một vị trí thua bằng phản chứng. Giả sử rằng tồn tại $r\in \{1,2,3,\ldots ,n-1\}$ sao cho $mn+r$ là vị trí thắng với mỗi số nguyên dương $m.$ Gọi $u$ là vị trị thua lớn nhất (nếu $k>0$) hoặc $0$ (nếu $k=0$).

Đặt $s$ là bội chung nhỏ nhất của tất cả các số nguyên dương từ $2$ đến $u+n+1.$ Khi đó, tất cả các số $s+2,s+3,\ldots ,s+u+n+1$ đều là hợp số. \medskip

 

Xét số nguyên dương ${m}’$ thỏa mãn

$s+u+2\le {m}’n+r\le s+u+n+1$.

Để ${m}’n+r$ là vị trí thắng thì phải có số tự nhiên $p$ là $1$, là số nguyên tố hoặc là bội của $n$ sao cho hiệu ${m}’n+r-p$ sẽ là vị trí thua, là $0$ hoặc là một số nhỏ hơn hoặc bằng $u.$ Chú ý rằng

$$s+2\le {m}’n+r-u\le p\le {m}’n+r\le s+u+n+1$$

nên $p$ phải là hợp số, chứng tỏ $p$ chỉ có thể là bội của $n$ (theo giả thiết của đề bài). \medskip

 

Đặt $p=qn$ thì ${m}’n+r-q=({m}’-q)n+r$ cũng sẽ là một vị trí thắng khác; tuy nhiên, theo nguyên lý trò chơi thì không thể đi từ vị trí thằng này đến vị trí thắng khác được. Điều mâu thuẫn này cho thấy không thể xảy ra trường hợp toàn bộ các số dạng $mn+r$ là vị trí thắng. \medskip

 

Từ đây ta suy ra rằng có ít nhất $n-1$ vị trí thua nên từ các điều trên, ta thấy có đúng $n-1$ vị trí thua hay có $n-1$ vị trí mà người $B$ có chiến lược để thắng.

Bài 9: (JBMO 2015)

Một khối chữ $L$ bao gồm ba khối vuông ghép như một trong các hình bên dưới:

 

 

Cho trước một bảng $5\times 5$ bao gồm $25$ ô vuông đơn vị, một số nguyên dương $k\le 25$ và một số lượng tùy ý các khối chữ $L$ nêu trên. Hai người chơi $A,B$ cùng tham gia một trò chơi như sau: bắt đầu bởi $A$, hai người sẽ lần lượt đánh dấu các ô vuông của bảng cho đến khi nào tổng số ô được đánh dấu bởi họ là $k.$ \medskip

 

Ta gọi một cách đặt các khối chữ $L$ trên các ô vuông đơn vị còn lại chưa được đánh dấu là tốt nếu như nó không bị chồng lên nhau, đồng thời mỗi khối đặt lên đúng ba ô vuông như một trong các hình ở trên. $B$ sẽ thắng nếu như với mọi cách đặt tốt ở trên, luôn luôn tồn tại ít nhất ba ô vuông đơn vị chưa được đánh dấu trên bảng. \medskip

 

Xác định giá trị $k$ nhỏ nhất (nếu có tồn tại) để $B$ có chiến lược thắng.

 

Lời giải

Ta sẽ chứng minh rằng $A$ sẽ thắng nếu $k=1,2,3$ và $B$ thắng nếu $k=4.$ Suy ra giá trị nhỏ nhất của $k$ là $4.$ \medskip

 

1) Nếu $k=1$ thì người chơi $A$ sẽ đánh dấu ô ở góc trên bên trái và đặt các khối như bên dưới

 

Không có mô tả.

 

Khi đó, rõ ràng $A$ thắng. \medskip

 

2) Nếu $k=2$ thì vẫn tương tự trên, $A$ đánh dấu vào ô ở góc trên bên trái. Khi đó, cho dù $B$ đánh dấu ô nào đi nữa thì $A$ cũng sẽ có cách đặt tương tự như trên, thiếu đi nhiều nhất là $2$ ô thuộc cùng khối vuông chữ $L$ với ô mà $B$ chọn. Điều này chứng tỏ $A$ vẫn thắng. \medskip

 

3) Nếu $k=3$ thì cũng tương tự, ở lượt sau, $A$ đánh dấu vào ô cùng khối chữ $L$ với ô mà $B$ đã đánh dấu. Khi đó, $A$ vẫn thắng. \medskip

 

4) Với $k=4$, ta sẽ chứng minh rằng $B$ sẽ luôn có chiến lược thắng cho dù $A$ đi thế nào đi nữa. Rõ ràng còn lại $21$ ô nên $A$ phải chọn cách đánh dấu sao cho có thể đặt được toàn bộ $7$ khối vuông chữ $L$ (vì nếu không thì sẽ còn lại ít nhất $3$ ô chưa được đặt). \medskip

 

Giả sử trong lượt đầu tiên, $A$ không chọn ô nào trong hàng cuối (vì nếu có thì ta xoay ngược bảng lại và lập luận tiếp một cách tương tự). Khi đó, $B$ sẽ chọn ô số $1$ như bên dưới.

Không có mô tả.

 

  •  Nếu trong lượt tiếp theo, $A$ không chọn ô nào trong các ô $2,3,4$ thì $B$ chọn ô số $3.$ Khi đó, rõ ràng ô số $2$ sẽ không thể đặt lên bởi bất cứ khối chữ $L$ nào và $B$ chiến thắng.
  •  Nếu trong lượt tiếp theo, $A$ chọn ô số $2$ thì $B$ chọn ô số $5$, dẫn đến ô số $3$ không thể đặt lên bởi khối $L$ nào.
  •  Nếu trong lượt tiếp theo, $A$ chọn một trong hai ô $3$ hoặc $4$ thì $B$ chọn ô còn lại, kết quả tương tự trên, ô số $2$ cũng sẽ không thể tiếp cận.

Vậy nói tóm lại, $k=4$ là giá trị nhỏ nhất cần phải tìm.

Bài 10: (JBMO 2016)

Một bảng kích thước $5\times 5$ được gọi là “tốt” nếu như mỗi ô của nó có chứa một đúng bốn giá trị phân biệt, và mỗi giá trị xuất hiện đúng một lần trong tất cả các bảng con $2\times 2$ của bảng đã cho. Tổng tất cả các số có trên bảng được gọi là “giá” của bảng. Với mỗi bộ bốn số thực, ta có thể xây dựng tất cả các bảng tốt và tính giá của nó. Tính số giá phân biệt lớn nhất có thể có.

 

Lời giải

Ta sẽ chứng minh rằng số giá phân biệt lớn nhất là $60.$ Ta có nhận xét sau: \medskip

 

Nhận xét:  Trong mỗi bảng tốt, mỗi hàng chứa đúng hai số trong các số hoặc mỗi cột chứa đúng hai số trong các số. \medskip

 

Thật vậy, ta thấy mỗi hàng của bảng đều chứa ít nhất hai số (vì nếu chứa toàn bộ là một số thì mâu thuẫn với giả thiết). Khi đó, nếu toàn bộ các hàng đều chứa hai số thì nhận xét đúng. \medskip

 

Giả sử ngược lại là có hàng $R$ chứa ít nhất ba số trong bốn số của bảng là $x,y,z,t$. Khi đó, các số đó phải có nằm ở vị trí liên tiếp nào đó trên hàng, giả sử là $x,y,z$ liên tiếp. Theo giả thiết thì trong mỗi bảng $2\times 2$, ta đều có đủ bốn giá trị nên trong hàng phía trên và phía dưới của $R$ phải chứa $z,t,x$ theo đúng thứ tự đó, và tương tự là $x,y,z$. Ta có bảng như bên dưới

 

* & x & y & z & * \\

* & z & t & x & * \\

* & x & y & z & * \\

* & z & t & x & * \\

* & x & y & z & * \\

 

Điền thêm các ô còn lại, dễ thấy rằng các cột đều chứa đúng hai số. Nhận xét được chứng minh. \medskip

 

Không mất tính tổng quát, ta có thể giả sử mỗi hàng của bảng đều có đúng hai số (nếu không thì có thể xoay bảng lại). Nếu không xét hàng đầu tiên và cột đầu tiên, ta sẽ có bảng $4\times 4$ mà trong đó, mỗi số trong $x,y,z,t$ đều xuất hiện $4$ lần nên tổng các số trong bảng này là $4(x+y+z+t).$

Do đó, ta chỉ cần tính xem có bao nhiêu cách khác nhau để đặt các số lên hàng đầu tiên ${{R}_{1}}$ và cột đầu tiên ${{C}_{1}}.$ Gọi $a,b,c,d$ là số lần xuất hiện của các số $x,y,z,t$ thì khi đó, tổng tất cả các số của bảng sẽ là

$$4(x+y+z+t)+xa+yb+zc+td.$$

Nếu hàng $1-3-5$ chứa các số $x,y$ với $x$ ở vị trí đầu tiên của hàng $1$ thì các hàng $2-4$ sẽ chứa các số $z,t$ (theo giả sử ở trên). Khi đó, ta có

$a+b=7$ và $a\ge 3,b\ge 2$,

$c+d=2$ và $c\ge d.$ \medskip

 

Khi đó $(a,b)=(5,2),(4,3)$ tương ứng với $(c,d)=(2,0),(1,1).$ Suy ra $(a,b,c,d)$ sẽ nhận các bộ là $$(5,2,2,0),(5,2,1,1),(4,3,2,0),(4,3,1,1).$$

Tổng số hoán vị của các bộ là $$\frac{4!}{2!}+\frac{4!}{2!}+4!+\frac{4!}{2!}=60.$$

Bằng cách chọn $x={{10}^{3}},y={{10}^{2}},z=10,t=1$ thì dễ thấy rằng các tổng tương ứng với mỗi hoán vị của bộ số trên đều phân biệt, nghĩa là giá của các bảng đều phân biệt. Vậy số lượng giá tối đa là $60.$

Dưới đây là một số bài toán để bạn đọc tự rèn luyện thêm:

Bài 11. (JBMO 2019) Cho bảng ô vuông $5\times 100$ được chia thành $500$ ô vuông con đơn vị, trong đó có $n$ được tô đen và còn lại tô trắng. Hai ô vuông kề nhau nếu chúng có cạnh chung. Biết rằng mỗi ô vuông đơn vị sẽ có tối đa hai ô vuông đen kề với nó. Tìm giá trị lớn nhất của $n.$

Bài 12. (JBMO 2020) Alice và Bob chơi một trò chơi như sau: Alice chọn một tập hợp $A={1,2,\ldots ,n}$ với $n\ge 2.$ Sau đó, bắt đầu bằng Bob, họ sẽ thay phiên chọn một số trong tập $A$ sao cho: đầu tiên Bob chọn bất kỳ số nào, sau đó, các số được chọn phải khác các số đã chọn và hơn kém đúng $1$ đơn vị so với số nào đó đã chọn. Trò chơi kết thúc khi tất cả các số trong $A$ đã được chọn. Alice thắng nếu tổng các số bạn ấy chọn được là hợp số. Ngược lại thì Bob thắng. Hỏi ai là người có chiến lược thắng?

Leave a Reply

Your email address will not be published. Required fields are marked *