Đến nội dung

Hình ảnh

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$


  • Please log in to reply
Chủ đề này có 8 trả lời

#1
Dennis Nguyen

Dennis Nguyen

    Hạ sĩ

  • Thành viên
  • 59 Bài viết

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$.



#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

$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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
Dennis Nguyen

Dennis Nguyen

    Hạ sĩ

  • Thành viên
  • 59 Bài viết

$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
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

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).


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#5
jupiterhn9x

jupiterhn9x

    Hạ sĩ

  • Banned
  • 71 Bài viết

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
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Ý 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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#7
jupiterhn9x

jupiterhn9x

    Hạ sĩ

  • Banned
  • 71 Bài viết

Ý 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
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#9
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Em xin đề xuất lời giải khá là trực quan qua phép chứng minh bằng phản chứng như sau:
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.
===========
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...




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh