Puzzles for Programmers and Pros


Hôm trước tình cờ lên Amazon tìm vài quyển sách về các cuộc thi lập trình thì bắt gặp quyển sách này: Puzzles for Programmers and Pros. Là một người mê các loại câu đố (mặc dù không phải là người giỏi), mình tìm ngay ebook của nó và thấy nội dung cũng khá hay. Hôm nay xin phép được đưa lên blog bài đầu tiên trong quyển sách. Hy vọng sẽ có người quan tâm và cho ý kiến.

Đề bài: SWEET TOOTH
Jeremy và Marie cùng nhau chơi trò chơi chia bánh. Có hai chiếc bánh hình vuông giống hệt nhau được chuẩn bị cho trò chơi. Jeremy sẽ cắt chiếc đầu tiên thành hai phần, có thể bằng nhau, có thể không. Sau khi Jeremy cắt xong, Marie sẽ quyết định xem cô ấy sẽ chọn trước hay là để cho Jeremy chọn trước. Nếu Marie chọn trước, cô ấy sẽ lấy phần bánh lớn hơn. Nếu Marie chọn sau, cô ấy sẽ giả sử rằng Jeremy sẽ chọn phần lớn hơn.
Sau đó, Jeremy sẽ cắt cái bánh thứ hai thành hai phần (nên nhớ rằng 1 trong hai phần bánh có thể rất nhỏ nếu Jeremy muốn). Nếu Marie đã là người chọn trước ở cái bánh đầu tiên thì lần này Jeremy sẽ có quyền chọn trước phần bánh dành cho mình (và tất nhiên Jeremy sẽ chọn phần lớn hơn). Nếu Marie là người chọn sau ở cái bánh đầu tiên thì lần này Marie sẽ có quyền chọn trước phần lớn hơn.

Giả sử rằng Jeremy và Marie đều cố gắng để có thể lấy được nhiều bánh nhất, chiến lược tối ưu dành cho Jeremy sẽ là như thế nào?

*************************************************************************************************

Đáp án: Giả sử Jeremy chia cái bánh đầu tiên thành hai phần là f và 1-f (với giá trị nhỏ nhất của f là 1/2). Nếu Marie là người chọn đầu tiên và chọn phần f (phần lớn hơn) thì đến lượt cái bánh thứ hai, Jeremy sẽ có thể lấy toàn bộ cái bánh (Jeremy chia cái bánh thứ hai thành 2 phần với 1 phần là rất nhỏ, xem như là không đáng kể, khi đó phần lớn hơn được xem như là toàn bộ cái bánh). Như vậy, Marie sẽ nhận được f và Jeremy sẽ nhận được (1-f) + 1. Nếu Marie lấy phần nhỏ hơn của cái bánh thứ nhất (1-f), Jeremy sẽ lấy được nhiều bánh hơn bằng cách chia cái bánh thứ hai thành hai phần bằng nhau. Như vậy, tổng cộng Marie nhận được (1-f) + 1/2. Jeremy nhận thấy rằng cách tốt nhất mình cắt là sao cho f = (1 – f ) + 1/2  <=> f=3/4.  Nếu Marie chọn phần đầu tiên của cái bánh thứ nhất (3/4) thì Jeremy sẽ nhận được 1/4 cái bánh thứ nhất và toàn bộ cái bánh thứ hai. Nếu Marie chọn phần thứ hai của cái bánh thứ nhất (1/4) thì Jeremy sẽ có 3/4 của cái bánh thứ nhất và 1/2 cái bánh thứ hai. Trong cả hai trường hợp, Marie có tổng cộng 3/4 cái bánh, Jeremy có 5/4 cái bánh.

Giả sử nếu như Jeremy chia cái bánh đầu tiên thành hai phần mà phần lớn nhỏ hơn 3/4 của cái bánh thì Marie sẽ có nhiều hơn 1/4 của cái bánh đầu tiên (bằng cách chọn sau) và có 1/2 của cái bánh thứ hai, và số bánh nhận được lớn hơn 3/4 cái bánh (lớn hơn trường hợp tối ưu). Ngược lại, nếu Jeremy chia cái bánh đầu tiên thành hai phần mà phần lớn sẽ lớn hơn 3/4 thì Marie sẽ lấy phần này và có tổng cộng lớn hơn 3/4 số bánh (cũng lớn hơn trường hợp tối ưu).

Mở rộng: Jeremy và Marie lần này cùng nhau chia 3 cái bánh giống hệt nhau. Tuy nhiên, luật chơi có một chút thay đổi. Jeremy sẽ vẫn là người cắt bánh, nhưng Marie sẽ có hai lần lựa chọn trước, Jeremy chỉ có một lần. Như vậy, Jeremy cắt cái bánh đầu tiên. Marie sẽ quyết định chọn trước hoặc chọn sau. Sau đó, Jeremy cắt cái bánh thứ hai, và Marie lại là người quyết định là chọn trước hoặc chọn sau. Tương tự cho cái bánh thứ ba, nhưng Jeremy sẽ là người quyết định trước.

    1. Làm thế nào Jeremy có thể lấy được nhiều bánh nhất, quy luật là như thế nào? Jeremy sẽ nhận được bao nhiêu bánh?
    2. Giả sử có 7 cái bánh và Marie có quyền quyết định 6 trong 7 cái bánh. Ai sẽ là người có lợi và số bánh nhận được là bao nhiêu?
    3. Có cách nào đảm bảo rằng mỗi người đều nhận được số bánh bằng nhau, biết rằng Jeremy luôn là người cắt bánh?

Hẹn gặp lại vào bài toán tiếp theo!!!!

 

Tác giả: xuanchien

Tran Xuan Chien. Japan Advanced Institute of Science and Technology - Japan. Senior Developer - NUS Technology.

1 thought on “Puzzles for Programmers and Pros”

  1. 1. hai lần đầu chia đều ,lần thứ ba chia 1 to , 1 bé , tùy lòng tham mà J có thế lấy nhiều nhất có thể gần = 1 cái bánh.2. Tùy vào tấm lòng của J , trong trường hợp tham lam nhất số bánh mà J hơn M chỉ là gần bằng 1 cái bánh (nếu lòng tham cả hai người như nhau thì M chỉ lợi nhất là gần được 1 cái bánh , không bao h đạt được 1 cái )3. Never

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s