Một bài toán!? Chia quà cho người yêu [Lưu Trữ] - Học sinh và Cựu Học Sinh Chuyên Thăng Long

Tuan12T96

30-03-2004, 10:27 PM

Bài toán này gồm hai phần (Phần hai do mình nghĩ ra) :-D

Phần một: (đây là bài toán tên: ******)
[size=8]---Đã bảo là không được nêu tên bài toán ra mà - OC----

Bạn có hai người con rất tham ăn. Bạn có một bịch kẹo lớn gồm đủ thứ kẹo: chocolate. kẹo dừa, kẹo sữa, kẹo dâu, kẹo chuối....

Mổi người con có một sở thích khác nhau về kẹo, đương nhiên mỗi người con giá trị mỗi loại kẹo khác nhau. Bạn hoàn toán không biết về sở thích kẹo của hai người con.

Hai người con sẽ đánh nhau liền nếu thấy phần kẹo của người kia giá trị hơn phần kẹo của mình.

Bạn làm sao đây?

Hint: nếu có ba người con, bài toán này sẽ không có lời giải nếu không có giả thiết thêm.

lnbkhanh

31-03-2004, 12:51 AM

Sao tựa đề là chia cho người yêu mà vô tới nơi thì thấy con cái nheo nhóc vậy nè? 8O

bush

31-03-2004, 03:09 AM

Chia đôi sao cho số kẹo mỗi lọai là bằng nhau, nếu số kẹo là số lẻ thì mình ăn, hay đem vứt

lnbkhanh

31-03-2004, 03:31 AM

Mổi người con có một sở thích khác nhau về kẹo, đương nhiên mỗi người con giá trị mỗi loại kẹo khác nhau. Bạn hoàn tòan không biết về sở thích kẹo của hai người con.

Chia đôi sao cho số kẹo mỗi lọai là bằng nhau
tuanSWB không đọc kỹ đề rồi, chia như vậy thì hai đứa đánh nhau là cái chắc

Tuan12T96

31-03-2004, 08:10 AM

Cảm ơn cô Khánh. Cô Khánh nói đúng rồi đấy. Bài toán này hay lắm. Giải giúp mình đi.

sontran

31-03-2004, 08:17 AM

"đương nhiên mỗi người con giá trị mỗi loại kẹo khác nhau" hình như câu này hơi khó hiểu. Tuấn edit lại giúp nhé

Câu này xin edit lại như sau: Mỗi người có sở thích về kẹo khác nhau, do đó giá trị mỗi viên kẹo đối với mỗi người là khác nhau. Ví dụ: A thích kẹo chuối nên giá trị viên kẹo chuối là $5 cho A, nhưng B không thích kẹo chuối nên giá trị viên kẹo chuối chỉ là $2 cho B.

HienSy

31-03-2004, 08:06 PM

Mình nghĩ thế này! mong bà con góp ý!
- Trươ1c tiên , để ý điều kiện , mình hòan toàn không biết được 2 thằng cu nhà mình thích gì, thích ở mức độ nào! ( dĩ nhiên mình có thể hỏi , trắc nghiệm, thống kê lại, sẽ được: với mỗi thằng cu, mỗi loại kẹo có 1 hệ số a1,b1,c1... --- a2,b2,c2 ...gì dó .Giải pt nhiều biến sẽ ra rất nhiều nghiệm.) Quá phức tạp:
- Mình sẽ không quyết định thằng nào được cái gì mà cho chúng tự quyết định in control của mình:
- Lần lượt từng đứa sẽ chọn 1 viên kẹo( 1 đơn vị chia ) , đưa cho đứa kia (dĩ nhiên, sẽ là cái nó không thích nhất trong số còn lại, tên nào cũng ham ăn mà)
(giả sử ở đây số kẹo không lẻ) như vậy, sau khi chia xong, không đứa nào ghen ti vì đứa kia lấy phần mình thích( mình đưa cho nó mà )
- Trong khi chia, viên kẹo mà mình thích vẫn luôn còn đó cho đến lúc đứa kia trao cho mình hoặc mấy cái còn lại còn tốt hơn( đ.với mình) và cầm nó trao cho tên kia!

Với số keo tương đối, độ ngẫu nhiên cao thì chia như vậy, một điều chắc chắn là không tên nào cãi tên nào cả.

Không biết có ý kiến nào khác không??

Tuan12T96

31-03-2004, 09:49 PM

Trước tiên xin đính chính với O41 là: Bài toán này rất có thể không có lời giải cho N=4. Nếu có thì nó sẽ phải đặt ra rất nhiều giả thiết về 4 người đó.

Bài toán cho N=3, Có lời giải nhưng nó mất hay bởi vì phải dựa vào một số giả thiết (bài toán N=3 là môt câu chuyện trong một cuốn kinh thánh)

Lời giải của Hien Sy rất thú vị nhưng không chính xác. Phương pháp này không khác mấy so với phương pháp cho mỗi người chọn cái mình thích nhất trước (tuy nhiên phương pháp của Sy hay ở chổ tránh đuợc một số problem ở phương pháp Cho Mỗi người chọn cái mình thích nhất trước)

Lý do: sau khi phân chia kẹo hai nguời con sẽ có hai đống kẹo khác nhau. Người A (hay B) sẽ nhìn vào đống kẹo của B (hay A) và so sánh giá trị của cả đống kẹo của người kia với đống kẹo của mình.

Tuan12T96

02-04-2004, 09:08 PM

sontran

02-04-2004, 09:34 PM

Quả là thú vị :)
Hôm giờ nhiều bài quá nên bài này bị quên lãng mất. Xem ra cái 10 bài mới nhất cũng có điểm yếu nhỉ :).

Tuan12T96

02-04-2004, 09:48 PM

Theo như đáp án này: Nếu N=3 thì lời giải không còn dễ dàng nữa phải không O41 :) .

baotran

02-04-2004, 09:54 PM

Quả là thú vị :)
Hôm giờ nhiều bài quá nên bài này bị quên lãng mất. Xem ra cái 10 bài mới nhất cũng có điểm yếu nhỉ :).
Em thường xem bài mới từ lần truy cập trước, có gì trả lời luôn. Nhưng những khi máy bị mad thì toi luôn, lúc đó thì cái 10 bài mới nhất cũng useful phết.

tuanle

03-04-2004, 06:28 PM

solution:

Kêu một trong hai người con vào: nói nó chia kẹo thành hai đống nó thích ngang nhau. Sau đó kêu dứa còn lại vào. Bào nó chọn đống kẹo nó thích hơn (chọn một trong hai đống kẹo). Vậy hai đứa chắc chắn sẽ không đánh nhau.

Anh nghĩ lời phương pháp [b]người chia người chọn[/] cho bài toán [b]chia công bằng[/] dùng trong trường hợp có vẻ không hợp lý. Đây là bài toán cho giá trị rời rạc (descrete) chứ không phải liên tục (continuous). Ví dụ như để chia bánh thì hợp lý hơn. Tuan12T96 nghĩ thế nào?

tuanle

03-04-2004, 06:40 PM

sontran

03-04-2004, 06:57 PM

Cách 1: 1 người chia - 2 người chọn
1 người con chia đống kẹo ra làm 3 phần mà theo he/she là công bằng.
Hai người còn lại chọn một phần trong 3 phần đó.
Có 2 trường hợp xảy ra:
(1) 2 người con kia chọn 2 phần khác nhau -> quá dễ
(2) 2 người con kia cùng chọn một phần -> người chia phải lấy 1 trong 2 phần còn lại. Hai phần kẹo kia đem gộp lại rồi phân chia như là trong trường hợp N = 2.

Trong trường hợp 2 sau khi chia xong lỡ có 1 đứa nào trong 2 đứa hoặc cả 2 đứa quay ra phân bì với người thứ nhất thì sao?
VD A chia lam 3 và đã lấy 1 phần; B merge 2 phần còn lại rồi chia theo ý B; Sau đó C vào chọn thì C có thể nhìn vào 2 phần đó và cho là 0 công bằng so với đống của A thì sao?

Cách 2: 2 người chia - 1 người chọn
Đầu tiên 2 người chia sẽ chia đống kẹo ra hai phần công bằng giống như trường hợp N = 2.
Sau đó mỗi người sẽ chia phần của mình ra làm 3 phần.
Người con còn lại (người chọn) sẽ chọn 1 phần từ mỗi người chia. Hai người chia lấy 2 phân còn lại.

Nếu như 2 người có thể xúm lại chia đống kẹo ra thành 2 phần công bằng thì với bài toán N=2 đã giải quyết xong rồi, đâu cần nghĩ nữa?

HienSy

03-04-2004, 07:16 PM

Em cũng có ý kiến như anh Tuấn Lê!
Với giá trị rời rạc, sẽ mất ý nghĩa chia đều. Tưởng tượng chỉ có 1 ít kẹo, các loại, 1 người cũng khó chia đều theo ý mình.

HienSy

03-04-2004, 07:32 PM

Cách 1: 1 người chia - 2 người chọn
1 người con chia đống kẹo ra làm 3 phần mà theo he/she là công bằng.
Hai người còn lại chọn một phần trong 3 phần đó.
Có 2 trường hợp xảy ra:
(1) 2 người con kia chọn 2 phần khác nhau -> quá dễ
(2) 2 người con kia cùng chọn một phần -> người chia phải lấy 1 trong 2 phần còn lại. Hai phần kẹo kia đem gộp lại rồi phân chia như là trong trường hợp N = 2.

Cách này tương đối hợp lý. Chỉ có 1 vấn đề là ở trường hợp 2:
Gọi 3 phần chia là A, B , C
-2 đứa kia đều chọn A 1st, vậy đứa chia sẽ chọn B, or C
-Problem khi, 2nd place với 2 dứa kia là B (vd vậy ) mà , đứa chia chọn B. Có khả năng A+C chia ra đối với 2 đứa kia nhỏ hơn B ( 2sd với chúng )
-Sovle vdề này dễ, chỉ bắt buộc đứa chia chọn C
-Real Problem khi 2nd với 2 đứa kia khác nhau. ---> dồn A+C chia 2, hoặc A+B / 2 đều có thể ít giá trị hơn phần còn lại dối với 1 trong 2 đứa kia. ---> tranh cãi với đứa chia!

không biết Ý anh Tuấn ntn?

Còn cách 2 thì em cũng đồng ý với anh Tuấn,mình hoàn toàn có thể tổng quát lên cho n ( đệ qui về n-1, (n-1 người sẽ chia phần cũa mình ra n phần = nhau theo ý mình) người n chọn n phần từ mỗi phần chia này , theo ý mình) Với phần tử rời rạc thì cũng khó chia!

sontran

03-04-2004, 07:33 PM

Thực sự thì mình 0 nghĩ là bắt buộc phải là bằng nhau tuyệt đối. Dường như đây là 1 kiểu toán chi tài sản gì đó bên kinh tế thì phải ??? Không bắt buộc chia ra có giá trị bằng nhau tuyệt đối nhưng gần bằng nhau đủ để người chia hài lòng thì chắc là được ấy nhỉ?

tuanle

03-04-2004, 09:06 PM

Trong trường hợp 2 sau khi chia xong lỡ có 1 đứa nào trong 2 đứa hoặc cả 2 đứa quay ra phân bì với người thứ nhất thì sao?
VD A chia lam 3 và đã lấy 1 phần; B merge 2 phần còn lại rồi chia theo ý B; Sau đó C vào chọn thì C có thể nhìn vào 2 phần đó và cho là 0 công bằng so với đống của A thì sao?

A chia xong đau có được chọn, 2 người kia chọn xong thì A mới lấy phần còn lại.

Nếu như 2 người có thể xúm lại chia đống kẹo ra thành 2 phần công bằng thì với bài toán N=2 đã giải quyết xong rồi, đâu cần nghĩ nữa?
Tui đang nói về tổng quát bài toán N=2 cho N=3 mà.

Tuan12T96

03-04-2004, 09:18 PM

Anh nghĩ lời phương pháp [b]người chia người chọn[/] cho bài toán [b]chia công bằng[/] dùng trong trường hợp có vẻ không hợp lý. Đây là bài toán cho giá trị rời rạc (descrete) chứ không phải liên tục (continuous). Ví dụ như để chia bánh thì hợp lý hơn. Tuan12T96 nghĩ thế nào?
Em một phần đồng ý với ý kiến anh Tuấn. Đúng là bài toàn này discrete này nó có vẻ không hợp lý ở một số điểm về toán học. Nhưng nếu nó là bài toán continuous (mọi thứ đều perfectly divisible) thì dễ dàng hơn. Tuy nhiên mục đích của bài toán này là envy free.

Cách chia discrete làm đuợc việc này.

Việc người con đầu tiên (gọi là A) chia kẹo thành hai phần nó thích ngang nhau . Đó là sự lựa chọn của người con này (có thể sẽ chia không đuợc vì tổng giá trị (utility of A) của đống kẹo là lẽ) nhưng A không thể envy nếu B chọn một trong hai đóng kẹo được vì A "đã" xem giá trị của hai đóng kẹo là "bằng nhau"

tuanle

03-04-2004, 09:26 PM

-Problem khi, 2nd place với 2 dứa kia là B (vd vậy ) mà , đứa chia chọn B. Có khả năng A+C chia ra đối với 2 đứa kia nhỏ hơn B ( 2sd với chúng )
-Sovle vdề này dễ, chỉ bắt buộc đứa chia chọn C
-Real Problem khi 2nd với 2 đứa kia khác nhau. ---> dồn A+C chia 2, hoặc A+B / 2 đều có thể ít giá trị hơn phần còn lại dối với 1 trong 2 đứa kia. ---> tranh cãi với đứa chia!

Vấn đề Sỹ đặt ra hay quá :) Anh không nghĩ ra trường hợp này.
Cách giải quyết của em cũng chưa rốt ráo, trong trường hợp second preference của 2 người chọn khác nhau thì làm thế nào? Cụ thể:
+first pref của cả 2 là A
+second pref của 1 người là B, một người là C.
Khi đó bắt người chia chọn cái nào?

Tuan12T96

03-04-2004, 09:30 PM

Tuan12T96

03-04-2004, 09:51 PM

Theo như đáp án này: Nếu N=3 thì lời giải không còn dễ dàng nữa phải không O41 :) .
Nếu dùng phương pháp như Tuan12T96 thì cho N=3 cũng đơn giản như vậy.
Cách 1: 1 người chia - 2 người chọn
1 người con chia đống kẹo ra làm 3 phần mà theo he/she là công bằng.
Hai người còn lại chọn một phần trong 3 phần đó.
Có 2 trường hợp xảy ra:
(1) 2 người con kia chọn 2 phần khác nhau -> quá dễ
(2) 2 người con kia cùng chọn một phần -> người chia phải lấy 1 trong 2 phần còn lại. Hai phần kẹo kia đem gộp lại rồi phân chia như là trong trường hợp N = 2.

Problem với phương pháp này:

(2) 2 người con kia cùng chọn một phần -> người chia phải lấy 1 trong 2 phần còn lại. Hai phần kẹo kia đem gộp lại rồi phân chia như là trong trường hợp N = 2.

Ai sẽ là người chọn trước. Ví dụ A phân chia thành ba phần mình thích ngang nhau. B và C cùng chọn một phần. Khi hai phần kẹo đem gộp lại và chia như trong trường hợp N=2. Sau khi chia, giá trị của một trong hai phần này có thể lớn hơn giá trị của được chọn đầu tiên theo quan điểm (preference) của A.

Cách 2: 2 người chia - 1 người chọn
Đầu tiên 2 người chia sẽ chia đống kẹo ra hai phần công bằng giống như trường hợp N = 2.
Sau đó mỗi người sẽ chia phần của mình ra làm 3 phần.
Người con còn lại (người chọn) sẽ chọn 1 phần từ mỗi người chia. Hai người chia lấy 2 phân còn lại.

Phương pháp này rất thú vị (em cũng suy nghĩ như vậy khi tiếp xúc với bài toàn này)
Problem:
Sau đó mỗi người sẽ chia phần của mình ra làm 3 phần.

Giả sử đây là A và B: Sau khi A và B mỗi người chia thành ba phần bằng nhau. Note: Giá trị ba phần A chia (công bằng theo preference của A) có thể có giá trị hoàn toàn khác đối với B. Ba phần chia của B cũng vậy.

Another problem: Người con còn lại C: Nếu his preference là (thích nhất và thích nhì) là cả hai phần kẹo của B. Vậy thì sao? Note: rất có thể A cũng thích một trong hai phần C chọn hơn ba phần mình chia vì B chia lại nên giá trị của 3 phần kẹo sẽ khác nhau theo preference của A.

sontran

03-04-2004, 10:53 PM

sontran đã viết :

Trong trường hợp 2 sau khi chia xong lỡ có 1 đứa nào trong 2 đứa hoặc cả 2 đứa quay ra phân bì với người thứ nhất thì sao?
VD A chia lam 3 và đã lấy 1 phần; B merge 2 phần còn lại rồi chia theo ý B; Sau đó C vào chọn thì C có thể nhìn vào 2 phần đó và cho là 0 công bằng so với đống của A thì sao?

A chia xong đau có được chọn, 2 người kia chọn xong thì A mới lấy phần còn lại.

Nếu vậy thì làm sao có 2 phần còn lại :?: Khi mà A chưa chọn thì sẽ 0 có 2 phần còn lại. Rite?

Tuan12T96

04-04-2004, 12:22 AM

Cách này tương đối hợp lý. Chỉ có 1 vấn đề là ở trường hợp 2:
Gọi 3 phần chia là A, B , C
-2 đứa kia đều chọn A 1st, vậy đứa chia sẽ chọn B, or C
-Problem khi, 2nd place với 2 dứa kia là B (vd vậy ) mà , đứa chia chọn B. Có khả năng A+C chia ra đối với 2 đứa kia nhỏ hơn B ( 2sd với chúng )
-Sovle vdề này dễ, chỉ bắt buộc đứa chia chọn C
-Real Problem khi 2nd với 2 đứa kia khác nhau. ---> dồn A+C chia 2, hoặc A+B / 2 đều có thể ít giá trị hơn phần còn lại dối với 1 trong 2 đứa kia. ---> tranh cãi với đứa chia!

không biết Ý anh Tuấn ntn?

Còn cách 2 thì em cũng đồng ý với anh Tuấn,mình hoàn toàn có thể tổng quát lên cho n ( đệ qui về n-1, (n-1 người sẽ chia phần cũa mình ra n phần = nhau theo ý mình) người n chọn n phần từ mỗi phần chia này , theo ý mình) Với phần tử rời rạc thì cũng khó chia!

Oh, Sỹ đã chỉ ra problem của Phương Pháp thứ nhất.
Phương pháp thứ hai cũng có problem giống vậy. Xin lỗi mình không đọc kỹ bài viết của mọi người.

Em cũng có ý kiến như anh Tuấn Lê!
Với giá trị rời rạc, sẽ mất ý nghĩa chia đều. Tưởng tượng chỉ có 1 ít kẹo, các loại, 1 người cũng khó chia đều theo ý mình.

Nều bài toán này mà continuous thì vần đề chia không còn là vấn đề. Bởi vì mọi viên kẹo cứ bẻ đôi ra một người một phần là xong. Cho N people, thì mỗi viên kẹo chia cho N phần là xong.

Trong thực tế, discrete case rất quan trọng. Nhưng hầu hết các nhà toán học và kinh tế học thì thích continuous vì nó dễ giúp giải quyết được nhiều vần đề khó khăn trong theory.

tuanle

05-04-2004, 08:17 PM

Nều bài toán này mà continuous thì vần đề chia không còn là vấn đề. Bởi vì mọi viên kẹo cứ bẻ đôi ra một người một phần là xong. Cho N people, thì mỗi viên kẹo chia cho N phần là xong.

Em nói vậy là mâu thuẫu với đề bài rồi. Mỗi người quan niệm giá trị của từng loại kẹo khác nhau mà. Nếu chia đôi tất cả các viên kẹo rồi cho mỗi người một nữa cũng đâu có ra được 2 phần công bằng.

Anyway, vấn đề này có thể áp dụng được ngay trong công việc hằng ngày, ví dụ 1 project được phân ra nhiều phần nhỏ, làm sao để chia công việc mà các thành viên không nạnh tị. Phương pháp kẻ chia người chọn này áp dụng vô là tuyệt cú mèo :)

HienSy

05-04-2004, 08:32 PM

Nều bài toán này mà continuous thì vần đề chia không còn là vấn đề. Bởi vì mọi viên kẹo cứ bẻ đôi ra một người một phần là xong. Cho N people, thì mỗi viên kẹo chia cho N phần là xong.

Em nói vậy là mâu thuẫu với đề bài rồi. Mỗi người quan niệm giá trị của từng loại kẹo khác nhau mà. Nếu chia đôi tất cả các viên kẹo rồi cho mỗi người một nữa cũng đâu có ra được 2 phần công bằng.

Anh Tuấn ơi! Công bằng chứ! 2 phần bằng nhau tuyệt đối về vật chất thì quan niệm gía trị có khác nhau , vẫn phải công nhận 2 phần đó là bằng nhau thui! một nửa viên kẹo, dù mình thích hay không thích vẫn phai công nhận nửa của thằng kia không hơn gì mình !
Giả pháp cho N = 3 quả thật khó quá, em vẫn không đưa ra được g.pháp nào tổng quá hóa nó lên. Nếu được thì có nhiều ứng dụng trong quản lý lắm.

Tuan12T96

05-04-2004, 08:37 PM

Anh Tuấn ơi, thực ra không có mâu thuẫn đâu. Nếu nó là continuous thì net trade vector của hai mọi người đều giống nhau nên không ai có thể ganh tị ai đuợc cả (ví dụ, có mười loại bánh khác nhau, hai người con mỗi người có nữa cái bánh của cả mười cái bánh, vậy thì không ai ghen tị ai đuợc cả). Hôm nào anh em mình gặp nhau có thể bàn luận thêm về nó. Phần này lêin quan tới kinh tế hơi nhiều.

(phần hai của vấn đề này mình còn có thể chứng minh đuợc sự yếu kém trên lý thuyết của nền kinh tế đóng cửa và cnxh).

Tuan12T96

05-04-2004, 08:43 PM

Anh Tuấn ơi! Công bằng chứ! 2 phần bằng nhau tuyệt đối về vật chất thì quan niệm gía trị có khác nhau , vẫn phải công nhận 2 phần đó là bằng nhau thui! một nửa viên kẹo, dù mình thích hay không thích vẫn phai công nhận nửa của thằng kia không hơn gì mình !
Giả pháp cho N = 3 quả thật khó quá, em vẫn không đưa ra được g.pháp nào tổng quá hóa nó lên. Nếu được thì có nhiều ứng dụng trong quản lý lắm.

Chào cậu có tiếng hát to nhất trường :lol: :-D . Để anh kiếm bài article về trường hợp N=3 rồi sẽ gởi cho em và anh Tuấn. Chắc là anh em thanglong mình mở một hội trao đổi về Game Theory (phần này có nhiều bài toán hay quá quá, đọc xong muốn phát khóc luôn)

tuanle

05-04-2004, 08:45 PM

Anh Tuấn ơi! Công bằng chứ! 2 phần bằng nhau tuyệt đối về vật chất thì quan niệm gía trị có khác nhau , vẫn phải công nhận 2 phần đó là bằng nhau thui! một nửa viên kẹo, dù mình thích hay không thích vẫn phai công nhận nửa của thằng kia không hơn gì mình !

Anh suy nghĩ máy móc quá. Nghe em nói mới giác ngộ :P, thanks a lot!

Giả pháp cho N = 3 quả thật khó quá, em vẫn không đưa ra được g.pháp nào tổng quá hóa nó lên. Nếu được thì có nhiều ứng dụng trong quản lý lắm.
Cố gắng lên em, biết đâu lại đăng ký được một bằng phát minh :) good luck nhé.

Anh Tuấn ơi, thực ra không có mâu thuẫn đâu. Nếu nó là continuous thì net trade vector của hai mọi người đều giống nhau nên không ai có thể ganh tị ai đuợc cả (ví dụ, có mười loại bánh khác nhau, hai người con mỗi người có nữa cái bánh của cả mười cái bánh, vậy thì không ai ghen tị ai đuợc cả). Hôm nào anh em mình gặp nhau có thể bàn luận thêm về nó. Phần này lêin quan tới kinh tế hơi nhiều.

Hẹn em một ngày đẹp trời, biết đâu lần sau anh không bị refuse Visa application thì sao. Anh em mình đi Las Vegas làm kinh tế :P

(phần hai của vấn đề này mình còn có thể chứng minh đuợc sự yếu kém trên lý thuyết của nền kinh tế đóng cửa và cnxh).

Kinh tế thị trường theo định hướng XHCH thì sao em?
Hay làm em đưa phần 2 lên đây luôn đi.

lnbkhanh

06-04-2004, 04:55 AM

Hẹn em một ngày đẹp trời, biết đâu lần sau anh không bị refuse Visa application thì sao. Anh em mình đi Las Vegas làm kinh tế :P
Dự đóan tổng quát số tiền mà hai anh Tuấn cùng kiếm được là bằng nhau về giá trị tuyệt đối lẫn giá trị so sánh, xét trên cả phương diện toán học, kinh tế học và ... bài bạc học ... ===...0 :-D :D

sontran

06-04-2004, 07:02 AM

Woa, sao nhiều vậy hả Khánh? :roll:

Tuan12T96

06-04-2004, 12:02 PM

Kinh tế thị trường định hướng XHCN là điều tốt trong giai đoạn đổi mới. Nền kinh tế nào cũng đều có thể không tốt nếu chính sách không phù hợp.

Anh Tuấn mà có thời gian đọc cuốn sách này thì hay tuyệt: Globalization and its discontents, Joseph Stiglitz, nobel prize winner in economics, đồng thời là chef economist của World Bank. Từ trang đầu dền gần trang cuồi ông ta toàn chửi IMF (IMF luôn luôn ủng hộ chủ nghĩa Tư Bản một cách khá mù quáng).

Claim của phần hai: Phương pháp chia trên thực sự không tối ưu. Nó làm hai đứa không ghen tị lẫn nhau nhưng không maximize hai đứa utility.

dnthong

06-04-2004, 04:17 PM

Chờ chút xíu nào, bài toán này dzui quá, thế mà mọi người định chuyển chủ đề rồi hử :wink:

Coi như trường hợp n=2 đã OK. Bây giờ xử n=3. Gọi 3 bé giành ăn là be_tuanle, be_Tuan12T96 và be_Hien_Sy :-D

Đối với cách 1 người chia - 2 người chọn, có thể làm khác 1 chút.

+be_tuanle chia đống kẹo thành 3 phần bằng nhau A, B, C

+2 bé còn lại, be_Tuan12T96 và be_Hien_Sy, mỗi bé chọn 2 phần kẹo mà bé thích nhất. Có 2 trường hợp xảy ra:

a)Hai phần kẹo này giống nhau (giả sử phần A và B): be_Tuan12T96 và be_Hien_Sy sẽ gộp 2 phần kẹo này lại và chia làm 2 phần như trường hợp n=2, be_tuanle lấy phần C.

b)Hai phần kẹo này khác nhau, giả sử be_Tuan12T96(A,B), be_Hien_Sy(B,C) : be_Tuan12T96 sẽ share phần kẹo B với be_Hien_Sy và share phần A với be_tuanle áp dụng case n=2. Tương tự cho be_Hien_Sy.

Như vậy sau khi chia, bé nào cũng hài lòng vì phần của mình là xịn nhất.

n>3, cũng có thể làm tương tự (1 người chia , n-1 người chọn)

tieuthu_style

06-04-2004, 04:31 PM

nghe chủ đề hấp dẫn wá , em định vào xem thử , nhưng xem xong thì thấy chóng hết cả mặt , em chả hiểu mọi người nói gì cả :?: :roll:

sontran

06-04-2004, 04:36 PM

Nhưng mà như Tuan12T96 đã nói khi phân mảnh ra thì giá trị về mặt ưa thích đã thay đổi.
Theo như anh Thông chia thì:
B) Tuan12T96 : 1 phần của A (share với tuanle) + 1 phần của B (share với Hiền_Sỹ)
tuanle có: 1 phần của A và 1 phần của C
Hien_Sy có: 1 phần của B và 1 phần của C

Bây giờ Hiền Sỹ có thể compare phần C mình có với phần A Tuan12T96 có . Lưu ý là mặc dù trước đây Sỹ 0 lấy phần A nhưng bây giờ sau khi chia xong thì phần A của Tuan12T96 lại better cái phần C của Sỹ thì sao. Tương tự với Tuanle và Tuan12T96. Trẻ con mà chúng nó thay đổi ý kiến hòai. :lol:
Như đã nói là sự bằng nhau này không phải là tuyệt đối mà chủ yếu là sự ưa thích.
Để dễ hình dung ta có thể ví dụ như thay kẹo bằng nhà cửa đi: 1 căn biệt thự ở Đà Lạt và 1 căn nhà nhỏ mặt tiền ở Sài Gòn có giá trị tương đương nhau. Giả sử ban đầu Sỹ thích căn ở Đà Lạt do nó to, nơi ở thóang mát ... còn Tuanle thích nhà Sài Gòn vì có mặt tiền làm ăn được dù nó hơi nhỏ. Nhưng chia theo cách của anh Thông thì sau khi chia đôi căn nhà bé tẹo ở SG ra thì Tuấn lê lại thấy chẳng thà lấy cái nửa nhà ở Đà Lạt còn hơn lấy cái căn nhà bi giờ bé bằng cái hẻm ở SG.
Đại khái là như dzậy :-D
Thui lại đi làm tiếp

HienSy

06-04-2004, 05:48 PM

Đối với cách 1 người chia - 2 người chọn, có thể làm khác 1 chút.

+be_tuanle chia đống kẹo thành 3 phần bằng nhau A, B, C

+2 bé còn lại, be_Tuan12T96 và be_Hien_Sy, mỗi bé chọn 2 phần kẹo mà bé thích nhất. Có 2 trường hợp xảy ra:

a)Hai phần kẹo này giống nhau (giả sử phần A và B): be_Tuan12T96 và be_Hien_Sy sẽ gộp 2 phần kẹo này lại và chia làm 2 phần như trường hợp n=2, be_tuanle lấy phần C.

b)Hai phần kẹo này khác nhau, giả sử be_Tuan12T96(A,B), be_Hien_Sy(B,C) : be_Tuan12T96 sẽ share phần kẹo B với be_Hien_Sy và share phần A với be_tuanle áp dụng case n=2. Tương tự cho be_Hien_Sy.

Như vậy sau khi chia, bé nào cũng hài lòng vì phần của mình là xịn nhất.

n>3, cũng có thể làm tương tự (1 người chia , n-1 người chọn)

Anh dnthong a! OC cũng có lý đó:

VD, Em thích C, a Tuân12T96 thích A, ( B chung rùi, không nói) nhưng khi chia đôi, em chia thành C1, C2 để chia với anh TuấnLệ , bằng đối với em nhưng với anh Tuan12T96 nó không bằng nhau!
Có thể đối với ảnh, C1 >> hẳn so với C2, biết đầu không > A1, A2 mà anh Tuân12T96 đã chia!Vấy anh Tuấn Lê chọn C1, hay em chọn C1, anh Tuân12T96 cũng sẽ khóc ầm mĩ lên, kêu bọn em ăn gian cho mà coi!

Anh dnthong để ý : phép chia đôi trên chỉ có giá trị thoả mẵn 2 người thôi (1 thấy công bằng, 1 thấy lợi ), người thứ 3 trở đi sẽ cho là 2 phần chia đó chênh lệch! So với phần của mình , có thể 1 trong 2 đó còn lớn hơn phần mình nữa!

Claim của phần hai: Phương pháp chia trên thực sự không tối ưu. Nó làm hai đứa không ghen tị lẫn nhau nhưng không maximize hai đứa utility.
Uh! Chia như vậy, nhìn ở mức độ tổng quát, 1 bằng , 1 lợi, xét cho cùng cũng là không công bằng.

Anh Tuân12T96 ơi! Anh cho đăng tiếp phần 2 đi! Chuẩn bị khởi động!

dnthong

06-04-2004, 09:46 PM

OC à, cách của tui cũng chỉ định giải quyết continuous cases (ở đây, chia bánh thì đúng hơn :)). Còn đối với discrete cases thì chắc có giải pháp rồi (người ta vẫn hàng ngày xử các vụ phân chia tài sản mà), tui tin thế.

OK. Đồng ý với OC và Hien_Sy, cách này của mình cũng không ổn rồi.

Như vậy vẫn chưa có lời giải đúng cho trường hợp n=3 hử Tuan12T96???

Mình thử search 1 tí để tìm hiểu 1 chút về background của vấn đề này thì thấy người ta cũng thảo luận nhiều lắm rồi và đưa ra không ít phương pháp giải quyết. Vấn đề này là envyfree cake-cutting (cake-division) problem.

Có 1 giải pháp do Brams đưa ra năm 1992 cho trường hơp n=3 như sau. Giả sử 3 người là P1,P2,P3

+P1 chia miếng bánh thành 3 phần bằng nhau (theo ý P1)

+P2 sẽ xén bớt 1 trong 3 phần mà P2 cho là to nhất sao cho phần này bằng với phần mà P2 cho là to thứ nhì (bằng theo ý P2, nếu P2 không phải xén thì nghĩa là 3 phần này như nhau theo ý P2, càng tốt).

+P3 sẽ chọn trước, sau đó P2 sẽ chọn tiếp theo và phải chọn phần bánh đã bị xén (nếu nó chưa bị P3 chọn). Phần bánh cuối cùng thuộc về P1.

Có thể dễ phân tích thấy đây là giải pháp envy-free

Tham khảo thêm ờ : http://www.sciencenews.org/pages/sn_arch/5...5_4_96/bob1.htm (http://www.sciencenews.org/pages/sn_arch/5_4_96/bob1.htm)

Tuy nhiên, khi áp dụng cách này cho n=4 thì Brams bí, phải nhờ sự giúp đỡ của ông Taylor, xem : http://www.people.vcu.edu/~gasmerom/MAT131...ramstaylor.html (http://www.people.vcu.edu/~gasmerom/MAT131/bramstaylor.html)

Một số giới thiệu tóm tắt về vấn đề này có thể tìm thấy ở:

http://www.geocities.com/CollegePark/6174/...MATH-DIVIDE.HTM (http://www.geocities.com/CollegePark/6174/jokes/MATH-DIVIDE.HTM)

http://www.colorado.edu/education/DMP/fair...r_division.html (http://www.colorado.edu/education/DMP/fair_division.html) (có lời giải cho discrete case)

http://www.pubchoicesoc.org/papers/jones.pdf

http://www.ams.org/proc/1997-125-02/S0002-...-97-03614-9.pdf (http://www.ams.org/proc/1997-125-02/S0002-9939-97-03614-9/S0002-9939-97-03614-9.pdf)

http://citeseer.ist.psu.edu/22271.html

http://www.math.hmc.edu/~su/papers.dir/wp311b.pdf

Trong khi chờ Tuan12T96 post phần 2, mọi người xem và tiếp tục bàn nhé.

Thân

Tuan12T96

07-04-2004, 10:29 AM

Thứ nhất, Anh Thông nói tới: Luật thừa kế, hay phân chia tài sản. Woa, cái này áp dụng hay lắm đó nha. Mai mốt có dịp mình đăng báo "bài toán" này đi Người Viết: ThăngLong, tên bài (Mấy anh em nghĩ hộ đi.) Tuy nhiên mình nên tìm phương pháp giải cho N=3 under discrete case trước đã. Anh Thông ơi, các bài viết trên hình như không deal với discrete case (Có thể em hông nhìn kỹ)

Phần hai để em có thới gian suy nghĩ cách đặt câu hỏi một cách chính xác rồi sẽ post lên.

sontran

07-04-2004, 10:55 AM

Thứ nhất, Anh Thông nói tới: Luật thừa kế, hay phân chia tài sản. Woa, cái này áp dụng hay lắm đó nha.

Anh không nghĩ là cái này áp dụng tốt cho ba cái Luật thừa kế này :). Vì bên thừa kế còn 1 số yếu tố tham gia như Tòa Án, Luật Sư tèm lem hết và họ sẽ là những người quyết định chính chứ hổg phải là những người được chia :). Thông thường có lẽ họ sẽ tìm cách chuyển về Continuous case để giải quyết (định giá tài sản).
Nếu mà 0 đưa ra tòa muốn giải quyết êm đẹp với nhau thì có thể dùng giải pháp này. Nhưng mà nếu đông anh em quá thì chắc áp dụng phương pháp định giá để chia xem ra còn đỡ phiền phức hơn.
Có lẽ người ta áp dụng discrete case cái này trong các vụ chia tách công ty hay ký hợp đồng song phương chẳng hạn ...
Mình vừa xem sơ trong cái link mà Thông nói có discrete case:

http://www.colorado.edu/education/DMP/fair...r_division.html (http://www.colorado.edu/education/DMP/fair_division.html) (có lời giải cho discrete case)

thì thấy dường như nó áp dụng phương pháp định giá tài sản để quy đổi về continuos case. Chỉ có điều việc định giá sẽ được quyết định trong N người tham gia bằng cách bỏ phiếu kín và lấy mức cao nhất thay vì là do 1 third party định giá.
Khôg có thì giờ đọc kỹ, anh em nào rảnh đọc thử giúp.
Hình như Tuan12T96 dự định sửa lại đề bài cho phù hợp như cái vụ chia kẹo cho người yêu à? Anh nghĩ em cứ thử new topic và post cái original version lên, anh em sẽ cùng nhau góp ý để chuyển ngữ sang tiếng Việt cho vui :-) Đương nhiên là không bỏ qua việc tìm giải pháp cho việc chia kẹo với 3 người này. Nhưng anh nghĩ là sẽ tốn thời gian đây. Vậy mình tách 2 topic ra để dễ theo dõi. Ok?

Tuan12T96

07-04-2004, 11:20 AM

Anh Sơn ơi, câu hỏi này không có ở version tiếng anh. Câu hỏi này nằm trong một số câu hỏi mà tụi em thường bàn bạc nói chuyện chơi với tụi classmates. Mai em thi, tối mai em viết bài nha.

Tuan12T96

07-04-2004, 11:23 AM