Cho tập $X\doteq \left \{ 1,2,3,....,9 \right \}$, chia tập X thành hai tập rời nhau A và B. Chứng minh với mọi cách chia, luôn tồn tại ba phần tử $a<b<c$ thuộc cùng một tập sao cho $a+c=2b$.
Chứng minh với mọi cách chia, luôn tồn tại ba phần tử $a<b<c$ thuộc cùng một tập sao cho $a+c=2b$
#2
Đã gửi 17-07-2021 - 00:13
$a+c=2b \Leftrightarrow a-b=b-c \Leftrightarrow (a;b;c)$ là một cấp số cộng (CSC).
Phân hoạch thành hai tập tương đương với việc tô mỗi số bằng một trong hai màu cho trước.
Đây là một trường hợp kinh điển không tầm thường của định lý Van der Waerden. https://en.wikipedia...erden's_theorem
Cách chứng minh đầu tiên do V. Chvátal đề xuất bằng vét cạn: http://users.encs.co...chvatal/vwn.pdf
Có thể giảm số trường hợp cần xét bằng một số nhận xét sau:
Mọi bộ 3 số tự nhiên liên tiếp sẽ tạo thành một CSC. Do đó, chỉ cần xét những trường hợp mà không có 3 số tự nhiên liên tiếp nào cùng một màu.
Cuối cùng, có khoảng một chục cách để tô màu các số $1\ldots 8$ sao cho không thỏa đề. https://datagenetics...2017/index.html
Với mỗi cách này, khi thêm số $9$ vào, bất kể màu nào, cũng sẽ tạo thành một CSC.
- DOTOANNANG yêu thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#3
Đã gửi 20-07-2021 - 09:41
$a+c=2b \Leftrightarrow a-b=b-c \Leftrightarrow (a;b;c)$ là một cấp số cộng (CSC).
Phân hoạch thành hai tập tương đương với việc tô mỗi số bằng một trong hai màu cho trước.
Đây là một trường hợp kinh điển không tầm thường của định lý Van der Waerden. https://en.wikipedia...erden's_theorem
Cách chứng minh đầu tiên do V. Chvátal đề xuất bằng vét cạn: http://users.encs.co...chvatal/vwn.pdf
Có thể giảm số trường hợp cần xét bằng một số nhận xét sau:
Mọi bộ 3 số tự nhiên liên tiếp sẽ tạo thành một CSC. Do đó, chỉ cần xét những trường hợp mà không có 3 số tự nhiên liên tiếp nào cùng một màu.
Cuối cùng, có khoảng một chục cách để tô màu các số $1\ldots 8$ sao cho không thỏa đề. https://datagenetics...2017/index.html
Với mỗi cách này, khi thêm số $9$ vào, bất kể màu nào, cũng sẽ tạo thành một CSC.
Bạn có thể trình bày rõ ra giúp mình với! Bạn chỉ cần giúp mình bài mình hỏi ý!
#4
Đã gửi 20-07-2021 - 14:21
Bạn có thể trình bày rõ ra giúp mình với! Bạn chỉ cần giúp mình bài mình hỏi ý!
Như mình đã nói phía trên. Việc phân chia thành hai tập hợp là tương đương với việc tô mỗi số bằng một trong hai màu, chẳng hạn xanh đỏ.
Bây giờ chỉ cần xét tập $Y$ từ $1$ đến $8$. Nếu trong cách tô màu (phân hoạch) mà có 3 số trong $Y$ cùng màu tạo thành CSC thì số $9$ cuối cùng tô màu gì cũng không quan trọng.
Ta xét trường hợp còn lại: có cách tô màu $Y$ để không có 3 số cùng màu nào tạo thành CSC.
Sẽ có 7 cách tất cả như thế (bạn tham khảo https://datagenetics...2017/index.html )
Với mỗi cách này, khi thêm số 9 vào cuối, bất kể bạn chọn màu nào, thì cũng sẽ tạo thành một CSC (có số 9 tận cùng).
- DOTOANNANG yêu thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#5
Đã gửi 15-03-2022 - 10:09
Như mình đã nói phía trên. Việc phân chia thành hai tập hợp là tương đương với việc tô mỗi số bằng một trong hai màu, chẳng hạn xanh đỏ.
Bây giờ chỉ cần xét tập $Y$ từ $1$ đến $8$. Nếu trong cách tô màu (phân hoạch) mà có 3 số trong $Y$ cùng màu tạo thành CSC thì số $9$ cuối cùng tô màu gì cũng không quan trọng.
Ta xét trường hợp còn lại: có cách tô màu $Y$ để không có 3 số cùng màu nào tạo thành CSC.
Sẽ có 7 cách tất cả như thế (bạn tham khảo https://datagenetics...2017/index.html )
Với mỗi cách này, khi thêm số 9 vào cuối, bất kể bạn chọn màu nào, thì cũng sẽ tạo thành một CSC (có số 9 tận cùng).
Ý tưởng của bạn chưa rõ ràng lắm nhỉ, bạn có thể nói cụ thể tại sao thêm số 9 vào thì tạo thành CSC không ạ?
#6
Đã gửi 15-03-2022 - 15:15
Ý tưởng của bạn chưa rõ ràng lắm nhỉ, bạn có thể nói cụ thể tại sao thêm số 9 vào thì tạo thành CSC không ạ?
Ý tưởng thì không phải của mình, nhưng cũng dễ hiểu Nếu có một CSC cùng màu trong tập $X' = \{1; 2; ...; 8\}$ thì coi như thỏa đề. Giờ xét trường hợp không có CSC cùng màu nào trong dãy $X'$. Bằng phương pháp vét cạn, V. Chvátal đã tìm ra 7 trường hợp (không kể đổi màu và đối xứng) để $X'$ không có CSC. Trong các trường hợp đó, khi bạn thêm số 9 vào với bất kỳ màu gì, cũng sẽ tìm ra một CSC.
Ví dụ trường hợp này: 1 2 3 4 5 6 7 8 ($X \quad D \quad D \quad X \quad X \quad D \quad D \quad X$). Nếu bạn thêm số 9 màu đỏ thì sẽ có CSC $(3;6;9)$ cùng đỏ, còn nếu màu xanh thì $(1;5;9)$ cùng xanh.
- DOTOANNANG yêu thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#7
Đã gửi 15-03-2022 - 16:07
Ý tưởng thì không phải của mình, nhưng cũng dễ hiểu Nếu có một CSC cùng màu trong tập $X' = \{1; 2; ...; 8\}$ thì coi như thỏa đề. Giờ xét trường hợp không có CSC cùng màu nào trong dãy $X'$. Bằng phương pháp vét cạn, V. Chvátal đã tìm ra 7 trường hợp (không kể đổi màu và đối xứng) để $X'$ không có CSC. Trong các trường hợp đó, khi bạn thêm số 9 vào với bất kỳ màu gì, cũng sẽ tìm ra một CSC.
Ví dụ trường hợp này: 1 2 3 4 5 6 7 8 ($X \quad D \quad D \quad X \quad X \quad D \quad D \quad X$). Nếu bạn thêm số 9 màu đỏ thì sẽ có CSC $(3;6;9)$ cùng đỏ, còn nếu màu xanh thì $(1;5;9)$ cùng xanh
Tóm lại bài này phải xây dựng các tập cụ thể chứ không thể dùng nguyên lý Dirichlet để chứng minh
#8
Đã gửi 15-03-2022 - 17:25
Không phải là không thể dùng Dirichlet. Chỉ là hiện tại mình chưa thấy ai dùng Dirichlet để chứng minh chặt chẽ $9$ là GTNN.
Nếu bạn đọc bài chứng minh trong Wiki thì bạn sẽ thấy người ta đã dùng Dirichlet để tìm ra chặn trên của GTNN.
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#9
Đã gửi 16-03-2022 - 00:08
Giả sử trong tập A cũng như trong tập B đều không chứa 3 phần tử nào tạo thành 1 cấp số cộng: như vậy, nếu $5 \in A$ thì $1$ và $9 \text{ không cùng thuộc } A$, do đó ta xét 3 trường hợp :
- TH 1: $(1 \in A)\wedge (9 \in B)$:
Vì $1$ và $5 \in A$ nên $3 \in B$.
Vì $3$ và $9 \in B$ nên $6 \in A$.
Vì $5$ và $6 \in A$ nên $4 \in B$.
Vì $3$ và $4 \in B$ nên $2 \in A$.
Vì $5$ và $6 \in A$ nên $7 \in B$.
Vì $7$ và $9 \in B$ nên $8 \in A$
$\Longrightarrow A$ chứa CSC $ 2, 5, 8 $ (trái với giả thiết).
- TH 2: $(9 \in A)\wedge (1 \in B)$:
Nhận xét : tập $X$ là bất biến khi ta thay mỗi phần tử bằng phần tử bù của chúng ( thí dụ : 1 thay bằng 9, 2 thay bằng 8..v..v..) lúc này sẽ trở về TH 1 mà ta đã xét.
- TH 3: $(1 \in B)\wedge (9 \in B)$: xét 2 tiểu trường hợp :
TH 3a: $(7 \in A)$:
Vì $5$ và $7 \in A$ nên cả $3$ và $6 \in B \Longrightarrow B $ chứa CSC $3, 6, 9$.
TH 3b: $(7 \in B)$: thì $8 \in A$.
Vì $1$ và $7 \in B$ nên $4 \in A$.
Vì $4$ và $5 \in A$ nên $3 \in B$.
Vì $1$ và $3 \in B $ nên $2 \in A \Longrightarrow A $ chứa CSC $2, 5, 8 $.
Kết luận : Kết quả của 3 TH trên đều trái với giả thiết, do đó , theo phép chứng minh bằng phản chứng thì khẳng định của bài toán là đúng.
- perfectstrong và NguyenLuTham368 thích
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh