(Cảm ơn anh Nghị gửi câu 98 rất hay!)
- Cho một đồ thị, mỗi đỉnh có một bóng đèn và một công tắc. Chuyển trạng thái công tắc ở một đỉnh thì sẽ dẫn đến sự đổi trạng thái của bóng đèn ở đỉnh đó và tất cả các bóng đèn ở các đỉnh kề với đỉnh đó. Hỏi: nếu lúc đầu tất cả các bóng đèn đều tắt, thì có cách nào bật tất cả các bóng đèn với một đồ thị bất kỳ không?
- Có 2n+1 đôi bóng trong một bảng cúp thế giới. Mỗi đội chơi một trận với tất cả các đội còn lại. Một vòng tam giác là một bộ 3 đội A, B, C mà A thắng B, B thắng C, và C thắng A. Hỏi: số vòng tam giác tối thiểu phải là bao nhiêu? Số vòng tam giác tối đa có thể có là bao nhiêu?
- 25 nghị gật ngồi quanh bàn tròn, bỏ phiếu (yes hoặc no) cho các luật lệ nghị quyết nghị định. Anh nghị gật nào cũng bỏ phiếu như sau: ở lần bỏ phiếu thứ n+1, nghị gật bỏ phiếu giống như phiếu thứ n nếu như phiếu thứ n của anh giống với ít nhất một trong hai phiếu thứ n của hai anh bên cạnh; nếu không thì phiếu thứ n+1 của nghị gật sẽ ngược lại với phiếu thứ n. Hỏi: chứng minh rằng bất kể phiếu đầu tiên bỏ thế nào, sau một khoảng thời gian hữu hạn các nghị gật sẽ không đổi trạng thái phiếu nữa.
Thế là bộ các câu hỏi phỏng vấn đã đạt đến số 100! Khi nào đến số 1000 thì tôi ngưng 
7 Comments
Câu 98. Tôi nghĩ là không. Ví dụ đồ thị có 2 đỉnh và 1 cạnh.
- Đáp án trước là sai (tôi tưởng là bắt đầu với 1 trạng thái bất kỳ).
- Nếu bắt đầu với trạng thái tất cả bóng đền đều tắt ta chỉ việc tới mỗi đỉnh bậc chẵn chuyển công tắc một lần là có thể bật được tất cả các bóng.
Duc: vẫn sai.
Câu 98: Ta làm thế này ạ. Đánh số các đỉnh là 1, 2, …, N . Tại mỗi đỉnh k, tập hợp các đỉnh kề k cộng thêm chính k, ký hiệu là A(k). Ta cần tìm tập hợp S là tập con của 1, …, N có tính chất, ta gọi là tính chất M: giao của S với A(k) bất kỳ có số phần tử là lẻ. Ta đếm số các tập không như thế, nghĩa là số những tập S mà tồn tại đỉnh k để giao của S với A(k) là chẵn. Ta có thể đếm và chứng minh là số tập S như vậy không vượt quá 2^N – 1 (cái này không khó lắm, chỉ là em gõ công thức toán ở đây không được). Tập 1, .., N có 2^N tập con, vậy tồn tại tập con có tính chất M.
Ta bấm lần lượt các công tắc của tập S đó lên, sẽ làm sáng tất cả các bóng đèn.
Câu 98 :
Nhận xét 1: Nếu bài toán có nghiệm thì với mỗi công tắc tại 1 đỉnh chỉ cần bật 1 lần hoặc không bật lần nào (không cần bật/tắt quá 1 lần).
Nhận xét 2:
Với mỗi đỉnh u ta gọi số lần bật/tắt đèn tại đỉnh u đó là C(u) ( C(u) nhận 2 giá trị 0 hoặc 1 tương ứng vào nhận xét 1).
Ta có trạng thái đèn tại đỉnh u sau khi dừng hết quá trình bật/tắt sẽ là C(v1) xor C(v2) xor C(v3) … xor C(u) = G(u)
với v1, v2, v3 … là các đỉnh kề với đỉnh u và G(u) = 1 nếu đèn tại u sáng và = 0 nếu đèn tại u tối.
Ban đầu các đèn đều tối hết và mục tiêu là để các đèn sáng hết –> G(u) sẽ phải = 1 với mọi u.
Từ 2 nhận xét trên ta quy bài toán này về bài toán giải hệ phương trình nhị phân bậc nhất N ẩn, có thể giải = khử Gauss.
Hệ PT có dạng
C(v1,1) xor C(v1,2 ) xor … xor C(v1,k1) xor C(1) = 1
…
C(vn,1) xor (Cvn,2) xor … xor C(vn,kn) xor C(n) = 1
Cấp độ của thuật toán là O(N^3).
Cau 100:
Binh thuong khi 2 phieu YY / NN canh nhau thi se stable (khong bao gio thay doi trang thai). Neu co mot phieu ben canh, ma phieu do (gia su la Y) nam giua 2 phieu khac loai (tuc la NYNN hoac NNYN) thi phieu Y do se bi convert thanh N va sau do khong thay doi trang thai nua. Nhu vay vung cac phieu giong nhau lien ke nhau se expand neu ben canh co 1 phieu khac loai bi co lap. Cuoi cung ca ban tron se stable khi khong con phieu co lap nao nua.
Co 1 truong hop ngoai le co ve nhu bai toan sai. Do la khi cac phieu nhan gia tri alternative YNYN. Sau moi luot tat ca cac phieu deu doi gia tri, va se cu nhu vay khong bao gio dung lai.
@Hung: Truong hop ngoai le ban noi’ khong xay ra, vi chung’ ta co’ mot so le? cac’ cu. nghi. gat. ^^