Chủ đề này có 8 trả lời

[MrMATH]

Bài 2: http://dientuvietnam...mimetex.cgi?k,n là các số nguyên dương, trong mặt phẳng, n đường tròn được bố trí sao cho
i) 2 đường tròn tùy ý cắt nhau tại 2 điểm phân biệt
ii) không có 3 đường tròn nào đi qua cùng 1 điểm
Các giao điểm được tô bởi 1 trong n màu, môi màu được dùng ít nhất 1 lần, trên mỗi đường có đúng k màu
Tình k, n để việc tô màu có thể tiến hành được.

[lovePearl_maytrang]

Sau có ...một buổi sáng suy nghĩ, tớ nhận ra rằng bài này không khó nếu...biết làm
Ta biểu diễn bài toán bằng Graph như sau: n đường tròn được biểu diễn bằng n đỉnh, hai đỉnh bất kì được nối với nhau bằng hai cạnh tượng trưng cho hai giao điểm của hai đường tròn đó. Vấn đề đặt ra là tô màu các cạnh của G,đây là đồ thị đầy đủ kép(có hai cạnh nối cùng hai đỉnh)
Ta gọi n đỉnh là http://dientuvietnam...mimetex.cgi?A_i
Ta có http://dientuvietnam...tex.cgi?|T_i|=k và http://dientuvietnam...mimetex.cgi?A_i trên đường tròn theo ngược chiều kim đồng hồ, gọi là chiều dương.
Ta sẽ tô các cạnh bằng n màu là 1,2,...,n
Với hai đỉnh http://dientuvietnam...tex.cgi?A_i,A_j bất kì, do k (n+1)/2 nên một trong hai con đường (theo chiều dương) từ http://dientuvietnam...mimetex.cgi?A_i đến http://dientuvietnam...mimetex.cgi?A_j và từhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?A_i có độ dài không vượt quá k. Nếu cả hai con đường cùng thỏa như vậy thì trong hai cạnh nối hai đỉnh này , một cạnh tô i và một cạnh tô j
Nếu chỉ có con đường từ http://dientuvietnam...mimetex.cgi?A_i đến http://dientuvietnam...mimetex.cgi?A_j thỏa thì ta tô cả hai cạnh màu j
Cách tô này thỏa mãn
Vậy (n+1)/2 k n

[lovePearl_maytrang]

I'm sorry
Lại sau một buổi chiều suy nghĩ tớ lại phát hiện ra một sai lầm trầm trọng của lời giải trên (là gì nhỉ). Bất ngờ hơn khi mà tớ đã phát hiện ra một cách tô màu mà qua đó chứng tỏ rằng với mọi n không nhỏ hơn k và k>2 đều thoả mãn bài toán.
Với k=2 thì chưa biết (rất có thể là không thoả).

[lehoan]

Bác sai ở chỗ này.

.
Với k=2 và n=3 thì vẫn tô màu được thỏa mãn bài toán .
@:Để về nghĩ tiếp đã

[lovePearl_maytrang]

ok đúng rồi đó
thỉnh thoảng lại hay có mấy tình huống dở khóc dở cười vậy đó
Mà sao mấy đề này lại để vào box Đại số vậy, làm em tìm khùng người.
Mấy bài đại số lại để vào trong box toán rời rạc!!!

[lehoan]

Đáp số là hoặc

[lovePearl_maytrang]

Bài toán 1:Trong một giải đấu bằng hệ thức vòng tròn hai lượt có n đấu thủ. Điều hành giải có n trọng tài. Mỗi trận có 1 trọng tài, và mỗi trọng tài điều hành ít nhất 1 trận. Tìm k sao cho ta có thể sắp xếp để trong các trận đấu của một đấu thủ bất kì là do đúng k trọng tài điều hành.
Bài toán 2: Cho bảng vuông n*n gồm n cột đánh số từ trái sang phải và n hàng đánh số từ trên xuống dưới. Ô vuông ở hàng k cột m kí hiệu là (m,k). Tại các ô (m,k) với m k ta đánh số bằng các số thuộc tập {1,2,..,n}. Sao cho mỗi số được dùng để dánh ít nhất 1 lần. Tìm điều kiện của n,k để có thể đánh số sao cho i=1,2,...,n các ô ở hàng i và cột i đánh số bằng đúng k giá trị khác nhau.

[lovePearl_maytrang]

Thử xét bài toán trên cho đơn đồ thị xem sao:
Cho đơn đồ thị đầy đủ K_n. Tìm n,k để ta có thể tô màu các cạnh của đồ thị bằng n màu mỗi màu dùng ít nhất 1 lần, sao cho với một đỉnh bất kì, có đúng k màu dùng để tô các cạnh xuất phát từ đỉnh đó
LPm vừa phát hiện ra rằng bài toán với đơn đồ thị cũng có lời giải trong hầu hết các giá trị của k và n.

[lehoan]

Bài toán 1:Trong một giải đấu bằng hệ thức vòng tròn hai lượt có n đấu thủ. Điều hành giải có n trọng tài. Mỗi trận có 1 trọng tài, và mỗi trọng tài điều hành ít nhất 1 trận. Tìm k sao cho ta có thể sắp xếp để trong các trận đấu của một đấu thủ bất kì là do đúng k trọng tài điều hành.

Giả sử cho n=20 ta xét với giải ngoại hạng Anh.Tại mỗi vòng đấu thì có 10 trận đấu cùng giờ (tương ứng có 10 trọng tài cùng điều khiển 1 lúc ).Hãy tìm tất cả các số nguyên dương k để trong số 38 trận đấu của mỗi đội thì có đúng k trọng tài khác nhau điều khiển.
Chắc là bài toán sẽ thay đổi nhiều đấy