[Kombinatoryka] zagadka o samolotach okrążających kulę ziemską

azonips · Post autor: **azonips** » 21 paź 2010, o 08:36

Na wyspie jest baza samolotów. Każdy z samolotów może zabrać ze sobą tyle paliwa, żeby przelecieć połowę globu po kole wielkim. Jedynym źródłem paliwa jest wyspa, samoloty mogą także tankować w powietrzu (jeden przekazuje drugiemu jakąś część swojego paliwa). Zakładając, że nie traci się czasu na tankowanie i że nie stracimy żadnego samolotu powiedz ile co najmniej potrzeba samolotów do okrążenia całego globu.

Ta zagadka jest dość prosta, jednak mnie ciekawią jej uogólnienia:
a) co by było gdyby paliwa wystarczało tylko na pokonanie ćwierci globu?
b) co by było gdyby paliwa wystarczało tylko na pokonanie \(\displaystyle{ (1/2)^n}\) globu?
c) co by było gdyby paliwa wystarczało tylko na pokonanie \(\displaystyle{ 1/n}\) globu?
przy czym \(\displaystyle{ n=1,2,\ldots}\)

czy jest jakiś wzór rekurencyjny na liczbę samolotów z podpunktu b) ?

Dumel · Post autor: **Dumel** » 21 paź 2010, o 09:53

one startują wszystkie z tej wyspy, tak?

azonips · Post autor: **azonips** » 21 paź 2010, o 10:28

tak, zapomniałem dodać: wszystkie samoloty startują z wyspy

cyberciq · Post autor: **cyberciq** » 21 paź 2010, o 17:25

Ja tylko mam dwa małe pytania odnośnie zadania. Przez okrążenie rozumie się pełny przelot jednego samolotu po kole wielkim tak? i samolot traci paliwo tylko w wypadku, gdy pokona jakiś odcinek drogi?

justynian · Post autor: **justynian** » 21 paź 2010, o 19:10

i czy przez nietracenie żadnego samolotu mamy rozumieć że te inne też muszą dolecieć do wyspy z powrotem ?

Myrthan · Post autor: **Myrthan** » 21 paź 2010, o 19:14

Wszystkie pytania na tak, czy to aż takie trudne jest?

A skoro już napisałem:

Moim zdaniem co do tych pytań, nie będzie to możliwe bo nie ma możliwej kombinacji, że samolot który może mieć na pokładzie paliwo potrzebne do przelecenia 1/4 okręgu, nie ma możliwości pokonania całego okręgu, to raz.

A druga sprawa piszesz że interesują cię uogólnienia, jak sobie je wyobrażasz, skoro okrążenie nie będzie możliwe?, to jest minimalnie możliwe dla podanych już w zadaniu danych/stałych.

abc666 · Post autor: **abc666** » 21 paź 2010, o 19:28

Myrthan, a umiesz to udowodnić?

rumcajs · Post autor: **rumcajs** » 21 paź 2010, o 20:03

Myrthan, ta sytuacja jest możliwa.
Wystarczy, że jeden samolot pokonuje 1/16 drogi, przekazuje paliwo innemu samolotowi na 1/8 drogi, a z pozostałą 1/16 wraca na wyspę.I tak dalej.

Myrthan · Post autor: **Myrthan** » 21 paź 2010, o 20:08

Jednak cofam moje słowa (jeśli mogę ) Długopis i kartka czynią cuda, jak najbardziej jest to możliwe ale przy dużo większej ilości samolotów, sam na razie się nie będę podejmował szukać w tym zależności bo jest to troszkę czasochłonne.

Pozdrawiam

EDIT:

rumcajs pisze:Myrthan, ta sytuacja jest możliwa.
Wystarczy, że jeden samolot pokonuje 1/16 drogi, przekazuje paliwo innemu samolotowi na 1/8 drogi, a z pozostałą 1/16 wraca na wyspę.I tak dalej.

Jak najbardziej

azonips · Post autor: **azonips** » 21 paź 2010, o 20:10

rumcajs pisze:Myrthan, ta sytuacja jest możliwa.
Wystarczy, że jeden samolot pokonuje 1/16 drogi, przekazuje paliwo innemu samolotowi na 1/8 drogi, a z pozostałą 1/16 wraca na wyspę.I tak dalej.

No właśnie ja miałem w głowie taką metodę ,,teleskopową' (podobnie chyba kombinujesz). Np. dla przypadku 1/4 obsadzamy samoloty w obszarach \(\displaystyle{ (2\pi\cdot k/16,2\pi\cdot (k+1)/16)}\), \(\displaystyle{ k=0,1,2,\ldtos}\) i one przekazują sobie wzajemnie paliwo, wydłużając możliwą do przebycia drogę. Ale konkretnego algorytmu nie mam (może się w ogóle mylę???).

-- 21 paź 2010, o 19:18 --

cyberciq pisze:Ja tylko mam dwa małe pytania odnośnie zadania. Przez okrążenie rozumie się pełny przelot jednego samolotu po kole wielkim tak? i samolot traci paliwo tylko w wypadku, gdy pokona jakiś odcinek drogi?

tak; kiedy ,,wisi w powietrzu' nie przemieszczając się też silniki pracują przecież

-- 21 paź 2010, o 19:18 --

justynian pisze:i czy przez nietracenie żadnego samolotu mamy rozumieć że te inne też muszą dolecieć do wyspy z powrotem ?

tak

abc666 · Post autor: **abc666** » 21 paź 2010, o 20:39

A czy samoloty mogą w przeciwnych kierunkach wylecieć czy tylko w jednym?

azonips · Post autor: **azonips** » 21 paź 2010, o 20:41

abc666 pisze:A czy samoloty mogą w przeciwnych kierunkach wylecieć czy tylko w jednym?

tak, właśnie myślałem, żeby te ,,teleskopy' ,,budować' z dwóch stron...

abc666 · Post autor: **abc666** » 21 paź 2010, o 20:56

No to najbardziej optymalnie będzie chyba jeśli \(\displaystyle{ 2^k}\) samolotów przeleci \(\displaystyle{ \frac{1}{3}}\) możliwej drogi, połowa odda \(\displaystyle{ \frac{1}{3}}\) paliwa drugiej połowie i zacznie wracać. Pozostała połowa znowu przelatuje \(\displaystyle{ \frac{1}{3}}\) swojego zasięgu w tym czasie z bazy startuje \(\displaystyle{ 2^{k-2}}\) które "obsłuży" te wracające żeby mogły wrócić oraz \(\displaystyle{ 2^{k-2}}\) z których połowa poleci dalej i "obsłuży" te wracające z dalszej pozycji. Itd. Oczywiście tak z obu stron (z jednej o odcinek opóźnione).

Oczywiście to tylko takie luźne rozmyślania.

azonips · Post autor: **azonips** » 22 paź 2010, o 10:01

czyli, jeśli dobrze rozumiem Twoja odpowiedź to: dla pojemności baku wystarczającej na pokonanie \(\displaystyle{ (1/2)^n}\) globu wystarcza \(\displaystyle{ 2^n}\) samolotów. Czy tak?

Jeśli tak, to coś się nie zgadza, bo dla \(\displaystyle{ n=1}\) wystarczają \(\displaystyle{ 3}\) samoloty (dwa nie wystarczą)

abc666 · Post autor: **abc666** » 22 paź 2010, o 11:09

No nie, trzeba zsumować liczbę samolotów w kulminacyjnym momencie, chociaż jak sobie porysowałem widzę że te "teleskopy" mogą być sporo krótsze. Dla \(\displaystyle{ n=1}\) będzie

\(\displaystyle{ (1+1)+1=2^1+2^0=3}\)
dla \(\displaystyle{ n=2}\)
\(\displaystyle{ (1+1+2+4+8)+(1+1+2+4)=2^4+2^3=24}\)