Proste sformułowanie - trudny problem
: 13 kwie 2010, 11:16
Witam wszystkich forumowiczów!
Zakładam ten wątek ponieważ od dłuższego czasu zmagam się z pewnym problemem który nawet nie za bardzo wiem jak sklasyfikować, a który ma bardzo proste sformułowanie. Być może jest on niealgorytmiczny. Można go ująć jako pytanie o własność stopu dla pewnego programu. A co ten program ma robić?
Otóż weźmy sobie liczbę (3^a)/(2^a) oraz liczbę (3^a-1)/(2^a-1). Niech "a" będzie dowolną liczbą naturalną i niech program poczynając od a=1 oblicza kolejno liczbę (3^a)/(2^a) oraz (3^a-1)/(2^a-1) i sprawdza czy pomiędzy owymi liczbami znajduje się jakaś liczba całkowita. Jeśli takową znajdzie to niech się zatrzyma. Pytanie, czy taki program kiedykolwiek się zatrzyma? Nie ma znaczenia czy przyjmiemy, że przedziały są obustronnie domknięte czy otwarte, gdy założymy przedziały domknięte, to znajdziemy z pewnością jedno rozwiązanie dla a=1 (bo (3^1-1)/(2^1-1)=2), jednak pytanie o inne przypadki nadal pozostanie otwarte. Przyjmijmy jednak dla jasności, że są one obustronnie otwarte.
Próbowałem szukać rozwiązania na własną rękę, sprawdziłem pierwsze przypadki dla a<50, niestety nie jestem informatykiem a programy typu exel czy zwykłe kalkulatory na niewiele tu się zdają. Żeby sprawdzić większą ilość przypadków potrzeba naprawdę dokładnych obliczeń na dużych liczbach.
Oczywiście wcześniej próbowałem również na wszelkie sposoby rozstrzygnąć problem za pomocą metod stricte matematycznych, ale okazuje się, że jest to zadanie gargantuicznie trudne, szczególne w stosunku do niepozornego sformułowania i pewnego intuicyjnie narzucającego się przekonania, iż poszukiwanych przypadków chyba nie ma i hipotetyczny program nigdy się nie zatrzymuje. W końcu przedziały pomiędzy kolejnymi liczbami są coraz mniejsze i dążą do 0. Jednak właśnie z uwagi na trudność matematycznego dowodu, że takich przypadków nie ma coś mi mówi aby sprawdzić większą część liczb, a może rozwiązanie się znajdze.
Być może ktoś z Was bedzie w stanie przesunąć tą skromną granicę a=50, albo znaleźć kontrprzykład i rostrzygnąć problem?
Zakładam ten wątek ponieważ od dłuższego czasu zmagam się z pewnym problemem który nawet nie za bardzo wiem jak sklasyfikować, a który ma bardzo proste sformułowanie. Być może jest on niealgorytmiczny. Można go ująć jako pytanie o własność stopu dla pewnego programu. A co ten program ma robić?
Otóż weźmy sobie liczbę (3^a)/(2^a) oraz liczbę (3^a-1)/(2^a-1). Niech "a" będzie dowolną liczbą naturalną i niech program poczynając od a=1 oblicza kolejno liczbę (3^a)/(2^a) oraz (3^a-1)/(2^a-1) i sprawdza czy pomiędzy owymi liczbami znajduje się jakaś liczba całkowita. Jeśli takową znajdzie to niech się zatrzyma. Pytanie, czy taki program kiedykolwiek się zatrzyma? Nie ma znaczenia czy przyjmiemy, że przedziały są obustronnie domknięte czy otwarte, gdy założymy przedziały domknięte, to znajdziemy z pewnością jedno rozwiązanie dla a=1 (bo (3^1-1)/(2^1-1)=2), jednak pytanie o inne przypadki nadal pozostanie otwarte. Przyjmijmy jednak dla jasności, że są one obustronnie otwarte.
Próbowałem szukać rozwiązania na własną rękę, sprawdziłem pierwsze przypadki dla a<50, niestety nie jestem informatykiem a programy typu exel czy zwykłe kalkulatory na niewiele tu się zdają. Żeby sprawdzić większą ilość przypadków potrzeba naprawdę dokładnych obliczeń na dużych liczbach.
Oczywiście wcześniej próbowałem również na wszelkie sposoby rozstrzygnąć problem za pomocą metod stricte matematycznych, ale okazuje się, że jest to zadanie gargantuicznie trudne, szczególne w stosunku do niepozornego sformułowania i pewnego intuicyjnie narzucającego się przekonania, iż poszukiwanych przypadków chyba nie ma i hipotetyczny program nigdy się nie zatrzymuje. W końcu przedziały pomiędzy kolejnymi liczbami są coraz mniejsze i dążą do 0. Jednak właśnie z uwagi na trudność matematycznego dowodu, że takich przypadków nie ma coś mi mówi aby sprawdzić większą część liczb, a może rozwiązanie się znajdze.
Być może ktoś z Was bedzie w stanie przesunąć tą skromną granicę a=50, albo znaleźć kontrprzykład i rostrzygnąć problem?