Vấn đề chia sẻ

28

KVANT 2008/№4

Ban giám khảo cuộc thi cũng ghi nhận thành tích tốt của nữ sinh Oksana Galyamova, Beloretsk, thể dục 14, lớp 8.

và các nhóm sau: Trung tâm Giáo dục thường xuyên, Nizhnekamsk, người đứng đầu F.G. Kalimullina,

Lyceum 64, Omsk, đạo diễn Yu.E. Ryazanova.

Tất cả những người chiến thắng cuộc thi đều được trao tặng DVD - kho lưu trữ điện tử của tạp chí «Kvant» từ năm 1970 đến năm 2006.

Chia sẻ vấn đề

V.UFNAROVSKY

WA BRIGATORS CHIA LOOT. CHƠI RẤT hay và dễ dàng, nhưng việc chia sẻ hóa ra lại khó khăn hơn nhiều! Mỗi tên cướp đều chắc chắn rằng mình là người có thể chia đều mọi thứ nhưng lại hoàn toàn không có niềm tin vào khả năng của đồng đội. Cuối cùng, người lớn tuổi nhất trong số họ nói: “Được rồi.” Tôi có một ý tưởng. Hãy để tôi cố gắng chia đều chiến lợi phẩm. - Nhưng anh không biết làm thế nào! - người trẻ hơn hét lên.

Minh họa của V. Ivanyuk

29

ĐẾN

“Chờ một chút,” trưởng lão trả lời và chia mọi thứ làm đôi. – Tôi nghĩ mình đã chia nó hợp lý. Bạn có đồng ý không? - Tất nhiên là không. Đây là những phần hoàn toàn không bằng nhau! - Cứ như vậy đi. Và bạn nghĩ phần nào lớn hơn? - Cái này! – tên cướp trẻ tuổi chỉ ra không chút do dự. - Tuyệt vời! Đưa cô ấy đi. Bạn có hài lòng không? - Tất nhiên rồi! Và bạn? - Không còn nghi ngờ gì nữa. Tôi chắc chắn rằng cả hai phần đều giống nhau: suy cho cùng, chính tôi đã chia chúng. Bọn cướp giải tán, hài lòng với sự phân chia. Lần tiếp theo có ba người trong số họ. Và một lần nữa cần phải chia đều chiến lợi phẩm, nhưng lần này là cho ba người. Làm thế nào để làm điều này? Lúc đầu, tên cướp cấp cao cố gắng sử dụng ý tưởng tương tự. Anh ta chia mọi thứ thành ba phần bằng nhau (đối với anh ta dường như) và mời những tên cướp khác chọn phần của chúng. Anh cả hy vọng rằng họ sẽ chọn những phần khác nhau - sau đó anh ấy sẽ chọn phần còn lại, và mọi người sẽ vui vẻ. Nhưng cả hai đồng nghiệp của anh đều muốn có cùng một phần. “Được rồi,” anh nói. – Vì cả hai bạn đều nghĩ đây là phần lớn nhất nên hãy chọn phần nhỏ nhất. Tôi sẽ tự mình giải quyết và các bạn sẽ tự giải quyết bằng cách nào đó. Đó là một ý tưởng hay, nhưng thật không may, giờ họ đã chọn những phần khác nhau. Và không ai khác biết phải làm gì. Có những cuộc tranh cãi, rồi những tiếng súng… Cảnh sát xuất hiện nhanh chóng một cách đáng ngạc nhiên, và bọn cướp vui mừng vì đã trốn thoát được. Nhưng cả ba vẫn tiếp tục suy nghĩ: làm sao có thể chia chiến lợi phẩm một cách công bằng để mọi người đều chắc chắn rằng mình nhận được ít nhất một phần ba (ngay cả khi mọi người có quan điểm khác nhau về một phần ba chiến lợi phẩm là gì và đâu là không)? Lần sau có mười tên cướp. Nhưng bây giờ họ phải chia chiến lợi phẩm thành 10 phần! Người lớn tuổi nhất nói với những người còn lại rằng việc chia thành ba phần khó khăn như thế nào và đề nghị: “Tôi nghĩ chúng ta cần gọi một nhà toán học, nếu không chúng ta sẽ không thể giải quyết được”. Tôi có một người bạn tốt. – Tôi có phải trả tiền cho anh ta không? – những người còn lại nhăn mặt. - Không, không, anh ấy sẽ làm miễn phí. Anh ấy rất thích giải quyết khó khăn bài toán. Và anh ấy sẽ rất vui nếu có thể viết một bài báo toán học về điều này. - Không có tên của chúng tôi? - Không có. “Vậy thì để anh ta thử xem,” bọn cướp miễn cưỡng đồng ý. Nhà toán học thực sự quan tâm đến vấn đề này. Sau khi suy nghĩ, anh ấy đề xuất như sau lời giải. “Bọn cướp,” anh ấy bắt đầu, “mỗi người trong số các bạn có chắc chắn rằng anh ấy (và chỉ mình anh ấy) biết 1/10 số rác rưởi này là bao nhiêu không?” “Tất nhiên,” họ xác nhận có phần bị xúc phạm. - Tuyệt vời! Sau đó, anh,” anh ta chỉ vào một trong những tên cướp, “tách 1/10 số này ra.” - Anh vâng lời. “Bây giờ là bạn,” anh chỉ vào người kia. – Bạn có nghĩ là hơn 1/10 không?

M

Sh

“Không,” tên cướp trả lời. - Tuyệt vời! Vậy thì bạn,” anh ta chỉ vào cái tiếp theo. – Bạn có nghĩ nó lớn hơn 1/10 không? “Ừ, ở đây nhiều quá,” anh ta càu nhàu. - Vậy thì giảm phần chia, làm cho chính xác là 1/10! - nhà toán học hỏi. Tên cướp giảm cọc đi phần nào. “Bây giờ thực sự là 1/10 ở đây,” anh ta nhận xét. “Còn mày,” nhà toán học quay sang hai tên cướp đầu tiên, “bây giờ mày có thể chắc chắn rằng thậm chí còn ít hơn 1/10 trong đống.” Họ xác nhận: “Tất nhiên, họ đã loại bỏ một chút khỏi nó”. - Tuyệt vời! Vậy tôi sẽ hỏi người tiếp theo,” và anh ta chọn một tên cướp mới, “bạn có nghĩ ở đây có hơn 1/10 không?” Và thế là nhà toán học đã phỏng vấn tất cả mọi người, đề nghị giảm tỷ lệ những người tin rằng nó quá lớn. Khi thẩm vấn tên cướp cuối cùng, nhà toán học lại nói với mọi người. - Vậy trong các bạn chắc không còn ai cho rằng đống này giờ đã chứa hơn 1/10 số chiến lợi phẩm được. “Tất nhiên,” bọn cướp trả lời. Ai nghĩ phần lớn thì đã giảm bớt rồi. - Tuyệt vời! Và ai là người cuối cùng giảm tỷ lệ này? “Đúng vậy,” tên cướp trẻ đáp. - Vậy khi chia bạn chắc chắn rằng đây là 1/10. - Tôi vẫn chắc chắn về điều này. Rốt cuộc, không ai giảm nó sau tôi. - Vậy thì tự mình lấy đi! Bạn cho rằng đây là 1/10 sản phẩm nhưng số còn lại chắc chắn rằng điều này không còn nữa. - Đúng! – bọn cướp vui vẻ đồng ý. Họ bắt đầu hiểu. - Ừm, tốt! Bây giờ chúng ta có bài toán đơn giản hơn: chia phần còn lại thành 9 phần. Hãy bắt đầu theo cách tương tự. Bạn,” nhà toán học chỉ vào một trong những tên cướp, “tách 1/9 số này ra… Và theo cách tương tự, nhà toán học chia một phần cho một tên cướp khác, rồi cho một tên cướp khác, và ngay sau đó mỗi tên cướp mỉm cười hài lòng, thấy mình có được phần chiến lợi phẩm của mình. Để ăn mừng, bọn cướp lấy ra một chai lớn rượu cổ ngon và ăn mừng. Đột nhiên nhà toán học đề nghị: “Anh có muốn tôi chia đều rượu không?” - Không, nó quá dài. - Đừng lo, tôi có thể giải quyết nhanh chóng. - Chuyện này thế nào? – họ không khỏi tò mò. - Rất đơn giản. Bản thân tôi không uống rượu nên lại phải chia cho mười. Mỗi bạn có chắc chắn rằng mình có thể xác định được 1/10 lượng chứa trong chai này là bao nhiêu không? - Không có gì! “Vậy thì tôi sẽ từ từ rót rượu từ chai vào chiếc cốc này.” Ngay khi có ai quyết định rằng đây chính xác là 1/10, người đó phải ngay lập tức hét lên và ngăn tôi lại. Đồng ý?

30

KVANT 2008/№4

“Hãy thử xem,” bọn cướp trả lời có phần bối rối. Trước đây họ chưa bao giờ uống say lạ lùng như vậy. Nhà toán học bắt đầu rót đầy cốc. Anh ngày càng hoàn thiện hơn. Cuối cùng, một trong những tên cướp không thể chịu đựng được và hét lên: “Dừng lại!” Nếu không nó sẽ là quá nhiều. Bây giờ chỉ còn 1/10 chai! – Nhưng những người khác lại không nghĩ vậy? – nhà toán học hỏi. “Tất nhiên là không,” tên cướp xác nhận, “họ im lặng, nghĩa là họ tin rằng có ít hơn 1/10.” - Thôi kệ đi! Vậy thì đây chính là chia sẻ của bạn! “Và chúng ta sẽ tiếp tục,” nhà toán học nói và bắt đầu rót đầy cốc tiếp theo. – Nếu nhiều người cùng hét lên thì sao? – một người còn lại bỗng trở nên lo lắng. “Chúng ta sẽ chia phần cho bất kỳ ai trong số họ và tiếp tục chia.” Dù sao đi nữa, cuối cùng thì mọi người sẽ nhận được ít nhất 1/10 theo quan điểm của mình,” nhà toán học trấn an mọi người. Bọn cướp suy nghĩ một lúc. - Tuyệt vời! Và nó thật đơn giản,” người thông minh nhất trong số họ cuối cùng cũng nói. - Tại sao chúng ta không thể chia chiến lợi phẩm như vậy? anh ấy hỏi. Bạn nghĩ sao, độc giả?

Bình luận Câu chuyện cổ tích là một lời nói dối, nhưng có một gợi ý trong đó. Chúng tôi hy vọng người đọc hiểu bài toán và lời giải đẹp đẽ được trình bày trong câu chuyện này. Tất nhiên, thuật toán chia sẻ được mô tả trong đó không phải là thuật toán duy nhất. Có lẽ người đọc đã tìm ra cách của riêng mình. Nhưng nếu không, hãy để bài toán sau đây giúp bé thấy được những cách chia khác. Bài toán 1. Vấn đề chính khi chia làm ba là: khi một trong những tên cướp chia chiến lợi phẩm thành ba phần, hai phần còn lại biểu thị phần lớn nhất theo cùng một cách và phần nhỏ nhất – khác nhau. Bạn có thể thoát khỏi tình huống này như thế này: hai tên cướp còn lại chia phần lớn nhất cho nhau, và mỗi tên cũng chia phần giữa (theo quan điểm của chúng) làm đôi với tên cướp đầu tiên. Hãy chứng tỏ rằng với sự phân chia như vậy thì mọi người đều vui vẻ. Bài toán 2. Đảm bảo rằng thuật toán sau cũng giải được bài toán cho ba. Hai người chia sẻ tất cả chiến lợi phẩm với nhau. Sau đó, tên thứ ba chia phần của mỗi tên cướp đầu tiên thành ba phần. Hai người đầu tiên chọn một phần nhỏ hơn trong ba phần của mình và đưa cho người thứ ba. Bài toán 3. Thuật toán này có hoạt động cho bốn người không: đầu tiên, ba người chia mọi thứ cho nhau, sau đó mỗi người chia phần của mình thành bốn phần, sau đó tên cướp cuối cùng lấy phần tốt nhất từ ​​mỗi phần? Lưu ý rằng thuật toán tương tự như thuật toán trước, nhưng vẫn hơi khác một chút. Bài toán 4. Xây dựng và thử nghiệm thuật toán tìm N tên cướp dựa trên ý tưởng từ bài toán trước đó. Bài toán $5^{*}$. Giả sử trong băng nhóm có một ataman đặt ra một điều kiện bổ sung - anh ta phải

nhận được không kém bất kỳ tên cướp nào khác (theo quan điểm của bạn). Đề xuất cách chia thích hợp: a) Đối với trường hợp ba tên cướp; b) với số lượng tùy ý. Bài toán $6^{**}$. Liệu ba kẻ đố kỵ có chia được chiến lợi phẩm để mọi người chắc chắn rằng không ai có được nhiều hơn mình? Có thể nghĩ ra cách chia sẻ cho bao nhiêu người ghen tị không? Lưu ý rằng bài toán này phức tạp hơn bài toán ban đầu về ba tên cướp hoặc bài toán về thủ lĩnh. Đối với những người muốn tìm hiểu sâu hơn về những vấn đề toán học phức tạp, chúng tôi khuyên bạn nên xem trên Internet tại trang http://www.turgor.ru/lktg/1999/razbr.php (trong đó có toàn bộ loạt nghiên cứu bài toán về những tên cướp, được cung cấp vào năm 1999 cho những người tham gia Hội nghị Mùa hè lần thứ XI của Giải đấu các Thành phố). Có một số vấn đề nhạy cảm hơn. Điều gì sẽ xảy ra nếu bọn cướp bắt đầu gian lận, chẳng hạn như hợp tác với nhau và chia không đều? Điều này có thể có lợi? Nhưng đây là một chủ đề cho một cuộc thảo luận khác. Các vấn đề trước đó ngầm giả định rằng chiến lợi phẩm có thể phân chia vô hạn (tức là mỗi bộ kho báu có thể được chia thành bất kỳ số phần nào bằng nhau theo quan điểm của một tên cướp nhất định). Nhưng nếu sản lượng không được phân chia nhiều thì sao? Ví dụ, làm thế nào để chia một chiếc TV hay một viên kim cương? Nếu bọn cướp có tiền, chúng ta có thể đề xuất một thuật toán tinh tế như vậy. Mỗi tên cướp định giá từng món đồ theo số tiền mà hắn tin rằng món đồ đó có giá trị. Người nào cho số tiền nhiều nhất thì trả tiền và lấy đồ về cho mình. Sau đó, tất cả số tiền trả được chia đều. Đây là một sửa đổi khác của ý tưởng này mà tác giả đã áp dụng thành công trong thực tế. Có người mua thì có người bán. Người bán muốn bán với giá cao hơn nhưng không buộc phải bán. Người mua muốn mua rẻ hơn nhưng không bắt buộc phải mua. Thay vì mặc cả, bạn có thể đưa ra phương pháp này. Người bán viết lên một tờ giấy số tiền tối thiểu A mà anh ta sẵn sàng bán và người mua viết số tiền B tối đa mà anh ta sẵn sàng trả. Sau đó họ nhìn vào những mảnh giấy. Nếu A>B thì giao dịch sẽ không diễn ra. Nếu không, giá sẽ là giá trị trung bình số học và cả hai sẽ hài lòng. Tất nhiên, trong cả thuật toán này và thuật toán trước, vấn đề gian lận đặc biệt thú vị. Và một điều cuối cùng. Nhưng trong thực tế, làm thế nào để bạn chia một cốc nước đầy thực sự bằng nhau (coi cái cốc là một hình trụ)? Rất đơn giản: từ từ (sao cho bề mặt phẳng) đổ nước ra cho đến khi bạn nhìn thấy phần đầu của đáy. Vì lý do đối xứng, chỉ một nửa sẽ còn lại trong kính.