Chủ đề này có 2 trả lời

[supermember]

Bài Toán: Tính số bộ số $(x_1;x_2;...; x_n)$ thỏa mãn: $ x_k \in \{0;1;2\} $ với mọi $ k = \overline{1;n}$ và: $ \prod_{k=1}^{n} x_k - \sum_{k=1}^{n} x_k$ là số chia hết cho $3$

Bài viết đã được chỉnh sửa nội dung bởi supermember: 21-09-2021 - 11:11

[supermember]

Bài này supermember sẽ trình bày ý tưởng đã, thực sự thì nếu trình bày full lời giải dựa trên ý tưởng này thì rất dài nên hi vọng có người nào đó có thể đưa ra cách làm tốt hơn.

 

Trước tiên, thay vì trực tiếp đếm số bộ số cần tìm, ta sẽ lần lượt đếm những bộ số đơn giản hơn:

 

Bước 1: Ta đi tính số bộ số $ (x_1; x_2; ...; x_n)$ với $ x_k \in \{1;2 \}$ với mọi $k$ chạy từ $1$ đến $n$ sao cho : $ 3 | x_1 + x_2 + \cdots + x_n$

Giả sử trong bộ $n$ số này có $k$ số $1$ và $l$ số $2$ thì ta có:

 

$ 0 \leq k; l \leq n ; \  k + l =n ; \ 3 | k+ 2l$

Ta xét các trường hợp sau:

 

Trường hợp $1$: $ n \equiv 0 \pmod 3 $

Khi đó, dễ thấy chỉ có thể xảy ra trường hợp: $ k \equiv l \equiv 0 \pmod 3$

 

Nên từ đây dễ thấy là $k$ sẽ có thể nhận các các giá trị: $ 0; 3 ; …; n$

 

Do đó, theo quy tắc cộng, thì số cách chọn ra bộ số trong trường hợp này là:

 

$ \binom{n}{0} + \binom{n}{3} + \cdots + \binom{n}{n}$

 

Trường hợp $2$: $ n \equiv 1 \pmod 3 $

 

Khi đó, dễ thấy chỉ có thể xảy ra trường hợp: $ k \equiv l \equiv 2 \pmod 3$

 

số cách chọn ra bộ số trong trường hợp này là:

 

$ \binom{n}{2} + \binom{n}{5} + \cdots + \binom{n}{n -2}$

 

Trường hợp $3$: $ n \equiv 2 \pmod 3 $

 

Khi đó, dễ thấy chỉ có thể xảy ra trường hợp: $ k \equiv l \equiv 1 \pmod 3$

 

số cách chọn ra bộ số trong trường hợp này là:

 

$ \binom{n}{1} + \binom{n}{4} + \cdots + \binom{n}{n -1}$

 

Mặt khác, theo chuyên đề đẳng thức tổ hợp của diễn đàn, thì ta có $3$ đẳng thức sau:

 

$ \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \binom{n}{9} + \cdots = \frac{1}{3} \cdot \left( 2^n + 2 \cos \frac{ \pi n}{3} \right)$   

$ \binom{n}{1} + \binom{n}{4} + \binom{n}{7} + \binom{n}{10} + \cdots = \frac{1}{3} \cdot \left( 2^n + 2 \cos \frac{n-2}{3} \pi \right)$   

$ \binom{n}{2} + \binom{n}{5} + \binom{n}{8} + \binom{n}{11} + \cdots = \frac{1}{3} \cdot \left( 2^n + 2 \cos \frac{n-4}{3} \pi \right)$   

 

Bước 2: Ta để ý : chỉ cần $1$ trong số $n$ số $ x_1; x_2 ;...; x_n$ bằng $0$ thì tích của $n$ số này bằng $0$, chia hết cho $3$

 

Và việc thêm hay bớt $1$ số $0$ trong tổng $ x_1+ x_2 +...+ x_n$ không ảnh hưởng đến số dư của tổng này trong phép chia cho $3$

 

Chẳng hạn như từ $1$ bộ $k$ số $ (x_1; x_2; ...; x_k)$  mà trong đó mỗi số $ x_1 ; x_2;... ; x_k \in \{1;2 \}$ với $k < n$ thì ta có thể cho tương ứng với: $\binom{n}{n-k} = \binom{n}{k}$ bộ số  $ (x_1; x_2; ...; x_n)$ thỏa yêu cầu bài toán mà trong đó mỗi số $ x_1 ; x_2;... ; x_n \in \{ 0; 1;2 \}$ . Hiểu đơn giản là có $ \binom{n}{n-k} $cách chọn vị trí cho $n-k$ số $0$ để điền vào $n$ ô trống cho trước.  Do đó, bằng cách thiết lập quan hệ truy hồi, ta có thể tính ra:

 

Số bộ số $ (x_1; x_2; ...; x_n)$  thỏa yêu cầu bài toán mà trong $n$ số này có ít nhất $1$ số $0$. Ý tưởng đơn giản là dùng quy tắc cộng và xét lần lượt: trường hợp có đúng $1$ số $0$; trường hợp có đúng $2$ số $0$; ...; trường hợp có đúng $n$ số $0$ . Hiển nhiên sẽ không thể xảy ra trường hợp tổng $ x_1+ x_2 +...+ x_n$ chia hết cho $3$ và không có số $0$ nào trong tổng này vì khi đó thì dễ kiểm tra tích $ x_1 x_2  \cdots x_n$ không chia hết cho $3$, vô lý vì không đáp ứng giả thiết ban đầu của bài toán là hiệu của tổng và tích $n$ số này chia hết cho $3$.

 

Bước 3: Ta đi tính số bộ số $ (x_1; x_2; ...; x_n)$ với mỗi số $ x_1; x_2 ; ...; x_n \in \{1;2 \}$ và tổng $ x_1 + x_2 +...+ x_n$ này không chia hết cho $3$

Không còn cách nào khác là cũng đi vét cạn theo môđulô $3$ mà thôi.

 

Trường hợp $1$ : $ n \equiv 0 \pmod 3 $

Ta thử xét hệ phương trình đồng dư:

 

$ \begin{cases} n \equiv 0 \pmod 3 \\ k+2l \equiv 1 \pmod 3 \\ 2^l \equiv 1 \pmod 3 \end{cases}$ hoặc $ \begin{cases} n \equiv 0 \pmod 3 \\ k+2l \equiv 2 \pmod 3 \\ 2^l \equiv 2 \pmod 3 \end{cases}$

 

tức là: $ \begin{cases} n=k+l \equiv 0 \pmod 3 \\ k+2l \equiv 1 \pmod 3 \\ l \equiv 0 \pmod 2 \end{cases}$ hoặc $ \begin{cases} n=k+l \equiv 0 \pmod 3 \\ k+2l \equiv 2 \pmod 3 \\ l \equiv 1 \pmod 2 \end{cases}$

 

$ \Leftrightarrow \begin{cases} n=k+l \equiv 0 \pmod 3 \\ k \equiv 2 \pmod 3 \\ l \equiv 1 \pmod 3 \\ l \equiv 0 \pmod 2 \end{cases}$ hoặc $\begin{cases} n=k+l \equiv 0 \pmod 3 \\ k \equiv 1 \pmod 3 \\ l \equiv 2 \pmod 3 \\ l \equiv 1 \pmod 2 \end{cases}$

 

$ \Leftrightarrow \begin{cases} n=k+l \equiv 0 \pmod 3 \\ k \equiv 2 \pmod 3 \\ l \equiv 4 \pmod 6 \end{cases}$ hoặc $\begin{cases} n=k+l \equiv 0 \pmod 3 \\ k \equiv 1 \pmod 3 \\ l \equiv 5 \pmod 6 \end{cases}$

 

$ \Leftrightarrow \begin{cases} n=k+l \equiv 0 \pmod 6 \\ k \equiv 2 \pmod 6 \\ l \equiv 4 \pmod 6 \end{cases}$ hoặc $\begin{cases} n=k+l \equiv 3 \pmod 6 \\ k \equiv 5 \pmod 6 \\ l \equiv 4 \pmod 6 \end{cases}$ hoặc $\begin{cases} n=k+l \equiv 0 \pmod 6 \\ k \equiv 1 \pmod 6 \\ l \equiv 5 \pmod 6 \end{cases}$ hoặc $\begin{cases} n=k+l \equiv 3 \pmod 6 \\ k \equiv 4 \pmod 6 \\ l \equiv 5 \pmod 6 \end{cases}$

 

$ \Leftrightarrow \begin{cases} n=k+l \equiv 0 \pmod 3 \\ l \equiv 4;5 \pmod 6 \end{cases}$ 

 

Tức là với $ n \equiv 0 \pmod 3$  thì số bộ số cần tính là tổng của $2$ tổng con:

 

$ \binom{n}{4} + \binom{n}{10} + \binom{n}{16} + \binom{n}{22} + \cdots $

 

Và $ \binom{n}{5} + \binom{n}{11} + \binom{n}{17} + \binom{n}{23} + \cdots $

 

Nhưng những tổng con này đều có thể tính ra chi tiết được theo $n$ vì theo kết quả đã nêu ra trong chuyên đề đẳng thức tổ hợp thì ta có kết quả tổng quát:

 

$ \sum_{ r \geq 0}^{} \binom{n}{j+rk} = \frac{2^n}{k} \sum_{m=0}^{k-1} \left( \cos \frac{ m \pi}{k} \right)^{n}  \cos \frac{ (n-2j)m \pi}{k}  (\bigstar)$

 

Ta làm tương tự để tính với các trường hợp: $ n \equiv 1 \pmod 3$ ;  $ n \equiv 2 \pmod 3$

 

Bước 4: Số bộ số thỏa yêu cầu bài toán là tổng các bộ số thuộc $2$ nhóm:

 

- Nhóm $1$: Nhóm các bộ số thỏa mãn điều kiện bài toán và $ 3 | x_1 + x_2 + \cdots + x_n$ (đã tính ra chi tiết từ bước $2$)

 

- Nhóm $2$: Nhóm các bộ số thỏa mãn điều kiện bài toán và $ 3 \not | x_1 + x_2 + \cdots + x_n$ (đã tính ra chi tiết từ bước $3$)

 

Theo đó thì bài toán được giải quyết hoàn toàn.

 

Lời nhờ vả: Trong chuyên đề đẳng thức tổ hợp, kết quả $(\bigstar)$ được nêu ra như $1$ bài tập tự giải, các bạn hãy giải bài toán này chi tiết. Đồng thời hoàn thiện lời giải trên. Việc còn lại là các công đoạn thu gọn tổng cần tính để ra được kết quả cuối cùng theo $n$ .      Sau vài ngày nghỉ dịch thì nay supermember quay trở lại nhịp sống bình thường. Xin nhường những việc này cho các bạn

Bài viết đã được chỉnh sửa nội dung bởi supermember: 05-10-2021 - 08:29

[Nobodyv3]

Thú vị đây! Anh cứ trình bày các bước tiếp theo... Có thể em thực bước 1 áp dụng RUF (hy vọng em làm đúng).