Câu hỏi phỏng vấn (5)

Các câu hỏi kỳ này rất lý thú: câu 1-4 liên quan đến lý thuyết toán, câu 5-6 dẫn đến nhiều hướng suy nghĩ hay, câu 7-9 là các thuật toán thú vị!

Nguồn: Blog KHMT

  1. Giả sử

    f(x) = x^{x^{x^{\vdots}}} = 2

    (mũ x đến vô cùng). Vậy x bằng bao nhiêu?
    Ví dụ, ta có thể lý luận như sau. Dễ thấy rằng f(x) = x^{f(x)}. Do đó 2 = x^2, hay x = \sqrt{2}. Nhưng nếu f(x) = 4 thì, theo lý luận trên, 4 = x^4 cũng dẫn đến x = \sqrt{2}. Sao lạ thế? f(\sqrt{2}) = 2 = 4 à?

  2. Gọi S là một tập 10 số khác nhau giữa 1 và 100. Chứng minh rằng S có hai tập con không giao nhau với tổng bằng nhau.
  3. Có một tập hợp các điểm trên mặt phẳng. Không phải tất cả cùng nằm trên một đường thẳng. Chứng minh rằng có một đường thẳng chỉ đi qua hai điểm mà thôi.
  4. Có một cái đồng hồ mà kim giờ và kim phút giống hệt nhau. Có bao nhiêu thời điểm trong ngày mà nhìn đồng hồ này ta không thể biết được là mấy giờ?
  5. An và Bình thay phiên nhau chọn các số nguyên từ 1 đến 9. Số đã chọn không được chọn lại. Ai chọn được 3 số có tổng bằng 15 trước là thắng. Ai sẽ thắng?
  6. Bạn có 300 lít xăng và một cái xe tải. Xa tải chỉ chở được tối đa 100 lít xăng. Bạn muốn chở xăng đến bán ở chợ xăng cách khởi điểm 100 cây số. Vấn đề là xe tải chạy rất tốn xăng, mỗi cây số tốn 1 lít. Bạn được phép chở xăng để dọc đường rồi sau đó quay lại lấy để chở đi tiếp. Hỏi: Làm thế nào để bán được nhiều xăng nhất? (Nhớ là nếu bạn để xăng đâu đó dọc đường rồi quay lại lấy thêm xăng thì đoạn quay lại cũng tốn xăng.)
  7. Có 30 sinh viên đứng thành vòng tròn. Họ nhắm mắt lại. Giáo sư Tèo đội cho mỗi người một cái mũ. Tổng cộng có 20 mũ đen, 10 mũ trắng. Sau đó các sinh viên được quyền mở mắt. Họ thấy các mũ khác nhưng không biết mình đang đội mũ màu gì. Họ không được quyền trao đổi thông tin.
    Giáo sư Tèo nói: “Ít nhất một trong số các bạn đang đội mũ đen“.
    Sau đó giáo sư Tèo ra lệnh: “Sinh viên nào đã xác định được rằng mũ mình đang đội là màu đen thì ngồi xuống“.
    Dĩ nhiên, chẳng ai ngồi xuống vì không ai biết mình đang đội mũ màu gì.
    Một phút sau, giáo sư Tèo lập lại lệnh trước: “Sinh viên nào đã xác định được rằng mũ mình đang đội là màu đen thì ngồi xuống“.
    Vẫn không ai di động. Giáo sư Tèo lập lại lệnh này, mỗi phút một lần, trong vòng 30 phút kế tiếp.
    Câu hỏi 1: cái gì xảy ra? Khi nào?
    Câu hỏi 2: khi giáo sư Tèo nói “Ít nhất một trong số các bạn đang đội mũ đen” thì các sinh viên có thêm thông tin gì không? Vì rõ ràng là mỗi sinh viên đều biết là có mũ đen trong đám.
  8. Ta có n mẫu máu. Mỗi mẫu máu thuộc về một trong m nhóm máu. (Ta không biết chính xác m là bao nhiêu, và m không nhất thiết phải là hằng số.) Có một thiết bị mà nếu bỏ vào đó hai giọt máu từ hai mẫu máu khác nhau thì thiết bị sẽ cho biết hai mẫu máu có cùng nhóm máu hay không. Nếu bỏ vào thiết bị này hơn hai giọt máu thì câu trả lời không đáng tin cậy nữa.
    Ta muốn trả lời câu hỏi sau đây: có hay không hơn n/2 mẫu máu thuộc về cùng một nhóm máu. Dùng thiết bị trên để thử, làm thế nào để trả lời câu hỏi này với tổng số ít nhất các phép thử? (Chỉ cần ít nhất về mặt asymptotic là được.) Ví dụ: cách dễ nhất là thử tất cả các cặp mẫu máu nhưng như vậy cần dùng đến \Theta(n^2) phép thử.
    Ngoài ra, ta cũng giả sử rằng mỗi mẫu máu có khá nhiều giọt.
  9. Có N anh cướp biển sắp bị xử chém. Họ xếp thành một hàng dài. Mỗi người đội một chiếc nón, xanh hoặc đỏ. Cướp biển số 1 chỉ thấy nón (và màu nón) của cướp biển số 2, 3, … N; cướp biển số 2 chỉ thấy nón của số 3, 4, … N; vân vân. Dĩ nhiên, vì thế mỗi cướp biển không biết màu nón mình đang đội và màu nón của các cướp biển đứng trước mình trong hàng.
    Đao phủ bắt đầu chém từng cướp biển một, từ số 1 đến số N. Tuy nhiên, trước khi chém mỗi cướp biển thì đao phủ cho hắn một cơ hội: đoán màu nón của mình. Nếu nói đúng màu nón thì được tha. Tất cả các cướp biển đều nghe thấy nhau trả lời, nhưng không biết ai bị chém ai không.
    Trước hôm ra xử bắn, bọn cướp biển họp lại và tìm một thuật toán trả lời để cho tổng số cướp biển bị chém là ít nhất trong trường hợp tệ nhất (in the worst case). Ví dụ: nếu cướp biển số 2k-1 trả lời bằng màu nón của cướp biển 2k, và cướp biển 2k lập lại câu trả lời này, thì tệ nhất cũng chỉ có một nửa số cướp biển bị chém.
    Nếu bạn là cướp biển thì bạn thiết kế thuật toán thế nào?

2 responses to “Câu hỏi phỏng vấn (5)

  1. Câu 1. Giải x = sqrt(2), không đồng ý … he he
    Câu 2. Đi từ việc hình thành S (chưa nhất thiết phải lên đến 10 số đâu) sao cho không tồn tại 2 tập con có tổng bằng nhau :
    -Lấy S có 2 số đầu tiên là 1 và 2
    ===>>> S thể hiện các số 1,2,3
    tiếp số 4, (S = 1,2,4)
    ===>>> S thể hiện các số 1,2,3,4,5,6,7
    tiếp số 8, (S = 1,2,4,8)
    ===>>> S thể hiện các số 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
    tương tự, ta sẽ thấy
    số thứ 5 là 16,
    số thứ 6 là 32,
    số thứ 7 là 64,
    số thứ 8 là 128>100
    vậy S chỉ có thể có 7 số là tối đa
    Đề bảo chọn S 10 số, => không thể (8 là mếu rồi chứ đừng nói 10)

    Vậy chứng minh xong

    Câu 3. Vẽ tam giác :))
    Câu 4. http://tuoitrecuoi.com/phorum/showthread.php?t=26461

    Câu 5. Đố thằng nào thắng, chít liền …
    Câu 6. 50 :))

    Câu 9. 2 bit 2

  2. Nice try, Thân :D!
    Câu 1. Vì sao x=căn(2) lại không đồng ý?
    Câu 2. Chứng minh trên áp dụng cho tập S = {1,2,4,8,16,32,64,x,y,z}, nhưng còn các tập S bất kỳ khác? Hơn nữa các tập con không giao nhau.
    Câu 3. Sử dụng giả thiết “tập hợp các điểm hữu hạn”.
    Câu 4. Tôi không tìm được lời giải thỏa đáng.
    Câu 6. Nhiều hơn 50 đấy😀.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s