Các câu hỏi phỏng vấn [35]
- Cho một ma trận vuông
chứa các số thực. Bạn được phép đổi dấu tất cả các số trên một hàng hoặc một cột bất kỳ, và đổi dấu kiểu đó bao nhiêu lần tùy hỉ. Có thể nào, sau một số hữu hạn các lần đổi dấu, biến ma trận này thành ma trận mà tổng mỗi hàng và tổng mỗi cột đều không âm?
- Mỗi mặt của một đa diện lồi có một con kiến bò. Kiến bò trên các cạnh của mặt, theo chiều kim đồng hồ. Mỗi con kiến bắt đầu ở một điểm tùy hỉ trên mặt của nó, và bò với vận tốc biến thiên tùy hỉ. Chứng minh rằng không có cách nào cho bọn kiến bò, mỗi con quay lại điểm khởi đầu của nó, mà không đụng vào nhau.
- Cho một thanh sô-cô-la kích thước
, gồm 
ô vuông. Ta muốn bẻ thanh này thành ô để chia cho trẻ con. Mỗi bước, chọn một mảnh bất kỳ và bẻ đôi miếng này dọc hoặc ngang theo ranh giới tự nhiên. Chứng minh bẻ kiểu gì cũng cần cùng số bước.
Chủ đề : Dành cho du học sinh, Vui - Giải Trí and tagged Đố. Bookmark the
permalink. Trackbacks are closed, but you can .
10 Comments
95. Gọi Smax là tổng giá trị tuyệt đối các phần tử ban đầu.
Ở mỗi bước ta chọn hàng, hoặc cột có tổng S nhỏ nhất. Nếu S >= 0 thì không tồn tại hàng/cột âm, ta kết thúc thuật toán. Nếu S < 0 ta đổi dấu và tổng các phần tử của ma trận sẽ được tăng thêm 2*|S|.
Do tổng các phần tử của ma trận không thể vượt quá Smax, nên số bước luôn hữu hạn (không thể lớn hơn 2xn). Vì vậy thuật toán trên đảm bảo đạt đến trạng thái không có hàng/cột âm.
97. Gọi f(m, n) là số bước bẻ thanh sô-cô-la m x n (m, n >= 1). Ta chứng minh f(m, n) = m x n – 1 (*).
f(1, 1) = 0. Giả sử (*) đúng với mọi (m’, n’) < (m, n) (nghĩa là m’ < m hoặc m’ = m và n’ < n).
Với mọi m’ (1 <= m’ < m), ta có 1 + f(m’, n) + f(m – m’, n) = m x n – 1.
Với mọi n’ (1 <= n’ < n), ta có 1 + f(m, n’) + f(m, n – n’) = m x n – 1.
Vậy f(m, n) = m x n – 1, không phụ thuộc cách bẻ.
96. Hình như là liên quan tới định lý mặt cầu tóc của tô pô. Thêm nữa là đặc trưng Euler.
97. Số miếng tối đa: mxn. Mỗi lần bẻ tổng số miếng tăng lên 1, vậy cần mxn-1 lần bẻ, bất kể thế nào.
Hi all,
Về bài 96, dùng đặc trưng Euler là đủ: F + V = E + 2 (*).
Phản chứng, giả sử lũ kiến đều bò về đích mà ko đụng nhau, ta có:
- Khi lũ kiến về đích, cho chúng bò ngược lại với vận tốc biến thiên ngược lại lúc trước, thì cũng sẽ về đích mà ko đụng nhau (1).
- Trên mỗi cạnh, luôn có đúng 2 con kiến bò trên đó ngược chiều nhau (tất nhiên là ko bò đồng thời) (2).
- Tại thời điểm bắt đầu, tồn tại 1 đỉnh mà tất cả các cạnh nối với đỉnh đó đều có kiến. (3). Thật vậy, giả sử ko tồn tại đỉnh nào như vậy. Tức là xét cả V đỉnh thì đỉnh nào cũng có ít nhất 1 cạnh ko có kiến trong số các cạnh nối với đỉnh đó.
Suy ra tổng số cạnh ko có kiến của cả đa diện là: P >= V * 1 = V.
Tổng số cạnh có kiến của cả đa diện là: Q = F (số mặt = số kiến)
Nhưng tổng số cạnh của đa diện lại là: P + Q >= V + F hay E >= V + F (mâu thuẫn với (*)).
Vậy (3) đúng, từ (2) suy ra các con kiến trên các cạnh nối với đỉnh này đang cùng bò lại gần đỉnh hoặc đang cùng bò ra xa đỉnh. Nếu là ra xa, từ (1) ta có thể cho chúng quay đầu để bò lại gần đỉnh mà ko ảnh hưởng gì.
Nói vui tí, rõ ràng trong tình huống này các con kiến “tiến thoái lưỡng nan”, ko có con nào dám bò đến đỉnh trước, vì phía cạnh kia luôn có 1 con kiến khác đang chờ “xử” nó.
Vậy giả thiết phản chứng là sai.
Lập luận từ việc đỉnh nào cũng có ít nhất một cạnh không có kiến trong số các cạnh nối với đỉnh đó dẫn đến tổng số cạnh không có kiến là P >= V*1 = V là không đúng bởi vì mỗi cạnh không có kiến nối với 2 đỉnh.
Bài 96 chắc phải có thêm điều kiện chứ cứ cho bọn kiến xếp hàng bò, con này bò xong về đến chỗ xuất phát rồi mới cho con sau bắt đầu bò thì gặp nhau bằng niềm tin à?
@Giang: bạn nhận xét rất đúng, mình vẫn đang suy nghĩ tiếp. Phải nói bài này khó nhằn thật đấy.
@Trung: đề bài thế là đúng rồi, vì nếu 1 con kiến về đích thì nó nằm yên ko bò nữa, và như vậy sẽ cản trở con kiến sau, con kiến sau cần phải đi qua cạnh đó rồi thì con kiến trước mới được về đích.
Câu 96:
PB chứng minh không chặt lắm theo cách thức sau:
Nhận xét 1:
Do tất cả các chú kiến di chuyển theo cùng chiều kim đồng hồ, do đó hai chú kiến cùng đi qua một cạnh của đa giác sẽ có chiều ngược nhau. Kết quả là không thể tồn tại hai chú kiến có xuất phát điểm cùng một cạnh đi hết mồt vòng trên mặt đa giác mà mỗi chú chiếm hữu mà không đụng nhau.
Nhận xét 2:
Hai chú kiến ở hai mặt kề nhau, giả sử có một chú nằm trên cạnh tiếp giáp của hai mặt. Nếu không đụng nhau sau khi đi hết một vòng thì đường đi của hai chú kiến tương đương đường đi của chú nằm trên cạnh không kế cận trên đường bao của hai mặt.
Lời giải:
Xét một đa giác bất kỳ trên đa diện lồi, giả sử đa giác này có n cạnh. Thì số chú kiến tối thiểu sẽ là n + 1 chú. Giả sử n chú không thuộc mặt này sau khi đi hết một vòng không cắt nhau thì đường đi của các chú kiến tương đương với đa giác ấy. Nói cách khác thì n chú kiến không đụng nhau có thể xem tương đương với một chú kiến đi trên đa giác này có chiều ngược chiều kim đồng hồ. Vì thế chú kiến thứ (n+1) thuộc về đa giác trên chắc chắn sẽ đụng độ với chú kiến này.