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

nút 2
thayđổi trạng thái của tất cả các ngọc đèn mang số lẻ.
nút 3
thayđổi trạng thái của tất cả các ngọn đèn mang số chẵn.
nut 4
thayđổi trạng thái của tất cả các ngọn đèn được đánh số dạng 3K+1(với K≥0), ví dụ: 1,4,7,
…
Cómột chiếc máy đếm C ghi lại tổng số lần bấm nút.
Khi buổi dạ tiệc bắt đầu, tất cả các đèn đều ở trạng thái ON vàmáy đếm C được đặt ở 0.
Bàitoán Cho trước giá trị đếm máy C ghi đượcvà thông tin trạng thái cuối cùng của một số
ngọn đèn. Hãy viết chươngtrình xác định trạng thái cuối cùng có thể (không lặp lại) của
Nngọn đèn theo thông tin cho trước.
Input File PARTY.IN chứa bốn dòng: số ngọn đèn N, số lần bấm đèn C và trạng thái
cuốicùng của một số ngọn đèn.
Dòng đầu tiên chứa số N và dòng thứ hai chứa giá trị cuối cùng máyđếm C ghi nhận. Dòng
thứ ba chứa số ngọn đèn ở trạng thái cuối cùnglà ON, các thông tin được ngăn cách bằng
ký tự trống, cuối dòng cósố nguyên -1. Dòng thứ tư chứa số ngọn đèn ở trạng thái cuối
cùnglà OFF, các thông tin cũng được ngăn cách bằng ký tự trống và kếtthúc bằng số
nguyên -1.
party.inp
10
1
-1
7 -1
Trong ví dụ này có tất cả 10 ngọn đènvà chỉ một nút đã được bấm. Ngọn đèn số 7 ở trạng
thái cuối cùnglà OFF.
Output File PARTY.OUT phải chứa tất cả các trạng thái cuối cùng (không lặp lại) có thể
củatất cả các ngọn đèn. Mỗi trạng thái phải được thể hiện trên mộtdòng riêng. Các trạng
thái có thể được sắp xếp tuỳ ý.
Mỗi dòng có N ký tự trong đó ký tự đầutiên chỉ trạng thái của ngọn đèn số 1 và chữ số cuối


+ C
4
2
+ C
4
4
=1+6+1=8; một con số khá
nhỏ?.
Talập sẵn tất cả các tổ hợp các cách nhấn:
A*={{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},
{2,3,4},{1,2,3,4}}
Vớimỗi Ai với |Ai|=c, ta lần lượt biến các bóng đèn đã cho trước trạngthái (ban đầu là toàn
ON) xem có phù hợp hay không. Nếu đúng, ta ghinhận.
Bàitoán 3 : Xoayđồng hồ (Vô địch Hunggary 1991)
Đề:
Cho 9 cái đồng hồ,mỗi cái có 4 trạngthái chỉ giờ: 0,3,6,9 (hình 1) đánh số từ 1 đến 9
Cho 9 cách quay bộ đồng hồ như hình 2, dượcđánh số từ 1 đến 9 từ trên xuống, từ trái qua
phải. Các ô bôi đenxác định đồng hồ tương ứng sẽ quay kim giờ 1 góc 90 độ.
Ví dụ cách chọn sẵn ở hình 2 gồm cácđồng hồ 1,2,4,5.
Cho trước 1trạng thái của bộ đồng hồ, hãy xác lập 1 số ít nhất số lần biếnđổi để đưa tất cả
các đồng hồ về 0 giờ.
Trongfile dongho.inp gồm trạng thái của 9 cái đồng hồ (0..3 tương ứng0,3,6,9 giờ).
output
Trongfile dongho.out gồm:
- dòng đầu tiên là số lần biến đổi N.
- N dòng tiếp theo lần lượt là số hiệu của các cách nhấn.
ví dụ:
dongho.inp
1 0 1

đứng trước số0 (0 giờ).
Đầu tiên, ta tạo cho các đồng hồ cáckhoảng cách tương ứng với đồng hồ 1 độ lệch cố định
nào đó (từ 0 đến 3) với cấu hìnhB, gọi là cấu hình D.
ví dụ:
với B= 2 3 0
1 1 0
1 0 3
thì ta có thểđưa về: D= 1 2 3
0 0 3
0 3 2 { Mỗiđồng hồ thuộc D đều trễ hơn so với B 1 góc vuông }
bằng cách thayđổi từng khoảng cách của từng đồng hồ một bởi các tổ hợp cách:
Đồng hồ 1:2 4 9
-----------2 :1 2 3 4 5 6 8 8
-----------5 :2 4 6 8 1 9
tương tự cho cácđồng hồ còn lại.
Sau khi đã cóD, ta lại xét các trường hợp khoảng cách D và B, dựa vào đó, tasẽ san bằng
khoảng cáchgiữa B và D bằng tổ hợp biến đổi:
Kcách = 0: {}
-----------1: { 11 1 2 2 3 3 3 4 4 5 5 5 6 6 7 7 7 8 8 9 9 } (1) /* Ta sử dụng trình quay lui để
tính giùm bước này*/
-----------2: { 11 3 3 5 5 7 7 9 9 } (2) /* Ta gấp 2 và đơn giản cấu hình (1) */
-----------3: { 12 2 3 4 4 5 6 6 7 8 8 9 } /* ởđây ta cộng gộp đơn giản (1) và(2), rồi đơn giản
*/
Vậy là ta đã cócấu hình B, tập hợp tất cả các cách biến đổi trên lại thành tập E, đơngiản E
ta được C. Bổ đề số 3 đã được chứng minh xong.
Như vậy, ta có sựánh xạ song ánh từ tập 4
9
cách biến đổi đến 4
9
cấu hình bộ đồng hồ.