Thảo - Hải trình toán học - 019

Bài toán:

• Có 2025 tấm thẻ đặt trên bàn theo hàng ngang.
• Mỗi thẻ có 2 mặt: nửa màu cam, nửa màu xanh.
• Ban đầu có 19 thẻ có mặt màu cam úp ngửa (nửa cam trên).
• Mỗi lượt chơi, người chơi chọn đúng 100 thẻ liên tiếp và lật ngược tất cả các thẻ đó (mặt trên chuyển sang mặt dưới).
• Yêu cầu: Tìm cách lật sao cho tất cả 2025 thẻ đều có mặt nửa cam trên, và tìm số lần lật ít nhất.

Phân tích bài toán:

• Ban đầu, ta có 2025 thẻ.
• Mỗi thẻ có hai trạng thái: màu cam trên (ký hiệu 1) hoặc xanh trên (ký hiệu 0).
• Người chơi được chọn 100 thẻ liên tiếp (con đoạn dài 100 thẻ) để lật.
• Việc lật một đoạn thẻ dài 100 thẻ chính là thay đổi trạng thái của 100 thẻ từ 0 sang 1 hoặc từ 1 sang 0.
• Bài toán trở thành: Từ một chuỗi 0-1 (ban đầu có 19 thẻ màu cam ngửa = 1, còn lại là 0), sử dụng thao tác đảo trạng thái trên đoạn dài 100 thẻ, để biến toàn bộ thành 1 (tất cả 2025 thẻ đều màu cam trên).

Có thể giải bằng cách nào?

Ý tưởng giải:

1. Khởi đầu ta có chuỗi với trạng thái "bán" (0 hoặc 1).
2. Từ trái sang phải, ta soi từng vị trí:
3. • Nếu tại vị trí i, mảng đang có giá trị 0 (mặt xanh), thì ta phải lật bộ 100 thẻ bắt đầu từ i để chuyển thành 1.
   • Lật liên tục cho đến hết phần chuỗi 2025 - 100 + 1 (vì lần lật cuối cùng là trên 100 phần tử).
4. Nếu sau khi làm hết các thao tác đó, phần còn lại (từ vị trí 1926 đến 2025) đều là 1 thì thành công.
5. Nếu không thì không thể làm.

Cách làm tuyến tính hiệu quả (Thuật toán tham lam):

• Tạo một mảng trạng thái ban đầu của 2025 phần tử, 1 = cam trên, 0 = xanh trên.
• Duyệt từ i = 1 đến 1926:
• • Nếu mảng[i] = 0 (để đơn giản giả sử nhớ các thao tác lật đã áp dụng), ta lật 100 phần từ i đến i+99 (đổi 0 thành 1, 1 thành 0).
  • Ghi lại số lần lật.
• Cuối cùng, kiểm tra từ vị trí 1926 đến 2025 có còn bị 0 không.
• Nếu còn thì không thể làm được.

Câu hỏi trong đề bài:

• Sau một số lần lật như vậy, có thể tất cả 2025 thẻ đều có nửa trên màu cam được không? Nếu có thì hãy tìm cách lật để số lần lật ít nhất.

Kết luận:

• Vì thao tác mỗi lần lật luôn trên đoạn liên tiếp 100 thẻ,
• Và số thẻ là 2025 rất lớn, cho phép dùng phương pháp "tham lam" kiểu quét từ trái sang phải,
• Ta hoàn toàn có thể tạo ra một thuật toán để lật cho tất cả cùng màu cam nếu mọi thứ đảm bảo.

Mẫu code tham khảo bằng ngôn ngữ lập trình để làm rõ ý tưởng (Python):

# Giả sử arr: mảng 2025 phần tử, mỗi phần tử là 0 (xanh trên) hoặc 1 (cam trên).
# Bài toán: biến arr thành tất cả 1

def min_flips(arr):
    n = len(arr)
    k = 100
    flips = 0
    
    for i in range(n - k + 1):
        if arr[i] == 0:
            # Lật 100 phần tử từ i đến i+k-1
            for j in range(k):
                arr[i+j] = 1 - arr[i+j]  # đổi 0 thành 1, 1 thành 0
            flips += 1
    
    # Kiểm tra phần còn lại
    for i in range(n - k + 1, n):
        if arr[i] == 0:
            return -1  # Không thể làm được
    
    return flips

# Ví dụ khởi đầu:
arr = [0]*2025
for pos in range(19):  # 19 vị trí may mắn là cam trên
    arr[pos] = 1

print(min_flips(arr))

Tóm lại:

• Có thể làm được.
• Tối ưu số lần lật bằng cách duyệt từ trái sang phải, mỗi khi gặp thẻ xanh trên phải lật 100 thẻ từ vị trí đó.
• Nếu sau cùng không còn thẻ xanh nào thì trả lời "Có".
• Nếu còn thẻ xanh thì không thể làm.