Bài toán mệnh đề và biến đổi

Mệnh đề và một số bài toán biến đổi

Lê Trần Hoài Nam

Cácbạn thân mến! Qua các cuộc thi, hẳnta đã tiếp xúc khá nhiều bài toán mang tính chất

biến đổi trạng thái,để đưa trạng thái nguồn về trạng thái đích. Lối giải quyết thườngmù

tịt. Để giải chúng, ta cần trải qua một số nhận xét, mà tôi tạmgọi là bổ đề. Việc tìm ra

mệnh đề bổ trợ sẽ soi sáng đường chochúng ta đi đến kết quả, có thể là chặt bớt nhánh

trong một rừng tìmkiếm, có khi là tìm điều kiện tồn tại nghiệm, và đôi khi chúng còngiúp

bạn đến cỡ 90% bài toán. Chúng tra hãy cùng lướt qua một số vídụ.

Bàitoán 1 : Lưới đèn (Đề toàn quốc 1995)

Đề:

1lưới đèn N*N bóng ,mỗi bóng có 2 trạng thái: sáng (1) và tắt (0). Vídụ 1 trạng thái của

lưới với N=3.

1 0 1

1 1 0

0 0 1

Mỗihàng và cột đều có 1 công tắc. Khi ấn sẽ thay đổi trạng thái của tấtcả các bóng (0 →1,

1 → 0)trên hàng (cột) đó.

Nhiệmvụ là phải biến đổi 1 trạng thái nguồn thành trạng thái đích qua 1số ít nhất S lần biến

đổi.

Dữliệu cho trong file ′battat.inp′ cho số N và trạng thái đầu A, trạngthái đích B, kết quả in

ra ở file ′battat.out′ gồm số S và các bướcbiến đổi. Nếu không thể biến A thành B, S = -1.

Vídụ:

Battat.inp 3

10 1

11 0

00 1

00 0

10 0

01 1

Battat.out

2

h1c2

Giải:

Trướchết ta có đưa ra vài bổ đề:

1/ số cách ấn mỗi cách tối đa là 1.

2/ thứ tự các cách ấn là không quan trọng.

3/ nếu A[i,j]=B[i,j] thì nếu cách nhấn hàng i song hành với cáchnhấn cột j (i=1..m,j=1..n)

vàngược lại.

Dođó ta sẽ phân hoạch được tập A={hàng 1, hàng 2,.., hàng N, cột 1, cột2,..,cột N} thành 2

tập con (trong trường hợp có đáp án cho bài toán, tứcS ≠-1).