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

[QUANVU]

Cho $k$ là số nguyên dương và $S_n=\left \{1,2,...,n \right \},(n \geq 3) $. Hàm $f:S_n^k \to S_k$ thỏa mãn: nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$. Chứng minh rằng có $i \in \left \{1,2,...,k \right \}$ sao cho:
$$f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$$.

[PSW]

Bài toán này thuộc Gameshow NHỮNG BÀI TOÁN TRONG TUẦN. Bài toán đã được công bố lại hơn nhiều ngày nhưng chưa ai giải được. BTC đã đặt hoa hồng hi vọng cho bài toán này

Hoa hồng hi vọng sẽ mang lại 50 điểm cho người đầu tiên giải đúng (hoặc phủ định đúng) được bài toán này. Nếu hết ngày 19/03 mà vẫn không có ai giải được hoặc phủ định được bài toán này, BTC sẽ công bố bài toán khác, tuy nhiên hoa hồng hi vọng sẽ vẫn tồn tại cho đến khi có người giải được bài toán này

Bài viết đã được chỉnh sửa nội dung bởi PSW: 25-03-2013 - 22:52

[phudinhgioihan]

Cho $k$ là số nguyên dương và $S_n=\left \{1,2,...,n \right \},(n \geq 3) $. Hàm $f:S_n^k \to S_k$ thỏa mãn: nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$. Chứng minh rằng có $i \in \left \{1,2,...,k \right \}$ sao cho:
$$f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$$.

 

 

Trước tiên, theo giả thiết nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$ thì điều này có nghĩa là nếu $a,b \in S_n^k $ và $a \neq b$ thì $f(a) \neq f(b)$, tức $f$ đơn ánh.

 

Do đó,nếu tồn tại $i \in \left \{1,2,...,k \right \}$ sao cho $f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$

 

Nếu $k \ge 2 $,

 

Khi đó, với $j \in \{1,2,...,k \} -\{i\} $, chọn hai bộ số $(a_1,a_2,...,a_k)$ và $(a'_1,a'_2,...,a'_k)$ sao cho cả hai bộ số có phần tử vị trí $i$ bằng nhau và phần tử vị trí $j$ khác nhau, theo tính chất đề bài thì $f(a_1,a_2,...,a_k) \neq f(a'_1,a'_2,...,a'_k)$ , mâu thuẫn !

 

Nếu $k=1$ thì $f(i)=i \;, \forall i \in S_n $, do đó đề bài không đúng với $f$ là một hàm số bất kỳ.

 

Vậy điều phải chứng minh là sai !

[E. Galois]

Trước tiên, theo giả thiết nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$ thì điều này có nghĩa là nếu $a,b \in S_n^k $ và $a \neq b$ thì $f(a) \neq f(b)$, tức $f$ đơn ánh.

 

Hai bộ $a,b$ khác nhau thì chưa chắc đã khác nhau ở tất cả các vị trí. Đạt có nhầm lẫn chăng?

[Trungpbc]

Cho $k$ là số nguyên dương và $S_n=\left \{1,2,...,n \right \},(n \geq 3) $. Hàm $f:S_n^k \to S_k$ thỏa mãn: nếu $a,b \in S_n^k$ và chúng khác nhau ở tất cả các vị trí thì $f(a) \neq f(b)$. Chứng minh rằng có $i \in \left \{1,2,...,k \right \}$ sao cho:
$$f(a_1,a_2,...,a_k)=a_i ,\forall a=(a_1,a_2,...,a_k)\in S_n^k$$.

Kết luận của bài này chưa chính xác, tuy nhiên nếu sửa lại kết luận thành:

Chứng minh tồn tại chỉ số $i$ và hàm song ánh $g$ trên $S_n$ thỏa mãn: $f(a_{1},a_{2},\dots,a_{n})=g(a_{i}),\ \forall (a_{1},\dots,a_{n})\in S_{n}^k$ thì đây là một bài toán "logic" về hàm số khá thú vị.

Ta chứng minh kết quả bài toán bằng quy nạp theo $k$. Với $k=1$ bài toán hiển nhiên đúng. Xét $k>1$, có hai trường hợp xảy ra:

Trường hợp 1: Tồn tại bộ $(a_{2},a_{3},\dots,a_{k})\in S_{n}^{k-1}$ sao cho $f(a,a_{2},\dots,a_{n})\neq f(b,a_{2},\dots,a_{n}),\ \forall a\neq b$. Khi đó, hiển nhiên tồn tại hàm song ánh $g$ trên $S_n$ sao cho: $$f(a,a_{2},\dots,a_{n})=g(a),\forall a\in S_{n}$$ Với bộ $(b_{2},b_{3},\dots,b_{n})\in S_{n}^{k-1}$ bất kì thỏa mãn $b_{i}\neq a_{i},\ \forall i=2,3,\dots,n$. Theo giả thiết: $$f(b_{1},b_{2},\dots,b_{n})\neq f(a,a_{2},\dots,a_{n})=g(a),\ \forall b_{1}\neq a$$ Từ đó, với chú ý $g$ là hàm song ánh, suy ra: $f(b_{1},b_{2},\dots,b_{n})=g(b_{1})$. Với bộ $(c_{2},c_{3},\dots,c_{n})\in S_{n}^{k-1}$ bất kì, vì $n>2$ nên tồn tại bộ $(b_{2},b_{3},\dots,b_{n})\in S_{n}^{k-1}$ thỏa mãn: $b_{i}\neq a_{i},c_{i}$ với mọi $i=2,3,\dots,n$. Áp dụng kết luận trên cho bộ $(a_{2},\dots,a_{n})$ và bộ $(b_{2},\dots,b_{n}$, ta có: $$f(b_{1},b_{2},\dots,b_{n})=g(b_{1})$$ Áp dụng kết luận đó lần nữa cho bộ $(b_{2},\dots,b_{n})$ và bộ $(c_{2},\dots,c_{n})$, ta có:

$$f(c_{1},c_{2},\dots,c_{n})=g(c_{1})$$ Bài toán được chứng minh trong trường hợp 1.

Trường hợp 2. Với mỗi bộ $(a_{2},a_{3},\dots,a_{k})\in S_{n}^{k-1}$, tồn tại hai số $a\neq {a}'$ sao cho: $$f(a,a_{2},\dots,a_{n})=f({a}',a_{2},\dots,a_{n})$$ Đặt hàm $h:S_{n}^{k-1} \mapsto S_{n}$ như sau: $h(a_{2},a_{3},\dots,a_{n})=f(a,a_{2},\dots,a_{n})=f(a',a_{2},\dots,a_{n})$, chú ý rằng nếu có nhiều cặp $(a,a')$ có tính chất như trên thì chọn một trong các cặp đó để định nghĩa cho hàm $h$. Dễ thấy, hàm $h$ thỏa mãn giả thiết quy nạp, nên tồn tại chỉ số $i$, không mất tổng quát ta giả sử $i=2$, và hàm song ánh $g$ trên $S_n$ thỏa mãn: $h(a_{2},a_{3},\dots,a_{n})=g(a_{2})$. Giả sử tồn tại bộ $(a_{1},a_{2},a_{3},\dots,a_{n})\in S_{n}^{k}$ sao cho: $f(a_{1},a_{2},\dots,a_n)\neq g(a_{2})$. Vì $g$ song ánh nên có $b_2\neq a_2$ sao cho: $$f(a_{1},a_{2},\dots,a_n) = g(b_{2})$$ Chú ý rằng $n>2$ nên chọn được bộ $(b_{3},\dots,b_{n})\in S_{n}^{k-2}$ sao cho $b_{i}\neq a_{i}$ với mọi $i=3,\dots,n$. Chọn $b_{1}\in \left \{ b,b' \right \}$ sao cho $b_{1}\neq a_{1}$, ở đây vai trò của $b,b'$ tương tự vai trò của của $a,a'$. Khi đó: $$f(b_{1},b_{2},\dots,b_{n})=h(b_{2},\dots,b_{n})=g(b_{2})=f(a_{1},a_{2},\dots,a_{n})$$ mâu thuẫn vì $a_{i}\neq b_{i},\ \forall i=1,2,\dots,n$. như vậy bài toán được chứng minh trong trường hợp 2.

Tóm lại bài toán được chứng minh hoàn toàn.

Bài viết đã được chỉnh sửa nội dung bởi Trungpbc: 14-06-2013 - 23:04