1. ერთი დღის განრიგი შეიცავს 5 გაკვეთილს. განსაზღვრეთ ასეთი განრიგების რაოდენობა თერთმეტი დისციპლინის არჩევისას.
2. კომისია შედგება თავმჯდომარის, მისი მოადგილის და კიდევ ხუთი ადამიანისგან. რამდენად შეუძლიათ კომისიის წევრებს შორის მოვალეობების განაწილება.
3. რამდენი გზით შეიძლება აირჩიონ სამი დამსწრე 20 კაციანი ჯგუფიდან?
4. რამდენი განსხვავებული ხმის კომბინაციის მიღება შეიძლება ათი შერჩეული ფორტეპიანოს კლავიშზე, თუ თითოეული ხმის კომბინაცია შეიძლება შეიცავდეს სამიდან ათამდე ბგერას.
5. ვაზაში არის 10 წითელი და 5 ვარდისფერი მიხაკი. რამდენი გზით შეიძლება ვაზიდან ერთი და იმავე ფერის ხუთი მიხაკის შერჩევა?
6. ტრამვაის მარშრუტების ნომრები ზოგჯერ მითითებულია ორი ფერადი განათებით. რამდენი სხვადასხვა მარშრუტის მონიშვნა შეიძლება რვა ფერის ფარნის გამოყენებით.
7. 15 კაციანი ჯგუფიდან შეირჩევა სარელეო რბოლის ოთხი მონაწილე 800 + 400 + 200 + 100. რამდენი გზით შეიძლება სპორტსმენების განთავსება ესტაფეტაზე.
8. ხუთკაციანი გუნდი 20 სხვა სპორტსმენთან ერთად ცურვაში ასპარეზობს. რამდენი გზით შეიძლება გადანაწილდეს ამ გუნდის წევრების მიერ დაკავებული ადგილები.
9. 12 კაციანი ჯგუფიდან ყოველდღიურად ირჩევენ ორ დამსწრე 6 დღის განმავლობაში. განსაზღვრეთ სხვადასხვა მოვალეობების სიის რაოდენობა, თუ თითოეული ადამიანი მორიგეობს ერთხელ.
კითხვები ფორუმზე განსახილველად
1. კომბინატორიკის ამოცანების ამოხსნა.
დამატებითი ლიტერატურის სია:
1. გორბატოვი ვ.ა. დისკრეტული მათემატიკის საფუძვლები. მ.: უმაღლესი სკოლა, 2000. - 544გვ.
2. V. A. Kofman, შესავალი გამოყენებითი კომბინატორიკაში. მ.: რადიო და კომუნიკაცია, 1982. 431წ.
სემინარი №7. გრაფიკის თეორია
სემინარის მიზანი:
განვიხილოთ გადაწყვეტილების მიღებისას გრაფიკების თეორიის პრაქტიკულ გამოყენებასთან დაკავშირებული საკითხები.
Გაკვეთილის გეგმა:
სემინა ეძღვნება გრაფიკის თეორიას. პირველი თემა არის ძირითადი ცნებები და ოპერაციები გრაფიკებზე, შემდეგ თემა ეძღვნება მარშრუტებს და ხეებს. სემინარი 2 საათია.
დავალება 1.ნახაზი 7.1 გვიჩვენებს გრაფიკებს - თითოეულში ოთხი წვერით. შეადარეთ გრაფიკები.
ბრინჯი. 7.1. ითვლის -
გადაწყვეტილება.
გრაფიკის შედარების შედეგები შემდეგია:
არაორიენტირებული;
ორიენტირებული;
სრული და = ;
ეს არ არის სრული, რადგან მიუხედავად იმისა, რომ წვეროების თითოეული წყვილი დაკავშირებულია კიდით, არსებობს მარყუჟი. ზოგჯერ სრული გრაფიკი არის გრაფიკი მარყუჟებით ყველა წვეროზე, რომელთა თითოეული წყვილი დაკავშირებულია კიდით. გრაფიკი არ შეესაბამება ამ განმარტებას.
ამ გრაფის ყველა წვერო იზოლირებულია (გრაფიკი კიდეების ცარიელი სიმრავლით, ანუ 0);
და ისინი ავსებენ ერთმანეთს: = და = ;
მულტიგრაფი, რადგან ის შეიცავს რამდენიმე კიდეს ადა ბ, ისევე, როგორც ედა ვ;
მიმართული, კანონიკურად შესაბამისი არამიმართულ გრაფთან;
და არ არის ტოლი, ვინაიდან მათ აქვთ სხვადასხვა კიდეები (4,1) - და (1,4) in ;
რეჟისორული მულტიგრაფი: კიდეები ადა ბარის მრავლობითი, მაშინ როცა ეს არ არის მულტიგრაფიული, ვინაიდან კიდეები მასშია ადა ბგანსხვავებულად ორიენტირებული.
დავალება 2.როგორია 7.2 გრაფიკის წვეროების ხარისხები.
ბრინჯი. 7.2. ითვლის და
გადაწყვეტილება.
ორივე გრაფიკს აქვს ოთხი წვერო: . არამიმართული გრაფის წვეროების ხარისხები: , , , , თუ შევთანხმდებით განვიხილოთ მარყუჟის წვლილი წვეროს ხარისხში. გრაფის ყველა წვერის ხარისხების ჯამი არის 14, ე.ი. ორჯერ მეტი კიდეების რაოდენობა გრაფიკზე:
სად მ=7 არის გრაფიკის კიდეების რაოდენობა.
მიმართული გრაფის წვეროების ხარისხები:
პირველი და მეორე ტიპის გრაფიკის წვეროების ხარისხების ჯამები ემთხვევა და რიცხვის ტოლია მგრაფიკის კიდეები: .
დავალება 3.ნახ. 7.3 აჩვენებს ქსელის გრაფიკს (ქსელის მოდელი) გარკვეული პროგრამის ოპერაციების (სამუშაოების) ნაკრების შესასრულებლად. მასში ისრები მიუთითებს ოპერაციებზე, წვეროებზე - მოვლენებზე, რომლებიც ახასიათებს ზოგიერთი ნაწარმოების დასასრულს და სხვის დასაწყისს. ისრების მიმართულება ასახავს ამ მოვლენების თანმიმდევრობას. განსაზღვრეთ ქსელის გრაფიკი სხვადასხვა გზით.
ბრინჯი. 7.3. ქსელის გრაფიკი
გადაწყვეტილება.
გამოსახული ქსელის მოდელი არის მიმართული გრაფიკი, რომელიც შეიძლება სრულად იყოს მითითებული სხვადასხვა გზით:
1) გრაფიკულად (იხ. სურათი ზემოთ);
2) ორი ნაკრების მითითებით: და ;
3) სიხშირის მატრიცა (ცხრილი 7.1). ქსელის მოდელის მახასიათებელია ის, რომ ისრები გამოდიან საწყისი მოვლენიდან 1 და შედიან მხოლოდ საბოლოო მოვლენა 6-ში. მაშასადამე, ინციდენტების მატრიცის პირველ რიგში არის ერთეულები მხოლოდ მინუს ნიშნით, ხოლო ბოლო რიგში მხოლოდ პლუსის ნიშნით;
ცხრილი 7.1. ინციდენტების მატრიცა
4) მიმდებარეობის მატრიცა (ცხრილი 7.2). მე-3 პუნქტში მითითებული მიზეზის გამო, მიმდებარე მატრიცის ბოლო რიგში მოთავსებულია მხოლოდ ნულები;
ცხრილი 7.2. მიმდებარეობის მატრიცა
5) კიდეების სია აშკარად განსაზღვრავს ქსელის გრაფიკს, რადგან გრაფის კიდეები აღინიშნება მათი ბოლო წვეროებით. ამ შემთხვევაში „კიდეების“ სვეტში მითითებული წვეროების რიცხვები განმეორდება სიის „ვერტიკების“ სვეტში და იმ თანმიმდევრობით, რომლითაც აღნიშნულია ისრები - კიდეები ამ შემთხვევაში.
დავალება 4.გააკეთეთ გრაფიკები ნახ. 7.4 ქვემოთ არის ჰამილტონის ციკლები, ჯაჭვები.
ბრინჯი. 7.4. ითვლის და
გადაწყვეტილება.
ჰამილტონის ციკლი, როგორც მარტივი ციკლი, რომელიც გადის გრაფიკის ყველა წვეროზე, არსებობს გრაფიკზე - ის მიდის კიდეების გასწვრივ ( a, b, c, d, e, f, g, q, n, m, l, h, a). B-ში ასევე არის ჰამილტონის ჯაჭვი, რისთვისაც საკმარისია ჰამილტონის ციკლის ნებისმიერი კიდის ამოღება.
გრაფაში არ არის ჰამილტონის ციკლი: წვეროების გავლა ა, ბ, გგრაფიკის გარე სამკუთხედი უნდა შეიცავდეს ყველა კიდეს, რომელიც მდებარეობს ამ მხარეზე, მაგრამ შემდეგ ის არ გადის სამკუთხედის ცენტრში მდებარე წვეროზე. დთუმცა, გრაფაში არსებობს ჰამილტონის ჯაჭვი, მაგალითად, დასაწყისი წვეროზე. ა, დასასრული დდა წვეროების დამაკავშირებელი კიდეების თანმიმდევრობა ა, ვ, ბ, გ, გ, ე, დ.
დავალება 5.უმოკლესი გზის პრობლემა. რა არის უმოკლესი გზა გრაფიკის ერთი წვეროდან მეორეზე გადასასვლელად. წარმოების მენეჯმენტის თვალსაზრისით: როგორ მივიდეთ A წერტილიდან B წერტილამდე უმოკლეს გზაზე (და, შესაბამისად, საწვავის და დროის მინიმალური მოხმარებით) დაწყება წვეროდან ბოლომდე. განვიხილოთ ნახ. 7.5.
ბრინჯი. 7.5. გრაფიკი
სიტუაციის აღწერა შესაძლებელია არა მხოლოდ მიმართული გრაფიკით რკალებისთვის მინიჭებული წონებით, არამედ ცხრილით (იხ. ცხრილი ქვემოთ). ამ ცხრილში ორი წვერო - ბილიკის დასაწყისი და ბილიკის დასასრული - დაკავშირებულია მოგზაურობის დროს. მაგიდაზე. 7.3 განიხილავს ბილიკებს შუალედური გაჩერებების გარეშე. უფრო რთული მარშრუტები შედგება ცხრილში ჩამოთვლილი ელემენტარული სეგმენტებისგან.
ცხრილი 7.3. საწყისი მონაცემები უმოკლესი გზის პრობლემისთვის.
პრობლემაში ისმება კითხვა: როგორ მივიდეთ 1-ლი წვეროდან მე-4 წვერომდე უმოკლეს გზაზე.
გადაწყვეტილება.შემოვიღოთ აღნიშვნა: თან(თ) - უმოკლესი ბილიკის სიგრძე 1-დან წვერომდე თ. (რადგან ნებისმიერი გასათვალისწინებელი გზა შედგება რკალებისგან და არის რკალების სასრული რაოდენობა, და თითოეული შედის მაქსიმუმ ერთხელ, უმოკლეს ბილიკზე სასრულად ბევრი პრეტენდენტია და ელემენტების სასრული რაოდენობა ყოველთვის მიიღწევა. ) განხილული პრობლემა არის გამოთვლა თან(4) და მითითება გზაზე, რომელზედაც მიღწეულია ეს მინიმუმი.
პირველადი მონაცემებისთვის წარმოდგენილი ნახ. ზემოთ და ცხრილში. ზემოთ, მხოლოდ ერთი ისარი შედის 3 წვეროზე, მხოლოდ 1 წვეროდან და ამ ისრის მახლობლად არის მისი სიგრძე 1-ის ტოლი, ამიტომ თან(3) = 1. უფრო მეტიც, აშკარაა, რომ თან(1) = 0.
მე-4 წვერომდე შეგიძლიათ მიხვიდეთ ან მე-2 წვეროდან, გაიარეთ გზა 4-ის ტოლი, ან მე-5 წვეროდან, როცა გაიარეთ 5-ის ტოლი გზა. ამიტომ, კავშირი
თან(4) = წთ(С(2) + 4; თან(5) + 5}.
ამგვარად, განხორციელდა პრობლემის რესტრუქტურიზაცია (გამარტივება) - С(4) აღმოჩენა შემცირდა С(2)-მდე და. თან(5).
მე-5 წვერომდე შეგიძლიათ მიხვიდეთ ან მე-3 წვეროდან, გაიარეთ გზა 2-ის ტოლი, ან მე-6 წვეროდან, როცა გაიარეთ 3-ის ტოლი გზა. ამიტომ, კავშირი
თან(5) = წთ ( თან(3) + 2; თან(6) + 3}.
ჩვენ ეს ვიცით თან(3) = 1. ამიტომ
თან(5) = წთ(3; თან(6) + 3}.
ვინაიდან აშკარაა, რომ თან(6) დადებითი რიცხვია, მაშინ ბოლო მიმართებიდან გამომდინარეობს, რომ თან(5) = 3.
მე-2 წვერომდე შეგიძლიათ მიხვიდეთ ან 1-ლი წვეროდან, გაიარეთ 7-ის ტოლი გზა, ან მე-3 წვეროდან, გაიარეთ 5-ის ტოლი გზა, ან მე-5 წვეროდან, როცა გაიარეთ 2-ის ტოლი გზა. ამიტომ, კავშირი
თან(2) = წთ (С(1) + 7; С(3) + 5; თან(5) + 2}.
ჩვენ ეს ვიცით თან(1) = 0, თან(3) = 1, თან(5) = 3. ამიტომ
თან(2) = წთ (0 + 7; 1 + 5; 3 + 2) = 5.
ახლა ჩვენ შეგვიძლია ვიპოვოთ თან(4):
თან(4) = წთ ( თან(2) + 4; თან(5) + 5) = წთ (5 + 4; 3 + 5) = 8.
ამრიგად, უმოკლესი ბილიკის სიგრძეა 8. ბოლო მიმართებიდან ირკვევა, რომ მე-4 წვეროზე უნდა გადავიდეს მე-5 წვერომდე. დავუბრუნდეთ გამოთვლას. თან(5), ჩვენ ვხედავთ, რომ მე-5 წვეროზე უნდა მივიდეთ მე-3 წვერომდე. ხოლო მე-3 წვერომდე შეგვიძლია მივიდეთ მხოლოდ 1-ლი წვეროდან. ასე რომ, უმოკლესი გზა ასეთია:
1 → 3 → 5 → 4 .
დავალება 6.მაქსიმალური ნაკადის პრობლემა როგორ (ანუ რა მარშრუტებზე) საქონლის მაქსიმალური შესაძლო ოდენობის გაგზავნა საწყისი წერტილიდან საბოლოო წერტილამდე, თუ პუნქტებს შორის ბილიკების ტევადობა შეზღუდულია.
ამ პრობლემის გადასაჭრელად, სატრანსპორტო სისტემის შესაბამისი მიმართული გრაფიკის თითოეული რკალი უნდა იყოს დაკავშირებული რიცხვთან - ამ რკალის სიმძლავრესთან. განვიხილოთ გრაფიკი ნახ. 7.6.
ბრინჯი. 7.6. გრაფიკი
საწყისი მონაცემები სატრანსპორტო სისტემის შესახებ, მაგალითად, ქარხანაში, ნაჩვენებია ნახ. 7.6., ცხრილის დაყენება ასევე შეგიძლიათ 7.4 ცხრილში.
ცხრილი 7.4. საწყისი მონაცემები უმოკლესი გზის პრობლემისთვის.
გადაწყვეტილება.
მაქსიმალური ნაკადის პრობლემის გადაწყვეტა შესაძლებელია შემდეგი მოსაზრებებიდან.
ცხადია, სატრანსპორტო სისტემის მაქსიმალური სიმძლავრე არ აღემატება 6-ს, რადგან სასტარტო წერტილიდან 0-დან არაუმეტეს 6 ერთეული ტვირთის გაგზავნა შესაძლებელია, კერძოდ, 2 ერთეული 1-ლ წერტილში, 3 ერთეული მე-2 და 1 ერთეული მე-3 წერტილში. .
შემდეგი, აუცილებელია იმის უზრუნველყოფა, რომ ტვირთის 6-ვე ერთეულმა 0-დან გამომავალი წერტილი მიაღწიოს საბოლოო 4 წერტილს. ცხადია, 2 ერთეული ტვირთი, რომელიც ჩამოვიდა 1-ლ წერტილში, შეიძლება პირდაპირ გაიგზავნოს მე-4 წერტილში. მე-2 წერტილში ჩასულ საქონელს ექნება დაიყოს: 2 ერთეული დაუყოვნებლივ გაიგზავნება მე-4 პუნქტში და 1 ერთეული - შუალედურ 3 წერტილში (2 და 4 პუნქტებს შორის მონაკვეთის შეზღუდული ტევადობის გამო). მე-3 პუნქტში მიიტანეს შემდეგი ტვირთები: 0 პუნქტიდან 1 ერთეული და 2 წერტილიდან 1 ერთეული. ვაგზავნით მე-4 პუნქტში.
ასე რომ, განსახილველი სატრანსპორტო სისტემის მაქსიმალური სიმძლავრე არის 6 ერთეული ტვირთი. ამავდროულად, არ გამოიყენება შიდა განყოფილებები (ტოტები) 1 და 2 პუნქტებს შორის, ასევე 1 და 3 პუნქტებს შორის. ტოტი 1 და 4 პუნქტებს შორის არ არის სრულად დატვირთული - 2 ერთეული ტვირთი იგზავნება მასთან ერთად. გამტარუნარიანობა 3 ერთეული.
გამოსავალი შეიძლება წარმოდგენილი იყოს ცხრილის სახით. 7.5.
ცხრილი 7.5. მაქსიმალური ნაკადის პრობლემის გადაჭრა
ომნიბუსი N 9-10 2007 წ.
მარშრუტის განათების ზღვის სული.
იდუმალი რამ არის ტრადიცია. თავიდან ყურადღებით აკვირდებიან მას, ცდილობენ გაუძლონ ყველა ნიუანსს, მიიყვანონ ცრურწმენამდე, შემდეგ უცებ აღმოაჩენენ, რომ ის არ ამართლებს მასზე დაკისრებულ მოლოდინს, არ აკმაყოფილებს ლოგიკას, არ აქვს სამეცნიერო დასაბუთება - და არღვევენ. ტრადიციით და შემდგომში სევდით შეამჩნიე, რომ მასთან დაკარგა რაღაც ლამაზი და აუცილებელი. . .
სულ ახლახან გაჩნდა ტრადიცია, რომ ტრამვაის მარშრუტებს მიენიჭათ არა მხოლოდ ციფრული, არამედ ფერადი აღნიშვნა - მარშრუტის შუქები აანთეს მარშრუტის ნომრის ორივე მხარეს, მანქანის წინ და უკან. ტრამვაის მოძრაობის ქუჩები გამოირჩეოდა განსაკუთრებული, სადღესასწაულო ელეგანტურობით, მძღოლები, მგზავრები, ტრასების მუშაკები, დისპეტჩერები და გადამრთველები ტრამვაის ნაკადში მარშრუტის განათებით ხელმძღვანელობდნენ, ბევრი ვერ წარმოიდგენდა ტრამვაის ფერადი განათების გარეშე. მოსკოვის მარშრუტის განათების სისტემა აშენდა ციფრებსა და ფერებს შორის ერთ-ერთ კორესპონდენციაზე. "1" ყოველთვის წითელია, "2" არის მწვანე, "5" არის ზეთისხილისფერი, "7" არის ლურჯი და ა.შ. მაგრამ ლენინგრადში შუქები "ლაპარაკობდნენ" სხვა ენაზე,და მათი კითხვა "მოსკოვში" ყველაზე ხშირად იწვევდა სისულელეს, რადგან არ იყო 10 შუქი, როგორც მოსკოვში, არამედ მხოლოდ ხუთი. ისინი კარგად განსხვავდებოდნენ და მათი კომბინაციები ყოველთვის ძალიან ლამაზად გამოიყურებოდა. თუმცა, ხუთი განათებიდან შესაძლებელია ორის 25 განსხვავებული კომბინაცია, ხოლო სანქტ-პეტერბურგ-ლენინგრადის მარშრუტები საბოლოოდ გახდა დაახლოებით 70, ამიტომ მარშრუტების ნიშნები შეიძლება განმეორდეს. მაგალითად, ორი თეთრი - 9, 43; წითელი და ყვითელი - 1, 51, 64; ლურჯი და წითელი - 33, 52, 54; ორი წითელი - 5, 36, 39, 45, 47. და მხოლოდ N 20 მარშრუტი იყო დანიშნული მოსკოვისა და პეტერბურგის სისტემების მიხედვით: მწვანე და თეთრი.
მოხდა ისე, რომ პეტერბურგში მარშრუტის განათება შეიცვალა. თუ მოხდა, რომ ერთ-ერთი მარშრუტის შეცვლის შემდეგ იგი მუშაობდა საკმარისად გრძელ მონაკვეთზე სხვა მარშრუტით იგივე ფერებით, მაშინ ერთ-ერთ ამ მარშრუტზე უნდა შეცვალოს განათების შემადგენლობა.
მარშრუტი N 4 დეკემბრისტების კუნძულიდან ვოლკოვის სასაფლაომდე მიდიოდა და ორი ყვითელი (ნარინჯისფერი) შუქით იყო მითითებული. შემდეგ მარშრუტი დაიხურა და იმავე ნომრით გაიხსნა სხვა ადგილას სხვადასხვა განათებით: ლურჯი + ლურჯი, რადგან მას საერთო მონაკვეთი ჰქონდა 35-ე ტრამვაისთან (ორი ყვითელი).
მარშრუტს N 43 თავდაპირველად ჰქონდა განათება: წითელი + თეთრი. როდესაც 1985 წელს პორტამდე გაგრძელდა, განათება შეიცვალა: თეთრი + თეთრი, რადგან მარშრუტმა დაიწყო მონაკვეთის გაზიარება ტრამვაი N 28-თან (წითელი + თეთრი). მარშრუტი 3 მონიშნული იყო მწვანე და თეთრი ფერებით. როდესაც განათება აღადგინეს 2007 წელს, კომბინაცია შეიცვალა ყვითელი + მწვანე. ამავდროულად, შეიცვალა კომბინაციები სხვა მარშრუტებზეც: 48 (იყო: თეთრი + თეთრი, ახლა: ლურჯი + ლურჯი); 61 (იყო: თეთრი + თეთრი, ახლა: თეთრი + ყვითელი) და ა.შ.
სანკტ-პეტერბურგის მარშრუტის განათების სისტემა, გარეგნულად მარტივი და რთული, დაკავშირებულია, პირველ რიგში, ევროპული ტრამვაის ქალაქების ტრადიციებთან. ასე რომ, უკვე 1907 წელს, გაზეთ Novoye Vremya-სადმი მიწერილი წერილი შეიცავდა "ვასილევსკის კუნძულის მაცხოვრებლების" თხოვნას, დაენერგათ ფერადი განათება ტრამვაზე, "როგორც ამას აკეთებენ საზღვარგარეთ, კერძოდ, მაინის ფრანკფურტში". ამჟამად ამსტერდამში ტრამვაის მარშრუტების ნიშანზე ფერადი დიაგონალური განათების სახით შემორჩენილია ყოფილი სისტემების ნაშთები. ეს ტრადიცია, თავის მხრივ, სავარაუდოდ, სანავიგაციო ნათურებს უბრუნდება. რატომ ზუსტად ზღვაზე და არა, ვთქვათ, რკინიგზაზე? დიახ, რადგან მარშრუტის განათება, ისევე როგორც ზღვის განათება, არ კრძალავს არაფერს, არ აიძულებს ვინმეს, არამედ უბრალოდ ეხმარება სიბნელეში ორიენტირებაში.
საზღვაო ნავიგაციის ნათურები გაშიფრულია სპეციალურ საზღვაო წიგნებში - ზღვების მცურავი მიმართულებები. მარშრუტის განათება ასევე აღწერილია ქალაქის სახელმძღვანელოებში. მათგან პირველი იყო „სანქტ-პეტერბურგის ტრამვაის მობილური გზამკვლევი“, რომელიც გამომცემლობა ე.ი. მარკუსი (1910).
პეტერბურგის მარშრუტის განათებებში გამოყენებული ფერების შემადგენლობა (თეთრი, წითელი, ნარინჯისფერი ან ყვითელი, მწვანე, ლურჯი) ოდნავ განსხვავდება ზღვის განათების ფერებისგან (თეთრი, წითელი, ნარინჯისფერი, მწვანე, ლურჯი, მეწამული).
თუ ყურადღებით დავაკვირდებით, შეგიძლიათ იპოვოთ სხვა მსგავსება, მაგრამ ბევრად უფრო მნიშვნელოვანია იმის გაგება, თუ რატომ დამკვიდრდა მარშრუტის განათების ასეთი არა მკაცრი სისტემა გონივრულ პეტერბურგში, რომელიც მოითხოვს მუდმივ კორექტირებას. პასუხი მარტივია: პეტერბურგი ხომ ზღვისპირა ქალაქია და მისთვის ერთნაირად დამახასიათებელია არქიტექტურული ფორმების სიმკაცრე და კარნავალის სისულელე, რაც იმას ნიშნავს, რომ დამახასიათებელია მარშრუტის განათების ხალისიანი ფერებიც.
2007 წელს ტრადიციამ ახალი სახე მიიღო. ახლა მანქანები აღჭურვილია LED ნათურებით მარშრუტის განათებისთვის. ისინი გაბრწყინდებიან არა მხოლოდ საღამოს ბინდიში, არამედ დღის შუქზეც.
დავალება ნომერი 3. ცხრილი 26 ვარიანტი No სამუშაო
ცხრილი 26
გ) მეტროს მატარებელი 16 გაჩერებას აკეთებს, სადაც ყველა მგზავრი ჩამოდის. რამდენი გზით შეიძლება გადანაწილდეს 100 მგზავრი მატარებელში ბოლო გაჩერებაზე ამ გაჩერებებს შორის?
კომბინატორიკის ელემენტები.
ჯამი და პროდუქტის წესები.
კომბინატორიკა (ან ნაერთების თეორია) არის მათემატიკის ფილიალი, რომელიც სწავლობს კითხვებს იმის შესახებ, თუ რამდენი განსხვავებული კომბინაცია, რომელიც აკმაყოფილებს გარკვეულ პირობებს, შეიძლება გაკეთდეს მოცემული ობიექტებისგან.
იმ შემთხვევაში, როდესაც A და B სიმრავლეთა კვეთა ცარიელი არ არის, მოქმედებს შემდეგი ტოლობა: n(AÈB) = n(A) + n(B) – n(AÇB).
სამი კომპლექტის გაერთიანებაში ელემენტების რაოდენობა შეგიძლიათ იხილოთ ფორმულით
n(AÈBÈC) = n(A) + n(B) + n(C) - n(AÇB) -n(AÇC) - n(BÇC) - - n(AÇBÇC)
მაგალითი.ჯგუფში შემავალი 40 მოსწავლიდან 35-მა წარმატებით ჩააბარა გამოცდა მათემატიკაში, ხოლო 37 რუსულ ენაში. ორმა მოსწავლემ ორივე საგანში არადამაკმაყოფილებელი შეფასება მიიღო. რამდენ სტუდენტს აქვს აკადემიური დავალიანება?
გადაწყვეტილება.დავუშვათ A არის მოსწავლეთა სიმრავლე, რომლებმაც მიიღეს არადამაკმაყოფილებელი შეფასება მათემატიკაში, მაშინ n(A) = 40 - 35 = 5; და B არის სტუდენტების ნაკრები, რომლებმაც მიიღეს არადამაკმაყოფილებელი ნიშანი რუსულ ენაში, შემდეგ n(B) = 40 - 37 = 3. მაშინ აკადემიური დავალიანების მქონე სტუდენტების რაოდენობაა n(AÈB). აქედან გამომდინარე, n(AÈB) = n(A) + n(B) - n(AÇB) = 5 + 3 – 2 = 6.
თუ AÇB = Æ, მაშინ n(AÈB) = n(A) + n(B)
ჯამის წესიდა ჩამოყალიბებულია შემდეგნაირად: თუ x ელემენტის არჩევა შესაძლებელია k გზით, ხოლო y ელემენტი m გზებით და, და x ელემენტის არჩევის არცერთი გზა არ არის იგივე, რაც y ელემენტის არჩევის ნებისმიერი გზა, მაშინ არჩევანი "x ან y" " შეიძლება გაკეთდეს k + m გზებით.
ნაკრებებისთვის ასევე გვაქვს n(А´В) = n(А) × n(В)
კომბინატორიკაში ამ წესს ე.წ პროდუქტის წესიდა ჩამოყალიბებულია შემდეგნაირად: თუ x ელემენტის არჩევა შესაძლებელია k გზით, და თუ ყოველი ასეთი არჩევანის შემდეგ ელემენტი y შეიძლება აირჩეს m გზებით, მაშინ შეკვეთილი წყვილი m გზების არჩევანი.
მაგალითი.არის 3 გზა A ქალაქიდან B ქალაქამდე და 2 გზა B-დან C-მდე. რამდენი გზა არსებობს A-დან C-მდე B-ით მგზავრობისთვის?
გადაწყვეტილება.თუ აღვნიშნავთ 1, 2, 3 რიცხვებს და B-დან C-მდე გზებს - ასოებს x და y, მაშინ A-დან C-მდე გზის თითოეული ვარიანტი მოცემულია რიცხვებისა და ასოების მოწესრიგებული წყვილით. მაგრამ ჩვენ შეგვიძლია ავირჩიოთ რიცხვი სამი გზით და ასო ორი გზით, ასე რომ, ასეთი მოწესრიგებული წყვილების რაოდენობაა 3 × 2 = 6.
საცხოვრებლები.
მოდით n(A) = m. k სიგრძის ტოპს (k £ m), რომლის კომპონენტებიც A სიმრავლის ელემენტებია და ყველა კომპონენტი წყვილად განსხვავებულია, ე.წ. განთავსება განმეორების გარეშე
ნებისმიერი A სიმრავლისთვის ისეთი, რომ n(A) = m, m ელემენტების შესაძლო განლაგების რაოდენობა აღინიშნება k-ით.
და ის გამოითვლება ფორმულის მიხედვით
მაგალითი.საჭადრაკო ტურნირში 5 სკოლის მოსწავლე და 15 მოსწავლე მონაწილეობს. რამდენი გზით შეიძლება გადანაწილდეს სკოლის მოსწავლეების მიერ დაკავებული ადგილები ტურნირზე, თუ ცნობილია, რომ ორ მონაწილეს არ დაუგროვდა ერთნაირი ქულა?
გადაწყვეტილება.ტურნირში სულ 20 მონაწილეა. შესაბამისად, 20 ადგილიდან სკოლის მოსწავლეები 5-ს განეკუთვნებიან. ამიტომ, პრობლემის გადაჭრა დაკავშირებულია კომპლექტის ელემენტებიდან 5 სიგრძის ყველა შესაძლო ტუპლის ფორმირებასთან, რომელშიც არის 20 ელემენტი, ანუ ჩვენ ვართ. საუბარია განლაგებაზე 5 ელემენტის 20 ელემენტის გამეორების გარეშე.
მოდით n(A) = m. k სიგრძის ტოპი, რომლის კომპონენტებია A სიმრავლის ელემენტები, ეწოდება განთავსება გამეორებებით m ელემენტებიდან k ელემენტამდე.
ნებისმიერი A სიმრავლისთვის ისეთი, რომ n(A) = m, m ელემენტების გამეორებით შესაძლო განლაგების რაოდენობა k-ით აღინიშნება და გამოითვლება ფორმულით.
მაგალითი.არის 5 სხვადასხვა სკამი და 7 რულონი სხვადასხვა ფერის პერანგზე. რამდენი გზით შეიძლება სკამების გადახურვა?
გადაწყვეტილება.ვინაიდან სკამები განსხვავებულია, თითოეული პერანგი არის 5 სიგრძის ტუპი, რომელიც შედგება ქსოვილის ფერების მოცემული ნაკრების ელემენტებისაგან, რომელიც შეიცავს 7 ელემენტს. ეს ნიშნავს, რომ სკამების პერანგის იმდენი ხერხი არსებობს, რამდენიც ასეთი ტუპლები, ანუ 7 ელემენტის 5-ით გამეორებით მოწყობა. ვიღებთ .
პერმუტაციები.
მოდით n(A) = m. პერმუტაცია გამეორების გარეშე m ელემენტებიდან ნებისმიერი მოწესრიგებული m-ელემენტების სიმრავლე ეწოდება.
m ელემენტების სხვადასხვა პერმუტაციების რაოდენობა უდრის თანმიმდევრული ნატურალური რიცხვების ნამრავლს 1-დან m ჩათვლით, ე.ი.
მაგალითი.რამდენი განსხვავებული ხუთნიშნა რიცხვის დაწერა შეიძლება 0, 1, 2, 3, 4 ციფრების გამოყენებით, თუ რიცხვში არცერთი ციფრი არ მეორდება ორჯერ?
გადაწყვეტილება.ხუთი ციფრის ყველა შესაძლო პერმუტაციის რაოდენობაა P 5 = 5!. და რადგან რიცხვი ნული ვერ დაიკავებს პირველ ადგილს, სასურველი რიცხვია:
P 5 - P 4 \u003d 5! - 4! = 120 - 24 = 96.
პერმუტაცია გამეორებებითელემენტებიდან a, b,…,l,რომელშიც ეს ელემენტები მეორდება m 1, m 2, ..., m k-ჯერ, შესაბამისად, ეწოდება სიგრძის ტოპი m = m 1 + m 2 + ... + m k, რომლის კომპონენტებს შორის ახდება მ 1 ჯერ, ბ-მ 2-ჯერ და ასე შემდეგ ლ- მკ ჯერ.
პერმუტაციების რაოდენობა გამეორებით აღინიშნება სიმბოლოთი
სხვადასხვა პერმუტაციების რაოდენობა ელემენტების გამეორებით a, b,…,l,რომელშიც ეს ელემენტები მეორდება m 1, m 2, ..., m k-ჯერ, შესაბამისად, განისაზღვრება ფორმულით
მაგალითი.რამდენი რვანიშნა რიცხვის დაწერა შეიძლება 1, 3, 5 რიცხვების გამოყენებით, იმ პირობით, რომ რიცხვი 1 განმეორდება ოთხჯერ თითოეულ რიცხვში, 3 და 5 რიცხვები - 2-ჯერ?
გადაწყვეტილება.სასურველი რიცხვი არის სხვადასხვა პერმუტაციების რაოდენობა 1, 3, 5 რიცხვების გამეორებით, რომლებშიც რიცხვი 1 მეორდება ოთხჯერ, ხოლო რიცხვები 3 და 5 მეორდება ორჯერ. ამრიგად, ფორმულის მიხედვით, გვაქვს: 
.
კომბინაციები.
m-ელემენტების სიმრავლის ნებისმიერი k-ელემენტის ქვესიმრავლე (k £ m) ეწოდება კომბინაცია გამეორების გარეშე m ელემენტებიდან k-ით.
m ელემენტების სხვადასხვა კომბინაციების რაოდენობა k-ით აღინიშნება სიმბოლოთი
მაგალითი.რამდენი გზით შეგიძლიათ აირჩიოთ სამი დამსწრე 30 სტუდენტიდან?
გადაწყვეტილება.ვინაიდან დამსწრეთა არჩევის თანმიმდევრობა არ თამაშობს როლს, პრობლემა ეხება კომპლექტიდან არჩევას, რომელშიც არის 30 ქვეჯგუფის ელემენტი, რომლებიც შეიცავს თითოეულს სამ ელემენტს, ანუ კომბინაციები სამი ელემენტის ოცდაათი გამეორების გარეშე.
აქედან გამომდინარე, 
.
კომბინაცია გამეორებებთანმოცემული m სხვადასხვა ტიპის ელემენტებიდან k ელემენტების მიხედვით, k ელემენტების შემცველ ნებისმიერ კოლექციას უწოდებენ, რომელთაგან თითოეული არის მითითებული ტიპის ერთ-ერთი ელემენტი.
სხვადასხვა კომბინაციების რაოდენობა m ელემენტების გამეორებით k ელემენტებით აღინიშნა სიმბოლოთი.
k ელემენტების m ტიპის ელემენტების გამეორებით სხვადასხვა კომბინაციების რაოდენობა განისაზღვრება ფორმულით
მაგალითი. ფოსტა ყიდის ოთხი სახის საფოსტო ბარათს. რამდენი გზით შეიძლება აქ 9 ღია ბარათის ყიდვა?
გადაწყვეტილება. ღია ბარათების შეძენის გზების რაოდენობა უდრის სხვადასხვა კომბინაციების რაოდენობას 4 ელემენტის გამეორებით 9-ით, ანუ ტოლია 
.
სასრულ სიმრავლის ქვესიმრავლეების რაოდენობა.
მოდით n(A) = m.
A სიმრავლის ყველა ქვეჯგუფების რაოდენობაა 2 n.
სავარჯიშო 6
1. კლასში არის 30 ადამიანი, რომელიც ესწრება ფაკულტატურ გაკვეთილებს ფიზიკა-მათემატიკაში. ცნობილია, რომ ორივე საგანს სიღრმისეულად სწავლობს 10 ადამიანი, მათემატიკას კი 25. რამდენი ადამიანი ესწრება არჩევით გაკვეთილებს მხოლოდ ფიზიკაში?
2. 50 მოსწავლიდან 20 საუბრობს გერმანულად, 15 კი ინგლისურად. რამდენი შეიძლება იყოს ორივე ენის მცოდნე სტუდენტების რაოდენობა; ერთი ენა მაინც იცი?
3. 100 ადამიანიდან 28 სწავლობს ინგლისურს, 30 – გერმანულს, 10 – ფრანგულს, 5 – გერმანულ და ფრანგულს, 15 – გერმანულ და ინგლისურს, 6 – ინგლისურ და ფრანგულს. სამივე ენას სწავლობს 3 სტუდენტი. რამდენი სტუდენტი სწავლობს მხოლოდ ერთ ენას? რამდენი სტუდენტი არ სწავლობს არცერთ ენას?
ამოცანები დამოუკიდებელი მუშაობისთვის თემაზე "კომბინატორიკა" .
1. ერთი დღის განრიგი შეიცავს 5 გაკვეთილს სხვადასხვა საგანში. განსაზღვრეთ ასეთი განრიგების რაოდენობა 11 პუნქტიდან არჩევისას.
2. კომისია შედგება თავმჯდომარის, მისი მოადგილის და კიდევ ხუთი ადამიანისგან. რამდენი გზით შეუძლიათ კომისიის წევრებს თავმჯდომარისა და მოადგილის მოვალეობების ერთმანეთთან განაწილება?
3. რამდენი გზით შეიძლება აირჩიონ სამი დამსწრე 20 კაციანი ჯგუფიდან?
4. რამდენი განსხვავებული ხმის კომბინაციის მიღება შეიძლება ათი შერჩეული ფორტეპიანოს კლავიშზე, თუ თითოეული ხმის კომბინაცია შეიძლება შეიცავდეს სამიდან ათამდე ბგერას?
5. ვაზაში არის 10 წითელი და 5 ვარდისფერი მიხაკი. რამდენი გზით შეიძლება ვაზიდან ერთი და იმავე ფერის ხუთი მიხაკის შერჩევა?
6. ტრამვაის მარშრუტების ნომრები ზოგჯერ მითითებულია ორი ფერადი განათებით. რამდენი სხვადასხვა მარშრუტის მონიშვნა შეიძლება რვა ფერის ფარნის გამოყენებით?
7. ჩემპიონატი, რომელშიც 16 გუნდი მონაწილეობს, ტარდება ორ ტურად (ანუ თითო გუნდი ერთმანეთს ორჯერ ხვდება). განსაზღვრეთ გასამართი შეხვედრების რაოდენობა.
8. საკეტი იხსნება მხოლოდ იმ შემთხვევაში, თუ აკრიფეთ გარკვეული სამნიშნა ნომერი. მცდელობა შედგება მოცემული ხუთი ციფრიდან სამი ციფრის შემთხვევით აკრეფაში. ნომრის გამოცნობა შესაძლებელი იყო ყველა შესაძლო მცდელობიდან მხოლოდ ბოლოზე. რამდენი მცდელობა იყო წარმატებულამდე?
9. 15 კაციანი ჯგუფიდან შეირჩევა ოთხი ესტაფეტის მონაწილე 800 + 400 + 200 + 100. რამდენი გზით შეიძლება სპორტსმენების განთავსება ესტაფეტის ეტაპებზე?
10. ხუთკაციანი გუნდი ცურვაში ასპარეზობს 20 სხვა სპორტსმენთან ერთად. რამდენი გზით შეიძლება გადანაწილდეს ამ გუნდის წევრების მიერ დაკავებული ადგილები?
11. რამდენი ხერხით შეიძლება საჭადრაკო დაფაზე ორი წვერის დადება, რომ ერთმა მეორე ვერ დაიჭიროს? (ერთ მწვერვალს შეუძლია დაიჭიროს მეორე, თუ ის იმავე რანგის ან ფაილზეა ჭადრაკის დაფაზე.)
12. ჭადრაკის დაფაზე ათავსებენ სხვადასხვა ფერის ორი ღერი, რათა თითოეულმა შეძლოს მეორის დაჭერა. რამდენი ასეთი ლოკაცია არსებობს?
13. კონკურსში რვა მონაწილის შესრულების რიგითობა განისაზღვრება წილისყრით. გათამაშების რამდენი განსხვავებული შედეგია შესაძლებელი?
14. ოცდაათი ადამიანი იყოფა სამ ჯგუფად I, II და III თითო ათი კაციანი. რამდენი განსხვავებული ჯგუფის შემადგენლობა შეიძლება იყოს?
15. რამდენი ოთხნიშნა რიცხვი იყოფა 5-ზე შეიძლება გაკეთდეს 0, 1, 3, 5, 7 რიცხვებიდან, თუ თითოეული რიცხვი არ უნდა შეიცავდეს ერთნაირ ციფრებს?
16. რამდენი განსხვავებული მანათობელი რგოლი შეიძლება გაკეთდეს წრის გარშემო 10 მრავალფეროვანი ნათურის მოთავსებით (რგოლები ერთნაირად ითვლება, თუ ფერები ერთნაირი თანმიმდევრობითაა)?
17. წიგნების თაროზე 30 ტომია. რამდენი ხერხით შეიძლება მათი დალაგება ისე, რომ პირველი და მეორე ტომი ერთმანეთის გვერდით არ დადგეს?
18. ოთხმა მსროლელმა უნდა დაარტყას რვა სამიზნე (თითოეული ორი). რამდენი ხერხით შეუძლიათ მათ შორის მიზნების განაწილება?
19. 12 კაციანი ჯგუფიდან ყოველდღიურად 6 დღის განმავლობაში ირჩევენ ორ მორიგეს. განსაზღვრეთ სხვადასხვა მოვალეობების სიის რაოდენობა, თუ თითოეული ადამიანი მორიგეობს ერთხელ.
20. 0, 1, 2, 3, 4, 5 რიცხვებისგან შედგენილი რამდენ ოთხნიშნა რიცხვს შეიცავს რიცხვი 3 (ციფრებში რიცხვები არ მეორდება)?
21. ათი ჯგუფი ჩართულია ზედიზედ ათ კლასში. განრიგის რამდენი ვარიანტია, რომელ ჯგუფში 1 და 2 იქნება მიმდებარე კლასებში?
22. ტურნირში 16 მოჭადრაკე მონაწილეობს. განსაზღვრეთ პირველი ტურის სხვადასხვა განრიგის რაოდენობა (განრიგები განსხვავებულად ითვლება, თუ ისინი განსხვავდებიან მინიმუმ ერთი თამაშის მონაწილეებში; არ არის გათვალისწინებული ფიგურების ფერი და დაფის რაოდენობა).
23. სამშენებლო მოედნის ხუთ სართულზე მიწოდებულია ექვსი ყუთი სხვადასხვა მასალისგან. რამდენი გზით შეიძლება მასალების დადგენა იატაკის მიხედვით? რამდენი ვარიანტით მიეწოდება რომელიმე მასალა მეხუთე სართულზე?
24. ორმა ფოსტალიონმა უნდა მიაწოდოს 10 წერილი 10 მისამართზე. რამდენი გზით შეუძლიათ მათ სამუშაოს განაწილება?
©2015-2019 საიტი
ყველა უფლება ეკუთვნის მათ ავტორებს. ეს საიტი არ აცხადებს ავტორობას, მაგრამ უზრუნველყოფს უფასო გამოყენებას.
გვერდის შექმნის თარიღი: 2016-08-20
ადრე ტრამვაის ნომრებს ორი ფერადი ფარანი აწერდნენ. რამდენი სხვადასხვა მარშრუტის მონიშვნა შეიძლება რვა სხვადასხვა ფერის განათების გამოყენებით?
პასუხები:
ფორმულა იქნება: 8²=64 64 სხვადასხვა მარშრუტი.
მსგავსი კითხვები
- გაიხსენეთ რენესანსის ეპოქის არქიტექტურული შენობები და ქანდაკებები, რომლებსაც აქვთ მსგავსი რენესანსის საკათედრო ტაძარი და ვერროკიოს ქანდაკება. ჩაწერეთ მათი სახელები.
- ხარვეზების ნაცვლად ჩასვით შემოთავაზებული სიიდან შესაბამისი სიტყვების რიგითი ნომრები. სიაში სიტყვები მოცემულია მხოლობით რიცხვში, სახელობითში. გთხოვთ გაითვალისწინოთ: სიაში უფრო მეტი სიტყვაა, ვიდრე ტექსტში ხარვეზები! კლასიფიკაცია, რომელიც დამოკიდებულია ____ წევრობის შეძენის საფუძვლებსა და პირობებზე, ფართოდ გამოიყენება ____-ში, განასხვავებს პერსონალს ____ პარტიებში. პირველები გამოირჩევიან იმით, რომ პოლიტიკური ___ ჯგუფის ირგვლივ ყალიბდებიან და მათი სტრუქტურის საფუძველი აქტივისტთა კომიტეტია. საკადრო პარტიები, როგორც წესი, იქმნება „ზემოდან“ სხვადასხვა ___ ფრაქციის, პარტიული ბიუროკრატიის გაერთიანებების საფუძველზე. ასეთი პარტიები, როგორც წესი, ააქტიურებენ თავიანთ საქმიანობას მხოლოდ ___ დროით. სხვა პარტიები ცენტრალიზებული, კარგად დისციპლინირებული ორგანიზაციებია. ისინი დიდ მნიშვნელობას ანიჭებენ პარტიის წევრების ერთიანობას. ასეთი პარტიები ყველაზე ხშირად იქმნება "ქვემოდან", პროფკავშირული და სხვა ___ მოძრაობების საფუძველზე, რომლებიც ასახავს სხვადასხვა სოციალურ ინტერესებს. ჯგუფები 1) სოციოლოგია 10) არჩევნები 2) საჯარო 11) ნორმა 3 ფაქტორი 12) პარტიული 4) საარჩევნო 13) საპარლამენტო 5) ეროვნული 14) კონსენსუსი 6) საზოგადოება 15) იდოლოგიური 7) მასობრივი 16) სისტემა 8) იმპიჩმენტი 17) ლიდერი 9) პოლიტოლოგია
- No 1 ამოხსნა: 28/5 * 4 No 2 კოორდინატთა წრფეზე _______o____|___|___|___________> a -1 0 1 1) a -1 0 1 1) a; a -1;\frac(1)(a) 2) a;\frac(1)(a);a-1 3) a-1;\frac(1)(a);a 4)a-1; a;\frac(1)(a)
- არის რიცხვი 2008*2011*2012*2014+1 ზუსტი კვადრატი
- ახალაშენებულ კორპუსში სულ 300 ბინაა, პირველ დღეს 120 ბინა იყო დაკავებული, მეორე დღეს - დანარჩენის მესამედი, რამდენი ბინა დარჩა დასასახლებლად?
- ტოლიკმა გაამრავლა ხუთნიშნა რიცხვი მისი ციფრების ჯამზე. შემდეგ ტოლიკმა გაამრავლა შედეგი მისი (შედეგის) ციფრების ჯამზე. გასაკვირია, რომ ისევ ხუთნიშნა რიცხვი აღმოჩნდა. რა რიცხვი გაამრავლა ტოლიკმა პირველად? (იპოვეთ ყველა შესაძლო პასუხი.)
