Combinatorics

Bài toán : Gỉa sử rằng trong một nhóm $n$ người thỏa điều kiện cứ $n-2$ người bất kì thì có $3^k$ số cặp người quen nhau. Tìm $n$.

Lời giải :

Theo đề bài cứ một nhóm gồm $n-2$ người thì có $3^k$ số cặp quen nhau, mà trong $n$ người, số nhóm $n-2$ người là $C_n^{n-2}$. Do đó số cặp quen nhau trong $n$ người (tính cả các cặp trùng nhau trong các nhóm) là $C_n^{n-2}.3^k$.

Xét hai người $A,B$ quen nhau. Trong $n-2$ người còn lại ta chọn ra $n-4$ người để tạo thành một nhóm $n-2$ người với $A,B$. Số cách chọn như vậy là $C_{n-2}^{n-4}$, tức là hai người quen nhau này có mặt trong $C_{n-2}^{n-4}$ nhóm.

Như vậy số cặp người quen nhau trong $n$ người là $m=\frac{3^k.C_n^{n-2}}{C_{n-2}^{n-4}}$

Ta có :

$m$$=\frac{3^k.C_n^{n-2}}{C_{n-2}^{n-4}}\in {\mathbb{Z}}^{+}$$\Rightarrow \frac{3^k.\frac{n!}{2!(n-2)!}}{\frac{(n-2)!}{2!(n-4)!}}$$=\frac{3^k.n(n-1)}{(n-2)(n-3)}\in {\mathbb{Z}}^{+}$

Xét $n\in \left\{1,2,3,4\right\}$ thì nhận $n=4$

Nếu $n-3$ chẵn, đặt $n-3=2t,t\in {\mathbb{N}}^{\ast }$

Ta được $m=\frac{3^k.(2t+3)(2t+2)}{(2t+1).2t}=\frac{3^k(2t+3)(t+1)}{(2t+1).t}\in {\mathbb{Z}}^{+}$

Dễ dàng thấy rằng $gcd(2t+3,2t+1)=gcd(2t+1,t+1)=1$ nên $2t+1\mid 3^k\Rightarrow 2t+1=3^s,(s<k,s\in {\mathbb{N}}^{\ast })$

Từ đó suy ra $t=\frac{3^s-1}{2}$. Lúc này :

$m$$=\frac{3^k.(3^s+2).(\frac{3^s-1}{2}+1)}{3^s.\frac{3^s-1}{2}}$$=\frac{3^{k-s}.(3^s+2)(3^s+1)}{3^s-1}\in {\mathbb{Z}}^{+}$

Rõ ràng $gcd(3^{k-s},3^s-1)=gcd(3^s+2,3^s-1)=1$ nên$\frac{3^s+1}{3^s-1}\in {\mathbb{Z}}^{+}$ mà $gcd(3^s-1,3^s+1)=2\Rightarrow 3^s-1=2\Rightarrow s=1\Rightarrow n=5$

Nếu $n-3$ lẻ, đặt $n-3=2t+1,\left(t\in {\mathbb{N}}^{\ast }\right)$

Ta được $m=\frac{3^k(2t+4)(2t+3)}{(2t+2)(2t+1)}=\frac{3^k(t+2)(2t+3)}{(t+1)(2t+1)}\in {\mathbb{Z}}^{+}$

Dễ dàng thấy rằng $gcd(t+1,t+2)=gcd(t+1,2t+3)=1$ nên phải có $t+1\mid 3^k\Rightarrow t=3^s-1,\left(s=k,s\in {\mathbb{N}}^{\ast }\right)$

Lúc này :

$m$$=\frac{3^k.(3^s+1)(2.3^s+1)}{3^s(2.3^s-1)}$$=\frac{3^{k-s}.(3^s+1)(2.3^s+1)}{2.3^s-1}\in {\mathbb{Z}}^{+}$

Dễ thấy $gcd(2.3^s-1,3^s+1)=gcd(2.3^s+1,2.3^s-1)=gcd(3^{k-1},2.3^s-1)=1$ nên trường hợp này bị loại.

 Kết luận : $\boxed{n\in \left\{4,5\right\}}$