tôi gợi ý câu cuối.
bạn thấy cách nối như bài toán có nghĩa là theo quy tắc: Nối các điểm để tạo thành các đoạn thẳng sao cho ko tạo thành bất kì 1 tam giác nào cả.
trước hết ta chỉ ra 1 cách nối để có số đoạn thẳng = [tex]n^{2}[/tex]
Chia 2n điểm đó thành 2 tập X và Y, mỗi tập có n điểm, giả sử các điểm trong X là X1, X2, ..., Xn và trong Y là Y1, Y2, ..., Yn.
vì các điểm là phân biệt và ko có 3 điểm nào thẳng hàng nên 2 điểm bất kì luôn nối đc thành đoạn thẳng và 3 điểm bất kì luôn tạo thành tam giác.
xét cách nối (C) trong đó ta lần lượt nối mỗi điểm trong X với mỗi điểm trong Y, nghĩa là 2 điểm bất kì A trong X và B trong Y thì đc nối với nhau, còn nếu A và B thuộc cùng trong X hay Y thì ko nối. như vậy cách nối này sẽ nối mỗi điểm trong 1 tập với tất cả các điểm trong tập kia. tức là X1 nối với tất cả các điểm Y1, Y2, ..., Yn. và X2, X3,... , Xn cũng thế cũng nối với tất cả các điểm Y1, Y2, ..., Yn.
Rõ ràng số đoạn thẳng trong (C) là [tex]n^{2}[/tex]
Cách nối (C) thỏa mãn yêu cầu bài toán vì: Ko có 3 điểm bất kì nào đc nối thành tam giác. Thật vậy, với 3 điểm bất kì, nếu chúng đều nằm trong X hay Y thì chúng ko đc nối với nhau, còn nếu có 2 điểm trong 1 tập và 1 điểm trong tập còn lại, giả sử 2 điểm trong X và 1 điểm trong Y thì điểm trong Y đều đc nối với 2 điểm kia, và 2 điểm trong X ko nối với nhau, nên ko nối thành tam giác.
Bây giờ ta c/m là cách nối (C) như thế là cách nối có số đoạn thẳng nhiều nhất. Xét 1 cách nối (B) bất kì thỏa yêu cầu bài toán. Xét 1 đoạn thẳng MN bất kì trong (B). Nếu M và N mỗi điểm thuộc 1 tập (X hoặc Y) còn điểm kia thuộc tập còn lại, thì MN là đoạn thẳng trong (C). Nếu MN thuộc trong cùng 1 tập giả sử X chẳng hạn, thì luôn tồn tại điểm P bên Y sao cho P ko thể đc nối với cả M và N (vì như vậy sẽ nối thành tam giác), do đó ta luôn có thể nối lại (thay thế) đoạn MN thành đoạn khác có 1 đầu thuộc X và 1 đầu thuộc Y (chẳng hạn nếu P nối với M thì ta bỏ đoạn MN đi và nối đoạn mới là PN). Như vậy mỗi lần thay thế như thế thì số lượng các đoạn thẳng ko thay đổi (vì thay 1 đoạn = 1 đoạn khác).Vì số các đoạn thuộc cùng 1 tập X hoặc Y như thế là hữu hạn nên sau 1 số hữu hạn bước thay thế ta sẽ đưa (B) về (B') sao cho trong B' thì các điểm trong cùng 1 tập X hoặc Y đều ko có 2 điểm nào nối với nhau, tức là B' có dạng giống (C), suy ra các đoạn trong B' thỏa mãn yêu cầu bài toán và số đoạn trong B' luôn nhỏ hơn hoặc bằng trong (C) (vì mọi đoạn trong B' thì cũng có 1 đầu thuộc X và 1 đầu thuộc Y nên đoạn đó cũng nằm trong (C)). Vậy (C) là cách nối có số đoạn nhiều nhất có thể. --> dpcm.
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
