კომბინატორიკა -> რიგი სალაროსთან, პროგრამისტებისა და მათემატიკოსებისათვის

არის კომბინატორიკის შემდეგი ამოცანა.

ამოცანა:
კინოთეატრის სალაროსთან დგას m+n კაცისაგან შემდგარი რიგი, ამასთან m რაოდენობის კაცს აქვს ლარიანი, ხოლო n რაოდენობისას 50 თეთრიანი. სალაროს გახსნამდე სალარო ცარიელია, ანუ ბილეთების გამყიდველს არა აქვს ხურდები (50 თეთრიანები). ამოცანა მდგომარეობს შემდეგში. რამდენი სხვადასხვა კომბინაციით შეიძლება განვალაგოთ ეს ხალხი ისე, რომ რიგში არ მოხდეს შეყოვნება ხურდების უქონლობის გამო.

პასუხი:
ხალხის არასასურველი განლაგება რიგში ტოლია m და n რიცხვებისაგან შემდგარი ყველა იმ გადაადგილებათა რაოდენობისა, რომლებიც იწყებიან ლარიანით. და ა. შ. რის შედეგადაც ვღებულობთ რომ არასასურველი გადაადგილებების რიცხვი ტოლია P(m-1, k+1) = (m+k)!/(m-1)!(k+1)!

ამოცანის პირობა, ამოხსნა და დასკვნა არის ჩაკრულ ფაილში,
მაგრამ ამ ფაილის მიხედვით ვერ გავიგე (კონკრეტულად ის ადგილი რომელიც შემოხაზულია). გთხოვთ ვინმე დამეხმარეთ და უფრო ადამიანურად ამიხსენით თორემ ჩემს ტვინს უკვე პატრონის ტვინი მო...ა.


მიმაგრებული სურათი (გადიდებისთვის დაუწკაპუნეთ სურათზე)

Zombi: სალამი ზომბი. ამოცანა წავიკითხე, მაგარია. თავად ვეცადე, ვერ ამოვხსენი. წავიკითხე ჩამოკიდებული პასუხი. არა მგონია მაგაზე უკეთ აიხსნებოდეს.

პეპა: დღეს კიდევ ერთი ორი საათი ვუჯექი ამ ამოცანას მაგრამ მაინც უშედეგოდ. უკვე ტვინი ცხვირიდან მექცევა. ალბათ ჩემი ტვინის ნეირონული ქსელის ის ნაწილი არ არის განვითარებული, რომელმაც ამ ამოცანის ამდაგვარი ახსნა უნდა გაიგოს. -=მაგარსა გთხოვ=- დამიწერე ამ ამოცანის შენი ენით ახსნა, "სურათში ჩაუხედავად" პირდაპირ ისე როგორც ეს შენ გაიგე.
* * *
კონკრეტულად კი აი რას ვერ ვგებულობ შემოხაზულში: ის ფაქტი რომ "мы сопоставили каждоий <<неблагоприатноий>> последователности из m букв Р и k букв П последовательность из m букв Р и k+1 букв П, начинающиюся с буквы Р" რანაირად არის დამოკიდებული ყველა ამნაირი <<неблагоприатноий>> შემთხვევების რაოდენობასთან.

This post has been edited by Zombi on 8 Apr 2004, 18:50

Zombi: ვოტ ჩტო:
მოი დავარქვათ ყველა არასასურველი განლაგების სიმრავლეს 'ძველი'. ეს არის ყველა ის მ-მაენთიანი და კ-50თეთრიანი ხალხის თანმიმდევრობა, რომელშიც ვაჭრობა წყდება.

რახან ამ სიმრავლის დათვლა გვიჭირს, გადავაკეთოთ ამ სიმრავლის თითოეული ელემენტი ახალ ელემენტად იქ აღწერილი წესით (წესი ხომ იასნია, დაწვრილებითაა აღწერილი).

ეს პროცესი შეგიძლია დაამოდელო როგორც ფუნქცია ფ ორ, 'ძველ' და 'ახალ' სიმრავლეს შორის.

ახალი სიმრავლე, კონსტრუქციის გამო, შედგება მ მაენთიანი და (კ+1) 50თეთრიანი განლაგების ელემენტებისაგან. და ყველა განლაგების თავში მაენთიანი დგას.

'ახალ' -ი სიმრავლის უპირატესობანი:

1. 'ახალ' სიმრავლეში ზუსტად იმდენივე ელემენტია რაც 'ძველში'.
ამაში შეგიძლია დარწმუნდე ორი ნაბიჯით:
ა). 'ახალი' სიმრავლის თითოეულ წევრს წ-ს შეგიძლია მოუძებნო ელემენტი ძ 'ძველ' სიმრავლეში, ისე რომ ფ-წესით გადაკეთებისას ფ(ძ)=წ.
მართლაც წ ელემენტში უფრო მეტი მაენთიანებია ვიდრე 50თეთრიანები. ანუ სადღაც, რომელიღაც პოზიციაზე მაინც მის (მის ჩათვლით) მარცხნივ მაენთიანების და 50 თეთრიანების ერთი და იმავე რაოდენობაა. ახლა თუ უკუ-ფ-ს გააკეთებ, ანუ მოაშორებ პირველ მაენთიანს, და პოზიიდან და მარცხნივ 50_თეთრიანებს და მაენთიანებს გაცვლი, მიიღებ თავდაპირველ განლაგებას, თან ისეთს, რომელიც ვაჭრობას აგდებს, იმიტომ რომ პოზიიდან (ჩათვლიანა)მარცხნივ უფრო მეტი მაენთიანია ვიდრე 50თეთრიანი.
მაგალითად თუ წ=მთ... ეს ნიშნავს რომ მეორე პოზიციის მარცხნიც ტოლი რაოდენობის, ერთი მ და ერთი თ-ა, და თუ ეხლა ამას უკუღმა გადააკეთებ ფ-თი, მიიღებ განლაგებას ძ=მ..., რომელშიც რიგი მაენთიანით იწყება და თავიდანვე წყდება.
ბ). მხოლოდ ერთი ასეთი ელემენტი შეგიძლია მოუძებნო. ან, სხვანაირად რო თქვა, თუ ძ1 და ძ2 'ძველი' სიმრავლის ორი განსხვავებული წევრია, მაშინ წ1=ფ(ძ1) და წ2=ფ(ძ2) ახალი სიმრავლის ორი განსხვავებული წევრია.
ა)+ბ) ნიშნავს რომ არსებობს ერთი ერთზე შესაბამისობა 'ძველ' სიმრავლეს (რომელიც არის ჩვენთვის საინტერესო წარუმატებელი განლაგებების ერთობლიობა) და 'ახალ' სიმრავლეს შორის.
2. 'ახალი' სიმრავლე შეგვიძლია დავითვალოთ. მასში მ მაენთიანი და (კ+1) 50თეთრიანი-ია, მაგრამ იმის გამო რომ პირველი სულ ერთი მაენთიანი დგას, ეს ერთი ელემენტი ვერავითარ ვარიაციას ვერ იძლევა, მიჭედებულია, და მთელი ვარიაცია მდგომარეობს მომდევნო (მ-1) მაენთიანი და (კ+1) 50თეთრიანის კომბინაციებში. რა კომბინაციების რაოდენობაც
გამოითვლება C([მ+1], [კ+1]).

ნამდვილად ჩახუჭუჭებული ამოცანაა, განსაკუთრებით მოდელის გადაკეთება (ფ ფუნქციის მოფიქრება) არის გონებამახვილური. ჩემი გამოცდილება ისაა, რომ მათში გასარკვევად აუცილებელი და საკმარისია მოთმინება.

good luck.
***
აი კიდე რა ა)+ბ) რატომ ნიშნავს რომ 'ძველ' და 'ახალ' სიმრავლეში თაბარი რაოდენობის ელემენტებია.
თუ ფ ფენქციას წარმოიდგენ როგორც ხაზს, რომელიც 'ძველი' და 'ახალი' სიმრავლის ელემენტებს აერთებს, მაშინ
ა) ნიშნავს რომ 'ახალი' სიმრავლის ყველა ელემენტთან ერთხელ მაინც მიდის ხაზი, (ფუნქციაზე ასეთ დროს ამბობენ რომ ის არის surjective)
ბ) ნიშნავს რომ არაუმეტეს ერთი ხაზი მიდის (ამ დროს ფუნქცია ფ-ზე იტყვიან რომ ის არის injective).
ფუნქცია რომელსაც ორივე თვისება აქვს (ამგვარ ფუნქციებზე ამბობენ bijective) შეგიძლია წარმოიდგინო როგორ ორი სიმრავლის ელემენტების ერთი ერთზე დამაკავშირებელი ხაზი. თუ ძველი და ახალი სიმრავლის ელემენტები ერთი-ერთზე უკევშირდება ერთმანეთს, მაშინ მათი რაოდენობა ტოლია.

This post has been edited by პეპა on 8 Apr 2004, 22:49