ამოცანა 1.1

ბ) ჩემს პასუხს ბ) კითხვაზე გავყოფ 2 ნაწილად. აქ რაც წერია, იქამდე დამოუკიდებლად მივედი. რომ გავაგრძელო და გავამარტივო ქვემოთ მიღ. ფორმულა გარკვეული ფორმულების გამოყვანის გზების მოფიქრება დამჭირდება. ეს ფორმულები ინტერნეტში დევს, მაგრამ გადავწყვიტე არ გამოვიყენო სანამ არ დავამტკიცებ ან გამოვიყვან, ან გავიგებ არსებულ დამტკიცებას. თუ დიდი ხნის განმავლობაში ვერც გამოვიყვანე ან ვერც მივხვდი არსებულ რომელიმე დამტკიცებას, ამ ფორმულებს სავარაუდოდ მაინც გამოვიყენებ, მაგრამ შეგატყობინებთ რომ ამ ფორმულების ჭეშმარტიებას ვერ ვასაბუთებ. ჯერჯერობით იმას დავდებ, რისი დასაბუთებაც ასე თუ ისე შემიძლია.

$F(X,n)$-ის გარკვეული $n$-სთვის მაქსიმალური შესაძლო მნიშვნელობა ავღნიშნოთ $G(n)$-ით.

როგორ იქმნება ახალი არეები ქორდის გავლებით და რამდენი?

ვთქვათ წინ გიდევთ რაიმე $X$-ის შესაბამისი ნახაზი და ცდილობთ რამე ახალი ქორდის გავლებას. აშკარაა, რომ შეიქმნება იმდენივე ახალი არე, რამდენჯერაც თქვენი გავლებული ქორდა „ჩამოაჭრის“ სიბრტის გარკვეულ ნაწილს უკვე არსებულ არეებს. რაიმე არიდან რამე 1 ახალი არის „ჩამოჭრისას“ ქორდა თავდაპირველი არის პერიმეტრს ორჯერ გადაკვეთს. არეების პერიმეტრები შეიძლება შედგებოდეს წრეწირის ნაწილებისგან/რკალებისგან და ქორდების ნაწილებისგან/მონაკვეთებისგან. განვიხილოთ $S$ წერტილთა სიმრავლე, რომელიც მოიცავს ახალი ქორდის გადაკვეთის წერტილებს არსებულ/„ძველ“ ქორდებთან და წრეწირთან (ახალო ქორდის ბოლოებს). თუ S-ში შემავალ წერტილებს მიმდევრობით შევაერთებთ, მივიღებთ $k-1$ მონაკვეთს, რომელთაგან თითოეული ნახაზზე არსებულ ერთ-ერთ არეს ერთ ახალ არეს „ჩამოაჭრის“ (სადაც $k$ $S$ სიმრავლეში შემავალი წერტილების რაოდენობაა).

მაქსიმუმ რამდენი ნაწილი შეიძლება ჩამოაჭრას ქორდამ?

ვთქვათ ქორდის ცალ მხარეს $l$ წერტილია, მეორე მხარეს კი - $r$. ახალი ქორდა გადაკვეთს ზუსტად $lr$ ქორდას, რადგან იმისთვის, რომ ახალმა ქორდამ რამე სხვა ქორდა გადაკვეთოს, უკვე არსებული ქორდის ბოლოები ახალი ქორდის სხვადასხვა მხარეს უნდა მდებარეობდნენ. ა) ნაწილში დავასაბუთეთ, რომ ყოველთვის შეგვიზლია მოვახერხოთ ისეთი ნახაზის აგება, რომ წრეწირის შიგნით თითოეულ წერტილზე არ გადიოდეს 2 ქორდაზე მეტი. ჯამში გამოდის, რომ ქორდა არეებს $lr+2$ წერილში კვეთს, ამ წერილების მიმდევრობით შეერთებით კი გამოგვივა $lr+1$ მონაკვეთი, რომელთაგანაც თითოეული წარმოქმნის ახალ არეს.

როგორ ვიპოვოთ $G(n+1)-G(n)$?

ვთქვათ გვაქვს $n$ წერტილისგან შემდგარი გარკვეული $X_{1}$ განლაგება ისეთი, რომ $F(X_{1}, n)=G(n)$ და გვინდა ჩავამატოთ ახალი $M$ წერტილი ისე, რომ მივიღოთ ახალი $X_{2}$ განლაგება, რომლისთვისაც $F(X_{2}, n+1) = G(n+1)$. უფრო სწორედ კი, გვაინტერესებს უშუალოდ განლაგება კი არა, არამედ $F(X_{2}, n+1) - F(X_{1}, n)$ (ანუ $G(n+1)-G(n)$). რადგან წრეწირზე უკვე შერჩეულია $n$ წერტილი და თითოეულთან M-დან უნდა გავავლოთ ახალი ქორდა, სულ მოგვიწევს $n$ ახალი ქორდის გავლება. მოდით თითოეული ქორდა გავარჩიოთ როგორც წინა აბზაცში. აშკარაა, რომ ეს $n$ ცალი ახალი გავლებული ქორდა წრეწირის შიგნით ერთმანეთთან არ გადაიკვეთება ($n$ წრფე, რომლებზედაც მდებარეობენ ეს ქორდები *წრეწირზე* გადაიკვეთება, სიბრტყეზე კი ნებისმიერ 2 წრფეს 1-ზე მეტი გადაკვეთის წერტილი ვერ ექნება). შესაბამისად ვიღებთ, რომ (იმის დაშვებით, რომ წრეწირის შიგნით არც ერთ წერტილზე 2 ქორდაზე მეტი არ გადის, რაც ადრე დავასაბუთეთ) ამ n ქორდის გავლებით დაგვემატება $ \sum_{i=0}^{n-1} (1+i\cdot(n-i-1))=\sum_{i=1}^{n-1}\left(i\cdot\left(n-i-1\right)\right)+n$

როგორ ვიპოვოთ $G(n)$?

რადგან ნებისმიერი ნატურალური $n$-სთვის შეგვიძლია გამოვთვალოთ $G(n+1)-G(n)$ და ვიცით $G(n)$-ის მნიშვნელობა ერთ-ერთი $n$-სთვის მაინც, შეგვიძლია გამოვთვალოთ $G(n)$ ნებისმიერი (ნატურალური) $n$-სთვის. ზუსტად ასე მუშაობს ჩემი ატვირთული პროგრამა. კოდში $G$ უბრალოდ $f$-ით მაქვს აღნიშნული, თვითონ ფუნქცია კი ავღწერე შემდეგნაირად: $G(1) = 1; G(n) = G(n-1) + diff(n-1)$, სადაც $diff(n) = \sum_{i=1}^{n-1}(i\cdot(n-i-1))+n$. სხვანაირად $G(n)$ შემდეგნაირად შეგვიძლია ჩავწეროთ: $G(n) = 1+\sum_{i=1}^{n}\left(\sum_{j=1}^{i-1}\left(j\cdot\left(i-j-1\right)\right)+i\right)$. როგორც დასაწყისში მოგახსენეთ, სამწუხაროდ (ჯერჯერობით) ამ ფუნქციას ამაზე უფრო ვერ ვამარტივებ. ვარაუდის დონეზე რამე 4th degree polynomial  დაჯდება ალბათ..