- (Câu này do anh Nghị gửi hôm qua.) Có 15 cái túi, cần ít nhất bao nhiêu hòn sỏi để mỗi túi chứa số hòn sỏi khác nhau?
- (Câu này lấy bên Puzzle Toad.) Có hai điểm A và B nằm trong hình vuông đơn vị. B có thể bắn một tia laser ra theo hướng tùy thích. Tia laser này nếu đụng vào cạnh của hình vuông thì sẽ phản xạ lại (như phản xạ ánh sáng tuyệt hảo). A có quyền rải “vệ sĩ” trong hình vuông, mỗi vệ sĩ là một điểm trong hình. Nếu tia laser từ B bắn ra đi qua một vệ sĩ thì nó bị dừng lại (và vì thế không trúng A).
A cần bao nhiêu “vệ sĩ”, và đặt ở đâu, để cho không có bất kỳ tia laser nào từ B có thể bắn trúng A. Một số hữu hạn các vệ sĩ có đủ không?
17 Comments
Em xin trả lời câu 1.
Có 15 cái túi, mỗi túi đựng số viên sỏi khác nhau, cho nên minimum sẽ là đựng lần lượt 0, 1, 2, …, 14. Như thế phải có ít nhất 14 viên sỏi được dùng. Bây giờ ta cho mỗi túi đựng 1 viên trừ túi thứ nhất. Sau đó làm như sau: lấy túi 1 bỏ vào trong túi 2, lấy túi 2 bỏ vào trong túi 3, … túi 14 bỏ vào trong túi 15. Như thế số viên sỏi trong các túi lớn sẽ được cộng dồn từ các túi nhỏ và tạo thành dãy 0, 1, 2, …, 14 (túi 1 đựng 0 viên, túi 2 đựng 1 viên, túi 3 đựng 2 viên gồm của chính nó và của túi 2, …, túi 15 đựng 14 viên gồm của chính nó và các túi trước). Vậy cần nhỏ nhất 14 viên sỏi.
Lâu rồi mới thấy anh Hưng đăng các câu hỏi phỏng vấn
Câu 1 Tuấn Anh giải khéo léo quá!
Câu 2, A rải luôn một vệ sĩ nằm trùng với B thì B có bị “tịt ngòi” luôn không nhỉ?
@ Tuấn Anh: chính xác!
@ Hoàng: nếu vệ sĩ đặt ở B thì tia laser không “đi qua”, và vì thế không bị chặn.
Câu 2 em giải thế này:
Kí hiệu các mặt phẳng chứa cạnh hình vuông là MP1, MP2, MP3, MP4, MP5 (trùng với MP1), … MP(n) trùng với MP(n mod 4). Gọi B1 là đối xứng của B qua MP1, B2 là đối xứng của B1 qua MP2, … B(n) là đối xứng của B(n-1) qua MP(n).
Như thế ta có cách xây dựng 1 tia phản xạ n lần từ B bắn trúng A như sau: Nối A với B(n) cắt MP(n) tại điểm C(n), nối C(n) với B(n-1) cắt MP(n-1) tại C(n-1), …, nối C2 với B1 cắt MP1 tại C1, khi đó tia sáng từ B chiếu tới C1 sẽ bị phản xạ tới C2, C3, … C(n) và tới A.
Theo cách xây dựng trên, ta chỉ quan tâm tới hướng của tia cuối cùng, tức B(n) tới A. Nếu ta chỉ ra được 1 dãy các điểm B(k) sao cho số các hướng của từng điểm tới A là vô hạn và không trùng nhau thì điểm A sẽ không cách nào phòng bị được.
Để ý rằng 2 lần phép đối xứng trục bằng 1 phép đối xứng tâm, 2 lần đối xứng tâm được 1 phép tịnh tiến. Như thế tức sau 4 lần đối xứng trục ta có 1 phép tịnh tiến. Nghĩa là điểm B4 là tịnh tiến của B, B8 là tịnh tiến của B4, … Lưu ý luôn là vecto tịnh tiến bằng 2 lần đường chéo của hình vuông. Do đó các điểm B(4k) sẽ nằm cách đều nhau trên 1 đường thẳng.
Từ đây suy ra, nếu A không nằm trên đường thẳng qua B và song song với đường chéo chứa vecto tịnh tiến đó thì các đường nối A với các điểm B(4k) sẽ có hướng khác nhau, suy ra A sẽ bị bắn chết. Nếu A nằm trên đường thẳng đó, thì ta chỉ cần thay đổi thứ tự các MP đối xứng, thay vì MP1, MP2, … sẽ là MP2, MP3, …, lúc này nhận được các điểm B(4k) nằm trên đường thẳng song song với đường chéo còn lại, nên A cũng sẽ bị xử vì không nằm trên đó.
Chỉ còn trường hợp cuối cùng, khi A nằm cùng lúc trên cả 2 đường thẳng đó, tức là trùng với B. Bài toán trở thành liệu điểm B có bảo vệ được chính mình?
Trường hợp này em chưa xử lí được, nên nhờ mọi người giải quyết nốt.
Câu 83 và câu trả lời của Tuấn Anh lại một lần nữa được xử lý theo “kiểu Trạng Quỳnh”. Ai cũng biết đơn giản thì số sỏi ít nhất sẽ là: 0+1+2+…+14. Theo câu trả lời của TA, nếu như các túi không lồng được vào nhau thì sao?
Thiết nghĩ, những câu hỏi thế nào ko nên đưa lên blog KHMT.
Coi các cạnh là gương phẳng.
Ảnh của A qua các gương là vô số nên B có vô số hướng để bắn trúng A. Do đó không thể đặt một số hữu hạn các vệ sỹ được.
Em nghĩ là thế
Bác Đức ơi,
Tôi mà là manager đi phỏng vấn tuyển programer, nếu tôi lấy lời giải chuẩn là cái “ai cũng biết là đơn giản” ấy thì thằng programer giỏi nó sẽ coi thường công ty tôi. Thế mới là KHMT. Bao giờ lời giải này đăng trên blog kiểm toán hay hành chính công bác chỉ trích cũng chưa muộn.
Đáp án câu 83 như bạn Tuấn Anh rõ ràng không thỏa mãn trong mọi trường hợp .
@Trung T. Nguyen : Cho em hỏi là chả nhẽ sĩ diện công ty quan trọng hơn mục tiêu kiếm programer giỏi sao ?
Hà hà,
Một số bác có vẻ không “hài lòng” với câu trả lời này nhỉ? Trong ngữ cảnh của một cuộc phỏng vấn thì rất đơn giản: người được hỏi có thể hỏi ngược lại rằng “các túi có lồng vào nhau được không?” và các câu hỏi tương tự.
Còn nếu cần “thỏa mãn trong mọi trường hợp” thì đáp án 1+…+14 cũng không đúng. Nhỡ mỗi viên sỏi to bằng quả núi thì sao
Bản thân câu trả lời là gì không quan trọng bằng việc mình xử lý tình huống, giải quyết vấn đề như thế nào.
bolzano_1989
Thằng programmer giỏi không bao giờ nghĩ là nhỡ cái túi thế này cái túi thế khác nên lời giải này sai ta đừng đưa ra nữa. Chỉ có thằng kiểm toán giỏi hay thằng chuyên duyệt giấy phép xây dựng giỏi mới hay cứng nhắc thế thôi. Như bác Hưng đã viết, mấy cái bài này không chủ yếu nhằm xem thằng nào suy luận như parser, mà xem thằng nào có năng khiếu giải quyết vấn đề.
Cảm ơn mọi người
.
@bác Hưng: sỏi nào to bằng quả núi nhỉ? Thường thì khi ra bài toán, sẽ có một số assumption mà người ra đề và người giải đã ngầm thoả thuận. Ngược lại, việc ra đề sẽ mất rất nhiều câu để định nghĩa mọi thứ.
@bác Trung: em thấy thằng programmer nào mà nó xử lý theo kiểu “trạng Quỳnh” là em cho điểm trừ ngay. Bác muốn “cty ko bị coi thường” thì ra câu khác hơn, đánh vào khả năng của programmer.
Cuối cùng, vì đây là câu hỏi phỏng vấn nên có thể nói trả lời vô tội vạ, chủ yếu là cách nói như thế nào, tâm lý của interviewer thôi.
Chúc các bác sức khoẻ.
Câu hỏi này được hỏi ở phỏng vấn nào đấy ạ?VÀ đáp án cuối cùng là gì?Anh Hưng ghi câu hỏi mà chẳng đưa ra được câu trả lời khiến mọi người tâm phục gì cả!
Tôi sưu tầm câu hỏi không phải là để khoe mình thông thái, và cũng không phải để thách thức ai cả. Các bạn thấy thú vị thì nghĩ lời giải và bàn luận, không thì thôi. Tại sao lại phải tâm phục khẩu phục gì?
Vấn đề ở đây chỉ là cách diễn đạt và cách hiểu thôi. Mục đích của cuối của em vẫn là biết được câu trả lời chính xác của câu hỏi đó. Phải chăng câu hỏi đó chỉ để kiểm tra khả năng phản biện cách trả lời và việc giải thích được cách trả lời một cách hợp lý không ạ?
Em vừa đỗ cao học máy tính ĐHQG hà Nội, Đăng kí chuyên nghành KHMT. Đăng kí học xong thì mấy thằng bạn bảo là không nên học nghành này vì nghành này được đào tạo theo chuẩn quốc tế, học rất vất vả và tính ứng dụng của nó không cao lắm vì vậy mà sẽ không có nhiều thời gian để làm ngoài. Thực ra chính vì theo chuẩn QT nên em cũng muốn thử sức mình hơn, mong là sẽ là động lực để mình cố gắng. Nhất là em cũng muốn trình độ tiếng anh của mình sẽ nâng cao hơn. Nhưng cũng đang lo là sở thích của mình sẽ không được vì thứ 7 này không biết có qua được vòng phỏng vấn không.Ai có biết thông tin gì về các câu hỏi của vòng phỏng vấn bên ĐHQG Hà nội ko ạ?
chú em cứ yên tâm hỏi dễ không ý mà! Trước anh cũng lo như chú nhưng chẳng có gi` cả!