Thuvientoan.net xin gửi đến bạn đọc tài liệu Bài tập tổng hợp ôn thi TST của tác giả Nguyễn Trọng Tấn.

Bài 4. Trên mặt phẳng, cho n > 3 đường thẳng sao cho không có ba đường thẳng nào đồng quy và không có hai đường nào song song. Một giao điểm được gọi là "tốt" nếu như về hai phía của mỗi đường thẳng đi qua nó, còn ít nhất một giao điểm khác. Tìm giá trị nhỏ nhất của số điểm tốt.

Lời giải.
Ta sẽ có các định nghĩa như sau
 Một giao điểm được gọi là "xấu" nếu nó không "tốt".
 Hai giao điểm được gọi là liền kề trên đường thẳng l nếu giữa chúng không có một giao điểm khác.
 Một giao điểm được gọi là "mút" của đường thẳng l nếu nó chỉ liền kề với đúng một giao điểm trên l.
Xét đồ thị G(V, E) gồm các đỉnh là các giao điểm và được nối với nhau bằng một đoạn thẳng nếu chúng liền kề nhau trên một đường thẳng ban đầu. Khi đó, G có |V | = C2n và |E| = n(n − 2). Ta dễ thấy rằng, bậc của mỗi đỉnh chỉ có thể là 2, 3, 4 (đỉnh của giao điểm tốt sẽ có bậc là 4). Gọi si là số đỉnh có bậc i. Ta có bổ đề sau

Bổ đề. (Bổ đề bắt tay [4]) Cho đồ thị vô hướng G(V, E) thì ta có rằng:

Từ bổ đề trên, ta có các mối quan hệ sau:

Tiếp đến, ta thấy rằng, tồn tại đồ thị đa giác lồi P có các đỉnh là các giao điểm mút sao cho phủ lấy các giao điểm còn lại. Dễ thấy rằng bậc của chúng là 2 nên s2 ≥ 3. Do đó
s4 - s2 ≥ (n^2−5n+6)/2. Ta sẽ chứng minh rằng đó là giá trị nhỏ nhất của bài toán.

Tải tại đây.

THEO THUVIENTOAN.NET