Đến nội dung

Hình ảnh

Một bài toán phức tạp

- - - - -

  • Please log in to reply
Chưa có bài trả lời

#1
barcavodich

barcavodich

    Sĩ quan

  • Thành viên
  • 449 Bài viết

Một bài toán phức tạp

Có $n$ ngọn đèn $L_{0},L_{1},...,L_{n-1}(n>1)$ được đặt trên $1$ đường tròn.Ta dùng $L_{n+k}$ đẻ chỉ $L_{k}$.Ở mọi thời điểm,mỗi đèn có thể sáng hoặc bị tắt.Ban đầu tất cả đều sáng

Ta biểu thị các bước $s_0,s_1,...$ như sau :tại bước $s_i$ nếu $L_{i-1}$ đang tắt thì ta đổi chiều trạng thái của $L_i$ còn nếu $L_{i-1}$ đang sáng thì không làm gì cả

CMR

  • Tồn tại số nguyên dương $M(n)$ sao cho sau $M(n)$ bước thì tất cả đèn đều sáng
  • Nếu $n=2^k$ thì ta có thể chọn $M(n)=n^2-1$
  • Nếu $n=2^{k+1}$ ta có thể chọn $M(n)=n^2-n+1$

Bài viết đã được chỉnh sửa nội dung bởi barcavodich: 02-06-2013 - 22:30

[topic2=''][/topic2]Music makes life more meaningful





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh