Tìm số nguyên dương $k$ nhỏ nhất sao cho với mọi cách sắp xếp 99 điểm màu đỏ và 100 điểm

Câu hỏi số 799073:

Vận dụng

Tìm số nguyên dương $k$ nhỏ nhất sao cho với mọi cách sắp xếp 99 điểm màu đỏ và 100 điểm màu xanh trên mặt phẳng (không có ba điểm nào thẳng hàng), ta luôn vẽ được $k$ đường thẳng, mỗi đường thẳng không đi qua điểm nào trong các điểm trên và các đường thẳng đó chia mặt phẳng thành các miền mà trong mỗi miền không có hai điểm khác màu

Quảng cáo

Xem lời giải

Câu hỏi:799073

Phương pháp giải

Xét đa giác lồi 199 đỉnh với 99 điểm tô màu đỏ và 99 điểm tô màu xanh xen kẽ nhau và 1 điểm màu xanh tùy ý trên 1 đường tròn

Đa giác có 198 cạnh chứa cả hai đỉnh màu xanh và màu đỏ

Rõ ràng 1 đường thẳng cắt nhiều nhất hai cạnh của đa giác trên và mỗi cạnh chứa cả hai đỉnh có 2 màu phải được cắt ít nhất bởi 1 đường thẳng nên số đường thẳng ít nhất là $k \geq \dfrac{198}{2} = 99$

Xét bao lồi $S$ chứa các 199 điểm

Giải chi tiết

Xét đa giác lồi 199 đỉnh với 99 điểm tô màu đỏ và 99 điểm tô màu xanh xen kẽ nhau và 1 điểm màu xanh tùy ý trên 1 đường tròn

Đa giác có 198 cạnh chứa cả hai đỉnh màu xanh và màu đỏ

Ta chứng minh $k = 99$ thỏa mãn yêu cầu của đề bài

Xét bao lồi $S$ chứa các 199 điểm

Trường hợp 1: Nếu bao lồi có 1 điểm đỏ thì ta kẻ được một đường thẳng chia thành 2 miền đơn sắc (chỉ chứa màu đỏ hoặc màu xanh). Với 98 điểm đỏ còn lại, ta chia các điểm này thành 49 cặp, với 2 điểm $A,\,\, B$ bất kì cùng màu ta kẻ hai đường thẳng song song với $AB$ và cách $AB$ một khoảng nhỏ để tạo ra một miền mới mà miền này chỉ chứa đúng hai điểm $A,\,\, B$. Như vậy ta cần dùng $1 + 49.2 = 99$ đường thẳng

Trường hợp 2: Nếu bao lồi gồm toàn các điểm xanh thì kẻ một đường thẳng song song, cách cạnh của bao lồi khoảng đủ nhỏ thì ta tách được hai điểm xanh ra một miền mới. Còn 98 điểm xanh, ta chia các điểm này thành 49 cặp, làm tương tự trường hợp trên ta sẽ kẻ được $49.2 = 98$ đường thẳng. Như vậy ta cần kẻ 99 đường thẳng, mỗi điểm xanh chỉ nằm trong miền chứa toàn các điểm xanh khác.

Vậy $\min k = 99$

PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. PH/HS tham khảo chi tiết khoá học tại: Link