Bài 51: (Nguồn: AMM)
Tìm tất cả các số nguyên dương $n$ sao cho $\binom{n}{k}$ là ước của$\binom{2n}{2k}$ với mọi số nguyên dương $k$ không vượt quá $n$.
Lời giải. Ta xét một bài toán phụ sau:
Bài toán phụ. Tìm tất cả số nguyên dương $n$ sao cho không tồn tại số nguyên tố $2<p<n$ thoả mãn $n=ph+r$ với $h \ge 2, 1 \le r \le \frac{p-1}{2}$.
Lời giải. Xét số $n-1$, để thoả mãn điều kiện thì hoặc $n-1$ là số nguyên tố hoặc $n-1=2^x$.
TH1. Nếu $n-1$ là số nguyên tố, tức $n$ chẵn. Xét $n-2$ thì ta suy ra để thoả mãn điều kiện thì $n-2=2^y \cdot 3^z$ với $y,z \ge 0$ là các số nguyên dương. Ta xét tiếp $n-3$ thì ta thấy hoặc $n-3$ là số nguyên tố hoặc $n-3=3^u \cdot 5^v$ với $u,v \ge 0$.
Với $n-3=3^u \cdot 5^v$ thì ta suy ra $2^y3^z-1=3^u5^v$. Như vậy hoặc $z=0$ hoặc $u=0$ hoặc cả hai bằng $0$.
+) Nếu $u=0$ thì $2^y3^z-1=5^v$ mà $5^v+1 \equiv 2 \pmod{4}$ nên $y=1$ dẫn đến $2 \cdot 3^z-1=5^v$ suy ra $v \equiv 1 \pmod{2}$ nếu $z \ge 1$, (còn nếu $z=0$ thì $v=0$, khi đó $n=4$). Do đó $\nu_3(5^v+1)=1+\nu_3(v)=z$ suy ra $v=3^{z-1} \cdot l$. Với $z \ge 2$ thì ta có $5^z+1=5^{3^{z-1} \cdot l}+1>2 \cdot 3^z$, mâu thuẫn. Vậy $z=1$ suy ra $v=1$. Khi đó $n=8$.
+) Nếu $z=0, u \ne 0$ thì $2^y-1=3^u5^v$. Nếu $v=0$ thì $2^y-1=3^u$, ta dễ tìm được $y=2,u=1$. Khi đó $n=6$. Nếu $v \ge 1$ thì $4 \mid y$ và $\nu_3(2^y-1)=1+\nu_3(y)=u, \; \nu_5(2^y-1)=\nu_5(y)+1=v$. Suy ra $y=3^{u-1} 5^{v-1} l$. Ta thấy rằng $2^y-1>3^u5^v$ với mọi $u,v \ge 1$ nên suy ra không tồn tại $n$.
Với $n-3$ là số nguyên tố. Xét $n-4$ thì để thoả mãn điều kiện bài toán, ta phải có $2^y3^z-2=n-4=2^m3^h5^p7^q$. Nếu $n-3,n-1 \ne 3$ là hai số nguyên tố thì $3 \mid n-5$. Do đó để thoả mãn điều kiện bài toán, ta phải có $2^y3^z-3=3^u5^v7^t$ với $z \ge 1$. Khi đó buộc $h=0$.
+) Nếu $y=1$ tức $3^z-1=2^{m-1}5^p7^q$ thì nhận thấy nếu $q \ge 1$ thì $6 \mid z$ suy ra $13 \mid 3^6-1 \mid 3^z-1$, mâu thuẫn. Vậy $q=0$ suy ra $3^z-1=2^{m-1}5^p$. Nhận thấy với $8 \mid z$ thì $41 \mid 3^8-1 \mid 3^z-1$, mâu thuẫn. Vậy $\nu_2(z) \le 2$. Dễ tìm được với $p=0$ thì $z=2,m=4$. Khi đó $n=20$. Với $p \ge 1$ thì ta suy ra $4 \| z$ hay $m=5$ và $\nu_5(3^z-1)=\nu_5(z)+1=p$ dẫn đến $z=5^{p-1} \cdot 4i$ suy ra $3^z-1>16\cdot 5^p$ với $p>1$. Với $p=1$ thì $3^z=81$ suy ra $z=4$. Ta tìm được $n=164$. Tuy nhiên $7 \mid n-3=164-3$ nên ta suy ra mâu thuẫn.
+) Nếu $y \ge 2$ thì $m=1$ ta có $2^{y-1}3^z-1=5^p7^q$ và ta cũng có $2^y3^{z-1}-1=3^{u-1}5^v7^t$. Ta suy ra $pv=0$ và $qt=0$. Với $q=0$ ta quay lại phương trình cũ $2^{y-1}3^z-1=5^p$ đã giải ở trên. Ta có $y=2,z=1$ hoặc $y=2,z=0$. Ta tìm được $n=14$ hoặc $n=5$. Với $q \ge 1$ thì nếu $p \ge 1$ thì $v=t=0$ suy ra $2^y3^{z-1}-1=3^{u-1}$ suy ra $z=1,y=2$ hay $n=14$.
TH2. Nếu $n-1=2^x$ thì ta suy ra $2^x-2=n-3=2^y3^z5^t$.
Nếu $x=1$ thì $n=3$. Nếu $x \ge 2$ thì $y=1$ suy ra $2^{x-1}-1=3^z5^y$. Nếu $z=0$ thì $2^{x-1}=5^y+1 \equiv 2 \pmod{4}$ suy ra $x=2$ dẫn đến $n=5$. Nếu $y=0$ thì $2^{x-1}-1=3^y$ suy ra $x=3$ dẫn đến $n=9$. Nếu $z,y \ge 1$ thì $4 \mid x-1$ và $\nu_3(x-1)=z-1, \nu_5(x-1)=y-1$ nên $x-1=3^{z-1}5^{y-1} \cdot 4i$. Nếu $z \ge 2$ thì $3 \mid x-1$ suy ra $7 \mid 2^{x-1}-1$, mâu thuẫn. Vậy $z=1$. Nếu $y \ge 2$ thì $5 \mid x-1$ suy ra $31=2^5-1 \mid 2^{x-1}-1$, mâu thuẫn. Vậy $y=z=1$ suy ra $x=5$. Ta tìm được $n=33$.
Các số $n$ tìm được là $n \in \{ 3,4,5,6,8,9,14,20,33 \}$. $\square$
_________________________________________________________________________
Quay lại bài toán, ta có
$$\begin{aligned} \binom{2n}{2k} & = \frac{2^{n}n!(3 \cdot 5 \cdots (2n-1))}{ \left [ 2^k k! (3 \cdot 5 \cdots (2k-1)) \right ] \cdot \left [ 2^{n-k}(n-k)! (3 \cdot 5 \cdots (2n-2k-1)) \right ] }, \\ & = \binom nk \cdot \frac{3 \cdot 5 \cdots (2n-1)}{(3 \cdot 5 \cdot (2k-1)) \cdot (3 \cdot 5 \cdots (2n-2k-1)) } = \binom nk \cdot \frac{A}{B}. \end{aligned}$$
Ta xét các số $n \not\in \{ 3,4,5,8,9,14,20,33 \}$. Khi đó luôn tồn tại số nguyên tố $p<n$ sao cho $n=hp+r$ với $1 \le r \le \frac{p-1}{2}$ và $h \ge 2$. Ta suy ra $2hp+2 \le 2n=2hp+2r<2hp+p+1$. Ta chọn $2k-1=(2h-1)p$ thì khi đó $2n-2k-1=2n-2-(2h-1)p \ge p$. Do đó $$\nu_p(B)= \nu_p(3 \cdot 5 \cdots (2h-1)p)+\nu_p(3 \cdot 5 \cdots (2n-2-(2h-1)p)) \ge \nu_p(3 \cdot 5 \cdots (2h-1)p)+1.$$
Mặt khác, do $1 \le r \le \frac{p-1}{2}$ nên các số lẻ từ $(2h-1)p+2$ đến $2n-1<(2h-1)p+2p$ sẽ không có số nào chia hết cho $p$. Ta suy ra $\nu_p(A)= \nu_p(3 \cdot 5 \cdots (2h-1)p)< \nu_p(B)$. Vậy lúc đó $\binom nk \nmid \binom{2n}{2k}$.
Xét các số $n \in \{ 3,4,5,8,9,14,20,33 \}$. Với $n=3,5$ thì thoả mãn điều kiện đề bài.
Với $n=4$ thì chọn $2k-1=3$ ta thấy $\nu_3(B)>\nu_3(A)$, mâu thuẫn.
Với $n=6$ thì chọn $2k-1=5$ ta thấy $\nu_5(B)>\nu_5(A)$, mâu thuẫn.
Với $n=8,9$ thì chọn $2k-1=7$ ta thấy $\nu_7(B)>\nu_7(A)$, mâu thuẫn.
Với $n=14$ chọn $2k-1=13$ ta thấy $\nu_{13}(B)>\nu_{13}(A)$, mâu thuẫn.
Với $n=20$ chọn $2k-1=17$ ta thấy $\nu_{17}(B)>\nu_{17}(A)$, mâu thuẫn.
Với $n=33$ chọn $2k-1=23$ ta thấy $\nu_{23}(B)>\nu_{23}(A)$, mâu thuẫn.
Hiển nhiên $n=1,2$ cũng thoả mãn.
Vậy $n \in \{ 1,2,3,5 \}$ là đáp án bài toán. $\blacksquare$
Bài 52. [AoPS] Cho số $n \in \mathbb{N}, n \ge 4$. $M$ là một tập con của $\{ 1,2 \cdots , 2n-1 \}$ có $n$ phần tử. Chứng minh rằng, tồn tại một tập con khác rỗng của $M$ sao cho tổng các phần tử trong tập đó chia hết cho $2n$.
Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 10-06-2016 - 11:00