[Toán 9] Đề PTNK.

[hongnhung.97]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho em hỏi câu này với... em không biết làm (kiến thức em không tốt ah ~)

Câu V: Cho đa giác n cạnh. Dùng 3 màu xanh, đỏ, vàng tô màu các đỉnh đa giác một cách tùy ý (mỗi đỉnh được tô bởi một màu và tất cả các đỉnh đều được tô màu). Cho phép thực hiện các thao tác sau đây: Chọn 2 đỉnh kề nhau bất kì (nghĩa là 2 đỉnh liên tiếp) khác nhau và thay màu 2 đỉnh đó bằng màu còn lại.
a. Chứng minh rằng bằng cách thực hiện thao tác trên một số lần ta luôn luôn làm cho các đỉnh của đa giác chỉ còn được tô bởi 2 màu.
b. Chứng minh rằng vs n=4 và n=8, bằng cách thực hiện thao tác trên một số lần ta có thể làm cho các đỉnh của đa giác chỉ còn được tô bởi một màu.

P.s Nhờ giúp đỡ của bạn Anh em đã tìm dc lời giải bên Mathscope. Bà con tham khảo thử ~ còn cách nào hay hơn chỉ em với :">. Em xin cảm ơn.

Bài này có thể giải như sau:

Kí hiệu các màu vàng, đỏ, xanh lần lượt là V, Đ, X.
a) Không mất tính tổng quát, giả sử tại thời điểm ban đầu, màu vàng được tô ít nhất.
Ta sẽ chỉ ra một cách thực hiện thao tác để chuyển tất cả các đỉnh của đa giác về màu đỏ hoặc xanh.
Lúc này, ta chỉ quan tâm đến màu vàng và màu khác vàng, kí hiệu là K.
Đánh số các đỉnh từ 1 đến n theo chiều kim đồng hồ.
Nếu lúc đầu không có đỉnh nào được tô V thì bài toán kết thúc.
Ngược lại thì tồn tại ít nhất một dãy các đỉnh được tô V (dãy có thể có độ dài 1). Do tính nhỏ nhất nên dãy đỉnh này sẽ có độ dài không vượt quá và phía trước hoặc phía sau của nó sẽ là một đỉnh được tô màu K.
Ta lại thấy rằng bằng cách thực hiện quy tắc đổi màu như đề bài liên tục trên dãy đỉnh này thì:
KVVV...V -> KKVV...V -> KKKV...V -> KKKK...V -> ... -> KKKK...K
Áp dụng với tất cả các dãy, tất cả các đỉnh sẽ được tô màu K, ta có đpcm.

b) Nhận xét rằng đối với đa giác 4 đỉnh, nếu ta chuyển được về dạng:
XXVV hoặc XVXV (ở đây ta chọn đại diện hai màu này, thực ra nếu là thay VV bởi DD hay tương tự thế đều được), tức là mỗi cặp đỉnh cùng màu cùng nằm kề nhau hoặc cùng không nằm kề nhau thì bài toán coi như xong. Thật vậy, khi đó ta đổi hai đỉnh 1-4 thành DD và hai đỉnh 2-3 thành DD.
Nhưng việc chuyển về dạng trên luôn thực hiện được vì theo câu a, ta đã có thể chuyển 4 đỉnh về 2 màu.
+Nếu như 2 màu ấy có số lượng bằng nhau thì ta sẽ luôn có dạng trên.
+Nếu như 2 màu ấy khác số lượng nhau (tỉ lệ 1-3) thì ta chỉ cần chuyển thêm một lần nữa để đưa 2 đỉnh kề khác màu thành màu còn lại thì quay về trường hợp trên.

Đối với đa giác 8 đỉnh, đòi hỏi nhiều nhận xét hơn, chẳng hạn nếu chuyển được về dạng: XXXXVVVV (1) hoặc XXVVXXVV (2) thì xong.
(Nhắc lại lần nữa là 2 màu X và V chỉ lấy làm đại diện, có thể thay bởi cặp X, D hay D, V miễn sao thứ tự các màu giống là như trên).
Thật vậy, dạng 1 có thể chuyển về dạng 2 bằng bằng cách đổi màu đỉnh 4-5 và 1-8. Dạng 2 có thể đổi màu 1-8,2-3,4-5,6-7 để đưa tất cả về cùng màu còn lại.

Công việc của chúng ta là chứng minh rằng luôn có thể chuyển một đa giác 8 đỉnh về một trong hai dạng trên. Mời các bạn thử tiếp nhé!

--

Trường hợp mình giải lại chi tiết như sau:
Rõ ràng với một cách tô màu bất kì cho 8 đỉnh, ta luôn có thể chuyển về 2 màu, giả sử là X và V và số lượng đỉnh X không nhiều hơn số lượng đỉnh V. Ta xét các trường hợp sau (ta chỉ xét đại diện, các trường hợp còn lại có thể xảy ra đều nhận được từ một phép quay của các trường hợp nêu ra):




- Trường hợp có 1 đỉnh X và 7 đỉnh V: XVVVVVVV (1)
- Trường hợp có 2 đỉnh X và 6 đỉnh V, ta có các trường hợp nhỏ là:
XXVVVVVV (2), XVXVVVVV (3), XVVXVVVV (4), XVVVXVVV (5)
- Trường hợp có 3 đỉnh X và 5 đỉnh V, có 2 trường hợp:
+ Mỗi đỉnh X kề với ít nhất một đỉnh V, ta chuyển tất cả các cặp XV ấy về một trong các dạng (2), (3), (4), (5) trên.
+ Ba đỉnh X kề nhau: XXXVVVVV, ta chuyển như sau:
XXXVVVVV -> DXDDVVVD -> DVVDVVVD -> XXXXVVXX, đây là dạng (2).
- Trường hợp có 4 đỉnh X và 4 đỉnh V: ta chỉ cần xét 2 dạng là
XXVVXXVV (6) và XXXXVVVV (7)
Các dạng 4-4 khác đều có thể chuyển về một trong các dạng đã nêu.

*Ta có các nhận xét sau:

- Trường hợp (1) có thể chuyển về (2) bằng một phép biến đổi.
- Với trường hợp (6), ta chỉ cần chuyển 1-8,2-3,4-5,6-7 thành màu D là xong.
- Với trường hợp (7), ta chỉ cần chuyển như sau:
XXXXVVVV -> DXXDDVVD -> VVVVDVVD -> XVVXXVVX, đây là dạng (6).
- Tất cả các dạng (2), (3), (4), (5) đều có thể đưa về dạng (6), (7).

Với các nhận xét này, ta dễ thấy đpcm.
Cách này thủ công quá và nói chung cũng không mang tính tổng quát, bạn nào có cách khác thì chia sẻ nha!

Các bài tổ hợp yêu cầu phải xây dựng mô hình hay dãy các bước thỏa mãn đề bài thế này nên được chú trọng vì gần đây, các kì thi lớn như TST, IMO đều có và thường thể hiện dưới dạng các bài cực trị rời rạc, phần xây dựng nằm ở bước chỉ ra một bộ thỏa đề.

P.s Không biết Quote kiểu này có tính là spam không :-S. Nếu có thì xóa hộ em cái phần Quote ah ^^~.