|
|
Post by Evgeny on Mar 18, 2022 1:31:29 GMT 4
სიბრტყეზე გავლებულია $n$ ცალი წრფე ისე, რომ წრფეების არცერთი სამეული არ გადის ერთსა და იმავე წერტილში. რამდენ არედ დაიყოფა სიბრტყე ამ წრფეებით?
|
|
aleksandretchagalidz
სრული წევრი
Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.
Posts: 131
|
Post by aleksandretchagalidz on Mar 18, 2022 13:48:18 GMT 4
მაქსიმუმ $\frac{n^2+n+2}{2}$ (Lazy caterer's sequence). ასევე მაგალითად თუ გვაქვს $n$ პარალელური წრფე გვექნება $n+1$ არე.
|
|
|
|
Post by lrapava on Mar 22, 2022 20:10:49 GMT 4
ვთქვათ გვაქვს სიბრტყეზე გავლებული $n$ ცალი წრფის სიმრავე $S$.
$A$ და $B$ წერტილები სხვადასხვა არეს მხოლოდ და მხოლოდ მაშინ მიეკუთვნებიან, როდესაც $S$ სიმრავლეში არსებობს ისეთი $a$ წრფე, რომელიც გადის $A$-სა და $B$-ს შორის (კვეთს $AB$ მონაკვეთს).
ვთქვათ გავავლეთ რამე $a$ წრფე, რომელიც $S$-ის წევრ წრფეებს ზუსტად $k$ წერტილში კვეთს. აშკარაა, რომ a გაივლის ზუსტად $k+1$ არეში და თითოეულს მხოლოდ ერთხელ გადაკვეთს. $a$-ც თუ ჩავამატეთ $S$-ში არეების რაოდენობა $k+1$-ით გაიზრდება (თითოერული არე რომელსაც $a$ გადის გაიყოფა ორად, რადგან ამ არეებში $a$-ს სხვადასხვა მხარეს მდებარე წერტილები სხვადასხვა არეების ნაწილებად ჩაითვლება. $k+1$ ძველ არეს ჩაანაცვლებს $2(k+1)$ ახალი არე, ჯამშე რაოდენობა შეიცვლება $k+1$-ით). შესაბამისად, რაც მეტ წერტილში გადაიკვეთება $a$ $S$-ის წევრ წრფეებთან, მით უფრო მეტით გაიზრდება არეების რაოდენობა თუ $a$-ს შემდგომ $S$-ში ჩავამატებთ. რადგან 2 წრფე მაქსიმუმ გადაიკვეთება 1 წერტილში, ოპტიმალურ შემთხვევაში $k$ ვერ იქნება $n$-ზე დიდი. $k$ იქნება $n$-ზე პატარა, თუ ის ერთ-ერთი წრფის მაინც პარალელურია ან $a$-ს ერთ წერტილში მაინც გადაკვეთს $S$-ის წევრი 2 მაინც წრფე (ვგულისხმობ, რომ $a$ ჯერ არაა $S$-ის წევრი). შესაბამისად, თუ ჩვენ გვინდა არეების რაოდენობა რაც შეიძლება მეტით გავზარდოთ, $a$ ისე უნდა გავავლოთ, რომ იგი არ იყოს არცერთი $S$-ის წევრი წრფის პარალელური და არ გადაიკვეთებოდს 1-ზე მეტთან მათგანთან 1 წერტილში.
დავასაბუთოთ, რომ ყოველთვის შეგვიძლია ასეთი $a$ წრფის გავლება. სიბრტყეზე ავირჩიოთ ნებისმიერი ისეთი $A$ წერტილი, რომელზეც $S$-ის წევრთაგან არცერთი გადის. რადგან $A$ წერილზე გაივლის უსასრულო რაოდენობით წრფე, რომელთაგან მაქსიმუმ $n$ იქნება $S$-დან რომელიმეს პარალელური და მაქსიმუმ $\frac{n(n-1)}{2}$ ($S$-ის წევრი ყველა წრფე ყველასთან რომც იკვეთებოდეს) ისეთი, რომელიც გადის $S$-ში შემავალი წრფეების რომელიმე წყვილის გადაკვეთის წერტილზე (და ეს ორივე სიდიდე ($n$ და $\frac{n(n-1)}{2}$ სასრულია)) $A$-ზე გაივლის უამრავი ისეთი წრფე, რომლიც $S$-ში შემავალი არც ერთი წრფის პარალელურია და S-ში შემავალ წრფეთა არც ერთი წყვილის გადაკვეთის წერტილზე გადის.
ჩვენ შეგვიძლია ვთქვათ, რომ ეს შეზღუდვები უნდა გავრცელდეს S-ში შემავალ ყოველ წრფეზე (თუ გვინდა, რომ შედეგად გვქონდეს რაც შეიძლება მეტი არე), რადგან არეების რაოდენობა არ არის დამოკიდებული წრფეების გავლების მიმდევრობაზე.
რადგან როდესაც S=0 გვაქვს 1 არე და ყოველი წრფის დამატებით (თუ ოპტიმალურად ვიმოქმედეთ) ჩვენ შეგვიძლია არეების რაოდენობა k+1-ით გავზარდოთ, სადაც k არის ამ წრფის გავლებამდე გავლებული წრფეების რაოდენობა, n წრფისთვის მაქსიმუმ შეგვეძლება $1+1+2+3+...+n = 1 + \frac{n(n+1)}{2} = \frac{n^{2}+n+2}{2}$
|
|
|
|
Post by lrapava on Mar 22, 2022 21:03:42 GMT 4
უი, ბოდიშს გიხდით.. ზედა ტყუილად გამომიქვეყნებია.. ერთ ორ რამეს იქედან გამოვიყენებ, რადგან დავწერე უკვე მაინც და..
წარმოვიდგინოთ, რომ გარკვეული მიმდევრობით ვხაზავთ $n$ წრფეს, რომელიც გადაიკვეთება $m$ წერტილში (რომელთაგანაც თითოეულზე გადის ზუსტად 2 წრფე). ზევით დაწერილიდან შეგვიძლია დავასკვნათ, რომ ყოველი ახალი გავლებული წრფე ზუსტად იმდენით გაზრდის არეების ჯამურ რაოდენობას, რამდენ უკვე არსებულ არეზეც გაივლის. წრფე გაივლის $k+1$ არეზე, სადაც $k$ წერტილების რაოდენობაა, რომლებშიც იკვეთება სხვა წრფეებთან. ანუ, ჯამში გვექნება $1 + (k_{1}+1) + (k_{2}+1) + ... + (k_{n}+1)$ არე (1 თავში რადგან თავიდან 1 არე გვაქვს), სადაც $k_{1} + k_{2} +... + k_{n} = m$, ამიტომაც $1 + (k_{1}+1) + (k_{2}+1) + ... + (k_{n}+1) = 1 + n + m$
|
|
