szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 cze 2016, o 16:13 
Użytkownik

Posty: 13
Lokalizacja: Pcim
Jeśli sformułowanie poniższego problemu wyda się Państwu infantylne - przepraszam , ale nie jestem matematykiem z zawodu .

Dany jest skończony podzbiór zbioru liczb naturalnych A=\{1,2,3,...n\} . Dokonujemy eliminacji co drugiego elementu zbioru - czyli w pierwszej iteracji liczb 2,4,6... tzn liczb parzystych . W kolejnym przebiegu znowu wykreślamy co drugą liczbę (z tych co pozostały) tzn. jeśli zbiór A był zakończony liczbą parzystą - eliminowane będą 3,7,11,..., jeśli zakończony był nieparzystą liczbą eliminowane będą 1,5,9,... zawsze zgodnie z zasadą , że po wyeliminowanej liczbie na tym etapie musi pozostać dokładnie jedna liczba . Postępujemy tak do końca - czyli aż zostanie ostatnia liczba.

Powstaje pytanie czy istnieje formuła , zgodnie z którą można znając n przewidzieć , która liczba pozostanie . Hipoteza o której wspomniałem w tytule , mówi ,że należy przedstawić liczbę n w postaci binarnej , następnie dokonać przesunięcia najbardziej znaczącego bitu na miejsce najmniej znaczące - a otrzymana wartość da nam numer ostatniej pozostałej liczby . Czyli np. jeśli weźmiemy po uwagę zbiór o 57-miu elementach - reprezentacja binarna 57 = 111001_2. Przesuwamy jedynkę z początku na koniec 110011_2=51.

Wydaje mi się , że ten problem jest rozstrzygnięty , ale przeszukując internet nie udało mi się znaleźć rozwiązania .
Góra
Mężczyzna Offline
PostNapisane: 23 cze 2016, o 16:34 
Użytkownik

Posty: 15237
Lokalizacja: Bydgoszcz
Jeśli wykreślasz co drugą, to na końcu zawsze zostanie jedynka. Chyba, że inaczej opisałeś proces, a inaczej o nim myślisz (nie widzę przypadku, w którym druga iteracja zaczynała by się od trójki ):

1,2,3,4,5,6,7
1,3,5,7
1,5
1

1,2,3,4,5,6,7,8
1,3,5,7
1,5
1
Góra
Mężczyzna Offline
PostNapisane: 23 cze 2016, o 16:56 
Użytkownik

Posty: 13
Lokalizacja: Pcim
Druga iteracja może zacząć się od trójki , ze względu na "przeniesienie wolnego ostatniego elementu "z pierwszej iteracji .

Czyli dla 7-miu
1,2,3,4,5,6,7
1,3,5,7
3,7
7

A dla 8-miu tak jak u Ciebie .
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 Dany jest zbiór A={a,b,c,d}  Nanu  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl