Liczby Zosia: Spośród liczb naturalnych od 1 do 30 wybieramy 15. Na ile sposobów można wybrać te 15 liczb aby wśród nich żadna nie była dzielnikiem drugiej. Proszę o wyjaśnię nie sam wynik dziękuję

wredulus_pospolitus: W ramach jakiego działu masz takie głupie pytanie

Zosia: Kombinatoryka

wredulus_pospolitus: Moim zdaniem nie jest to zbyt dobre zadanie ... ponieważ na dobrą sprawę będzie się sprowadzać do (niemalże) metody − 'wypisz wszystkie możliwości i łudź się, że żadnej nie pominiesz'. Przedstawię Ci jak ja bym podszedł do tego zadania: 1. Wiemy, że zarówno '1' jak i '2' nie mogą być wybrane (1 jest dzielnikiem każdej liczby ... 2 z kolei wymusza wybranie 14 nieparzystych liczb w tym także 3 i 9) 2. jeden z 'oczywistych' możliwych wyborów to układ: 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 jako, że 16*2 > 30 ... to mamy pewność że nic tu nie jest niczyim dzielnikiem I określam ten wybór jako 'bazę' na której będę pracować. 3. Następnie można niektóre liczby połączyć w pary: 15 i 30 , 14 i 28, 13 i 26, 12 i 24, 11 i 22 <−−−− te liczby można 'podmienić' w bazie bez konieczności martwienia się, czy nie będą one dzielnikiem której z pozostałych liczb ... a to dlatego, że 11*3 = 33 > 30. To daje nam (na chwile obecną 2⁵ możliwości 4. Ale to nie wszystko, bo możemy także dokonać 'takiej zmiany w bazie' −> 10 zamienić z 20 i 15 z 30 (ten i jest istotny ... ponieważ 10 dzieli 30). To samo tyczy się 8 z 16 i 12 z 24 To daje nam kolejne 2⁵ + 2³ możliwości I teraz powinno się zadać najważniejsze pytanie −−− czy to są wszystkie możliwości

Mila:

wredulus_pospolitus: Miluś ... Ty widzisz jakąś możliwość na inne podejście do tego zadania, tak aby użyć wzorów?

Mila: Tylko drugi punkt zrobiłam. Jeszcze pomyślę.

Mila: Próbowałam też wypisać liczby pierwsze bez 2 i dobierać do nich ( na piechotę)resztę liczb.

wredulus_pospolitus: I jak Ci poszło

ABC: Sierpiński w swojej teorii liczb ma zadanie związane z powyższym, cytuję : " Zad) Niech n będzie liczbą naturalną. Ile co najwyżej liczb może zawierać zbiór liczb naturalnych nie większych od 2n, z których żadna nie jest podzielna przez żadną inną? Rozwiązanie. W szukanym zbiorze nie może być dwóch liczb a > b mających ten sam największy dzielnik nieparzysty m, bowiem wtedy b | a. Rzeczywiście, jeśli dla pewnych r > s mamy a = 2^r · m > 2^s · m = b, czyli a/b = 2^r−s. Liczb nieparzystych nie większych niż 2n jest n, a zatem tyle elementów może mieć co najwyżej poszukiwany zbiór. I rzeczywiście, zbiór liczb postaci: {n + 1, . . . , 2n} ma szukaną własność" Z tym że on nie pisze że ten zbiór jest JEDYNYM mający taką własność.

www: 72