Toán 10 Cho m, n thuộc N*, m lẻ, gcd (m,n) = 1

[lilnuuu]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho m, n thuộc N*, m lẻ, gcd (m,n) = 1. Trên vòng tròn đặt n bóng đèn, mỗi bóng đèn hoặc sáng hoặc tắt. Mỗi lần được chọn m bóng đèn liên tiếp và thay đổi trạng thái của chúng. Chứng minh rằng: với mọi trạng thái ban đầu ta luôn có thể thực hiện hữu hạn thao tắt để tắt tất cả bóng đèn

 

[2712-0-3]

Cho m, n thuộc N*, m lẻ, gcd (m,n) = 1. Trên vòng tròn đặt n bóng đèn, mỗi bóng đèn hoặc sáng hoặc tắt. Mỗi lần được chọn m bóng đèn liên tiếp và thay đổi trạng thái của chúng. Chứng minh rằng: với mọi trạng thái ban đầu ta luôn có thể thực hiện hữu hạn thao tắt để tắt tất cả bóng đèn

lilnuuuVì [imath](m,n)=1[/imath] và [imath]m[/imath] lẻ nên [imath](m,2n)=1[/imath]
Theo định lý Bozu trong số học, do [imath](m,2n)=1[/imath], luôn tồn tại x,y nguyên dương thỏa mãn: [imath]mx = n.2y+1[/imath]
Ta sẽ chỉ ra cách để tắt 1 bóng đèn bất kì đang bật (gọi là X) như sau:
Chọn [imath]m[/imath] đèn liên tiếp, có đèn đầu tiên là đèn X. Thay đổi trạng thái rồi, chọn tiếp tục m đèn liên tiếp (sau m đèn vừa thay đổi) ....
Cứ như vậy, sau x lần thay đổi , ta thay đổi trạng thái các bóng đèn [imath]2y.n+1[/imath] lần, nên lần thứ [imath]x[/imath], m bóng đèn được thay đổi sẽ có đèn ở cuối là [imath]X[/imath].
Tức là: đèn [imath]X[/imath] được thay đổi [imath]2n+1[/imath] lần, còn các bóng đèn còn lại thay đổi [imath]2n[/imath] lần.
Vậy chỉ có đèn [imath]X[/imath] từ bật thành tắt.
Vậy áp dụng như thế hữu hạn lần, ta có điều phải chứng minh.
Mời bạn tham khảo thêm tại: [Lý thuyết] Chuyên đề HSG: Toán rời rạc

 

[7 1 2 5]

Ta chỉ cần chứng minh tồn tại cách thay đổi trạng thái các bóng đèn sao cho có đúng [imath]1[/imath] bóng đèn bị thay đổi trạng thái.
Hiển nhiên [imath]m=1[/imath] hoặc [imath]n=1[/imath] thỏa mãn. Xét [imath]m,n \geq 3[/imath]
Vì [imath](2n,m)=1[/imath] nên theo bổ đề Bezout, tồn tại [imath]2[/imath] số [imath]a,b \in \mathbb{N}^*[/imath] sao cho [imath]a\cdot 2n-b \cdot m=1[/imath]
Ta đánh dấu vòng tròn các bóng đèn từ [imath]1[/imath] đến [imath]n[/imath] theo chiều kim đồng hồ. Ta sẽ thay đổi trạng thái của bóng đèn số [imath]n[/imath] như sau:
Bắt đầu từ bóng đèn số [imath]1[/imath], ta thay đổi trạng thái [imath]m[/imath] bóng đèn liên tiếp. Tiếp đó, ta thay đổi trạng thái [imath]m[/imath] bóng đèn tiếp theo theo chiều kim đồng hồ cho đến khi thực hiện được đúng [imath]b[/imath] lần thay đổi trạng thái.
Khi đó, vì [imath]bm=2an-1[/imath] nên lần thay đổi trạng thái cuối cùng sẽ thay đổi trạng thái các bóng đèn từ [imath]n-m[/imath] đến [imath]n-1[/imath], tất cả các bóng đèn từ [imath]1[/imath] đến [imath]n-1[/imath] đều được thay đổi [imath]2a[/imath] lần nên giữ nguyên trạng thái, còn bóng đèn thứ [imath]n[/imath] sẽ chỉ thay đổi trạng thái [imath]2a-1[/imath] lần và sẽ thay đổi trạng thái so với ban đầu.

Nếu còn thắc mắc chỗ nào bạn hãy trả lời dưới topic này để được hỗ trợ nhé ^^ Chúc bạn học tốt ^^
Ngoài ra, bạn tham khảo kiến thức tại đây nhé
[Lý thuyết] Chuyên đề HSG: Toán rời rạc