Problem 9.14
a) სტუდენტები იყვნენ ბიჭები, კომპანიები - გოგოები. 2 განსხვავებული დაწყვილების საპოვნელად გამოიყენეთ ტრადიციული და არატრადიციული რიტუალები.
b)თუ ტრადიციული და არატრადიციული მეთოდები ერთნაირ დაწყვილებებს მოგვცემენ, გამოდის რომ ერთადერთი სტაბილური დაწყვილება გვაქვს, თუ არადა, არა :)
Problem 9.17(a,b)
ადვილი ამოცანაა. c რთულია, მაგრამ ეგ არ გვაქვს.
Problem 9.18
პასუხი ამბროლას მითითებაშია:
ყოველ საავადმყოფოს გავუკეთოთ „კლონირება“, იმდენი რამდენი ადგილიც აქვთ გამოცხადებული (ვთქვათ, 3 ადგილი) და დავარქვათ, მაგალითად: ჩაჩავა 1, ჩაჩავა 2, ჩაჩავა 3.
Problem 9.19
პასუხი კვლავ ამბროლას მითითებაშია:
მითითება: დაალაგეთ წრიულად ბიჭი, გოგო, ბიჭი, გოგო, ბიჭი, გოგო. რაც უფრო ახლოა ადამიანი საათის ისრის მიმართულებით, მით უფრო მეტი იყოს მოწონება. შევაუღლოთ დიაგინალურად.
Problem 9.20
აიღეთ ამ ამოცანაში ლუწი n, მაგალითად, n=10 (კენტი n-ის შემთხვევაში დამტკიცება თითქმის იგივეა). q(B) იყოს რამდენმა გოგომ უთხრა უარი ბიჭ B–ს მოცემული მომენტისთვის. r(G) იყოს რამდენ ბიჭს უთხრა G გოგომ უარი მოცემული მომენტისთვის. გვაქვს თუ არა ტოლობა Σ q(B) = Σ r(G) საწყისი მომენტისთვის? ნებისმიერი მომენტისთვის?
კი, ნებისმიერ მომენტში გვაქვს, რამდენი უარიც თქვეს ჯამში გოგოებმა, იმდენი უარი მიიღეს ჯამში ბიჭებმა - პასუხი a-ზე.
b) მითითება 2: ბიჭი უიღბლოა → q(B) ≥ n/2, გოგო უიღბლოა → r(G) < n/2. არსი ისაა, რომ ყოველ ბიჭს n/2-ზე მეტმა გოგომ თუ უთხრა უარი, გამოდის (დირიხლეს პრინციპის მიხედვით) რომ ერთმა გოგომ მაინც თქვა n/2-ზე მეტი უარი, ანუ ერთი გოგო მაინცაა იღბლიანი. წინააღმდეგ შემთხვევაში, რომელიმე ბიჭია იღბლიანი.
6. დაასაბუთეთ, რომ ტრადიციული რიტუალი (Mating Ritual, p.158) მაქსიმალურად ხელსაყრელია ბიჭებისთვის და მაქსიმალურად არახელსაყრელია გოგონებისთვის. მითითება: გაარჩიეთ თეორემა 9.2.6 –ის და თეორემა 9.2.7–ის დამტკიცებები
ამტკიცებს, რომ ბიჭს ხვდება ოპტიმალური
Theorem 9.2.6. The Mating Ritual marries every boy to his optimal spouse.
Proof. Assume for the purpose of contradiction that some boy does not get his
optimal girl. There must have been a day when he crossed off his optimal girl
—otherwise he would still be serenading her or some even more desirable girl.
By the Well Ordering Principle, there must be a first day when a boy, call him
“Keith,” crosses off his optimal girl, Nicole.
According to the rules of the Ritual, Keith crosses off Nicole because Nicole has
a favorite suitor, Tom, and
Nicole prefers Tom to Keith (*)
(remember, this is a proof by contradiction :-) ).
Now since this is the first day an optimal girl gets crossed off, we know Tom
hasn’t crossed off his optimal girl. So
Tom ranks Nicole at least as high as his optimal girl. (**)
By the definition of an optimal girl, there must be some stable set of marriages in
which Keith gets his optimal girl, Nicole. But then the preferences given in (*)
and (**) imply that Nicole and Tom are a rogue couple within this supposedly
stable set of marriages (think about it). This is a contradiction.
ამტკიცებს, რომ გოგოს ხვდება პესიმალური
Theorem 9.2.7. The Mating Ritual marries every girl to her pessimal spouse.
Proof. Say Nicole and Keith marry each other as a result of the Mating Ritual. By the previous Theorem 9.2.6, Nicole is Keith’s optimal spouse, and so in any stable set of marriages,
Keith rates Nicole at least as high as his spouse. (+)
Now suppose for the purpose of contradiction that there is another stable set of marriages where Nicole does worse than Keith. That is, Nicole is married to Tom, and
Nicole prefers Keith to Tom (++)
Then in this stable set of marriages where Nicole is married to Tom, (+) and (++) imply that Nicole and Keith are a rogue couple, contradicting stability. We conclude that Nicole cannot do worse than Keith.
7. დაასაბუთეთ 157 გვერდზე მოყვანილი ლემა.
Lemma. There is no stable buddy matching among the four people in Figure 9.2.
Proof. We’ll prove this by contradiction.
Assume, for the purposes of contradiction, that there is a stable matching. Then
there are two members of the love triangle that are matched. Since preferences in
the triangle are symmetric, we may assume in particular, that Robin and Alex are
matched. Then the other pair must be Bobby-Joe matched with Mergatoid.
But then there is a rogue couple: Alex likes Bobby-Joe best, and Bobby-Joe
prefers Alex to his buddy Mergatoid. That is, Alex and Bobby-Joe are a rogue
couple, contradicting the assumed stability of the matching.
a) სტუდენტები იყვნენ ბიჭები, კომპანიები - გოგოები. 2 განსხვავებული დაწყვილების საპოვნელად გამოიყენეთ ტრადიციული და არატრადიციული რიტუალები.
b)თუ ტრადიციული და არატრადიციული მეთოდები ერთნაირ დაწყვილებებს მოგვცემენ, გამოდის რომ ერთადერთი სტაბილური დაწყვილება გვაქვს, თუ არადა, არა :)
Problem 9.17(a,b)
ადვილი ამოცანაა. c რთულია, მაგრამ ეგ არ გვაქვს.
Problem 9.18
პასუხი ამბროლას მითითებაშია:
ყოველ საავადმყოფოს გავუკეთოთ „კლონირება“, იმდენი რამდენი ადგილიც აქვთ გამოცხადებული (ვთქვათ, 3 ადგილი) და დავარქვათ, მაგალითად: ჩაჩავა 1, ჩაჩავა 2, ჩაჩავა 3.
Problem 9.19
პასუხი კვლავ ამბროლას მითითებაშია:
მითითება: დაალაგეთ წრიულად ბიჭი, გოგო, ბიჭი, გოგო, ბიჭი, გოგო. რაც უფრო ახლოა ადამიანი საათის ისრის მიმართულებით, მით უფრო მეტი იყოს მოწონება. შევაუღლოთ დიაგინალურად.
Problem 9.20
აიღეთ ამ ამოცანაში ლუწი n, მაგალითად, n=10 (კენტი n-ის შემთხვევაში დამტკიცება თითქმის იგივეა). q(B) იყოს რამდენმა გოგომ უთხრა უარი ბიჭ B–ს მოცემული მომენტისთვის. r(G) იყოს რამდენ ბიჭს უთხრა G გოგომ უარი მოცემული მომენტისთვის. გვაქვს თუ არა ტოლობა Σ q(B) = Σ r(G) საწყისი მომენტისთვის? ნებისმიერი მომენტისთვის?
კი, ნებისმიერ მომენტში გვაქვს, რამდენი უარიც თქვეს ჯამში გოგოებმა, იმდენი უარი მიიღეს ჯამში ბიჭებმა - პასუხი a-ზე.
b) მითითება 2: ბიჭი უიღბლოა → q(B) ≥ n/2, გოგო უიღბლოა → r(G) < n/2. არსი ისაა, რომ ყოველ ბიჭს n/2-ზე მეტმა გოგომ თუ უთხრა უარი, გამოდის (დირიხლეს პრინციპის მიხედვით) რომ ერთმა გოგომ მაინც თქვა n/2-ზე მეტი უარი, ანუ ერთი გოგო მაინცაა იღბლიანი. წინააღმდეგ შემთხვევაში, რომელიმე ბიჭია იღბლიანი.
6. დაასაბუთეთ, რომ ტრადიციული რიტუალი (Mating Ritual, p.158) მაქსიმალურად ხელსაყრელია ბიჭებისთვის და მაქსიმალურად არახელსაყრელია გოგონებისთვის. მითითება: გაარჩიეთ თეორემა 9.2.6 –ის და თეორემა 9.2.7–ის დამტკიცებები
ამტკიცებს, რომ ბიჭს ხვდება ოპტიმალური
Theorem 9.2.6. The Mating Ritual marries every boy to his optimal spouse.
Proof. Assume for the purpose of contradiction that some boy does not get his
optimal girl. There must have been a day when he crossed off his optimal girl
—otherwise he would still be serenading her or some even more desirable girl.
By the Well Ordering Principle, there must be a first day when a boy, call him
“Keith,” crosses off his optimal girl, Nicole.
According to the rules of the Ritual, Keith crosses off Nicole because Nicole has
a favorite suitor, Tom, and
Nicole prefers Tom to Keith (*)
(remember, this is a proof by contradiction :-) ).
Now since this is the first day an optimal girl gets crossed off, we know Tom
hasn’t crossed off his optimal girl. So
Tom ranks Nicole at least as high as his optimal girl. (**)
By the definition of an optimal girl, there must be some stable set of marriages in
which Keith gets his optimal girl, Nicole. But then the preferences given in (*)
and (**) imply that Nicole and Tom are a rogue couple within this supposedly
stable set of marriages (think about it). This is a contradiction.
ამტკიცებს, რომ გოგოს ხვდება პესიმალური
Theorem 9.2.7. The Mating Ritual marries every girl to her pessimal spouse.
Proof. Say Nicole and Keith marry each other as a result of the Mating Ritual. By the previous Theorem 9.2.6, Nicole is Keith’s optimal spouse, and so in any stable set of marriages,
Keith rates Nicole at least as high as his spouse. (+)
Now suppose for the purpose of contradiction that there is another stable set of marriages where Nicole does worse than Keith. That is, Nicole is married to Tom, and
Nicole prefers Keith to Tom (++)
Then in this stable set of marriages where Nicole is married to Tom, (+) and (++) imply that Nicole and Keith are a rogue couple, contradicting stability. We conclude that Nicole cannot do worse than Keith.
7. დაასაბუთეთ 157 გვერდზე მოყვანილი ლემა.
Lemma. There is no stable buddy matching among the four people in Figure 9.2.
Proof. We’ll prove this by contradiction.
Assume, for the purposes of contradiction, that there is a stable matching. Then
there are two members of the love triangle that are matched. Since preferences in
the triangle are symmetric, we may assume in particular, that Robin and Alex are
matched. Then the other pair must be Bobby-Joe matched with Mergatoid.
But then there is a rogue couple: Alex likes Bobby-Joe best, and Bobby-Joe
prefers Alex to his buddy Mergatoid. That is, Alex and Bobby-Joe are a rogue
couple, contradicting the assumed stability of the matching.
No comments:
Post a Comment