Các số trên vòng tròn

[Admin]

1. 25 hòn sỏi đen và 25 hòn sỏi trắng được xếp thành vòng tròn. Chứng minh rằng có một hòn sỏi mà hai hòn hai bên (trái, phải) đều trắng.

2. Có n số thực nằm trên một vòng tròn với tổng không âm. Chứng minh rằng tồn tại một trong n số này, tạm gọi là số x, thỏa mãn điều kiện sau đây: với mọi k > 0 thì tổng của k số thực, kể từ x theo chiều kim đồng hồ, là không âm.

3. Giả sử ta có n số nguyên trên một vòng tròn. Ta được phép làm một phép biến đổi, gọi là “biến đổi tếu“, như sau: tìm 3 số (a,b,c) nằm kề nhau liên tục trên vòng tròn, trong đó b < 0, và đổi chúng thành (a+b, -b, c+b). Mệnh đề sau đây đúng hay sai: có thể gán n số nguyên vào một vòng tròn để ta có thể biến đổi tếu mãi mãi, không bao giờ bị kẹt.

Source: blog Khoa Học Máy Tính

[shinichi9htv]

Mấy bài này hay phết nhỉ?

1. Blog khoa học máy tính

2. trên vòng tròn, trong tất cả các tổng con các số liên tiếp, lấy thằng lớn nhất. Sỗ x là số đầu tiên của dãy này

3. trông có vẻ phức tạp, chưa nghĩ

[Khoa Tran]

Mình chưa có thời gian để suy nghĩ cụ thể nhưng bài 3 có lẽ sử dụng 1 invariant function, 1 kĩ thuật phổ biến cho những bài toán dạng này.

[dexter8310]

1. Giả sử không có hòn sỏi nào thỏa mãn --> ko tồn tại trường hợp 2 hòn sỏi lân cận đều trắng (1) Vì trắng và đen tương đương --> cũng ko tồn tại 2 hòn sỏi lân cận đều đen (2)
(1) + (2) --> các hòn sỏi phân bố thành các cặp cùng màu liên tiếp trên vòng tròn
--> tổng số sỏi trắng (và tổng số sỏi đen) phải chẵn --> sai vì 25 lẻ

[drew]

(2, -2, 2, -2) --> (0, 2, 0, -2) --> (-2, 2, -2, 2) --> ......

[dexter8310]

3. Đúng.
CM: Tổng của 3 số sau biến đổi ko thay đổi so với trước khi biến đổi (= (a+b) + (-b) + (c+b) = a+b+c ) --> tổng của tất cả các số trong vòng tròn không thay đổi .
Do đó nếu tổng của n số ban đầu < 0 --> luôn tìm được 1 số trong vòng tròn < 0 --> thực hiện được phép biến đổi tếu

[dexter8310]

2. Nếu trên vòng tròn ko có số âm --> đúng
Giả sử m là số (âm) nhỏ nhất trên vòng tròn. Tính tổng của k số liên tiếp theo chiều kim đồng hồ bắt đầu từ m, với mọi k: 0<k<n+1 (--> có n tổng).
Gọi D là tổng âm nhỏ nhất trong n tổng này (D <= m), thì số x phải tìm là số liền sau số hạng cuối của tổng D theo chiều kim đồng hồ

[Khoa Tran]

Originally Posted by dexter8310

3. Đúng.
CM: Tổng của 3 số sau biến đổi ko thay đổi so với trước khi biến đổi (= (a+b) + (-b) + (c+b) = a+b+c ) --> tổng của tất cả các số trong vòng tròn không thay đổi .
Do đó nếu tổng của n số ban đầu < 0 --> luôn tìm được 1 số trong vòng tròn < 0 --> thực hiện được phép biến đổi tếu

Cho dù tổng <0 nhưng nếu b=0 thì cũng bị mắc kẹt rồi

[dexter8310]

Originally Posted by Khoa Tran

Cho dù tổng <0 nhưng nếu b=0 thì cũng bị mắc kẹt rồi

Vẫn tồn tại 1 số < 0

[shinichi9htv]

@Dexter8310: Excellent answer

P.S: Mà sao dạo này ko thấy anh Dexter tham gia diễn đàn nữa nhỉ, admin Khoa thử hỏi thăm xem :-?