omj 2017/2018 świruś: 3. Niech n będzie dodatnią liczbą całkowitą. Każdą z liczb 1,2,3,...,1000 pomalowano jednym z n kolorów. Okazało się, że każde dwie liczby, z których jedna jest dzielnikiem drugiej są pomalowane różnymi kolorami. Wyznacz najmniejszą liczbę n, dla której taka sytuacja jest możliwa.

wredulus_pospolitus: okey ... jaki miałaś pomysł

świruś: no że od początku 1−musi mieć swój kolor (np. kolor nr 1) 2−musi mieć swój kolor nr 2 3− musi mieć swój kolor nr 2 4− musi mieć kolor nr 3 5− musi mieć swój kolor nr 2 6− musi mieć swój kolor nr 3 itd... nwm czy widać o co mi chodzi

świruś: 2,4 muszą mieć różne 4,8 muszą mieć różne itd.. potęgi 2 muszą mieć różne kolory

wredulus_pospolitus: okey ... idziesz w dobrym kierunku ... powedzmy że liczby które mają ten sam kolor należą do tej samej grupy ... jak by wyglądały liczby w każdej z tych grup? Co łączyłoby liczby będące w tej samej grupie

świruś: liczby w tej samej grupie łączyłoby to, że żadna nie dzieli się przez rzadną

świruś: np. liczby pierwsze

świruś: np. liczba jeden, która miałaby osobny kolor

świruś: właśnie niezbyt mam pomysł na to bo sporo tych liczb no aż 1000

wredulus_pospolitus: okey ... a spotkałaś się z taki zapisem liczby: dowolną liczbę naturalną można zapisać w postaci: n = 2^a*3^b*5^c*7^d*11^e*13^f*.... (masz tu kolejne liczby pierwsze podnoszone do potęgi) gdzie a,b,c,d,e,f,... ∊ {0,1,2,3,....}

wredulus_pospolitus: Podstawowe pytanie (także na przyszłość) −−− wolisz w taki sposób 'pomocy', wolisz jeżeli jasno podam Ci moją propozycję rozwiązania, czy też wolisz gotowca ? Osobiście uznałem że wolisz właśnie taki sposób, ale mogę się mylić, dlatego się pytam.

świruś: Zauważyłam, że dość dobrze zapamiętuję rozwiązania innych (gotowe).Ale ten drugi sposób też jest bardzo dobry, bo można przy tym nauczyć się wielu nowych wzorów, sposobów itd.. Może umówmy się, że jak będę potrzebowała gotowca to zaznaczę to w poście

świruś: a z tym zapisem się nie spotkałam

świruś: przynajmniej nie kojarzę nic takiego

świruś: ale jeśli n=0 to... nie da się chybaa

wredulus_pospolitus: masz rację −−− mała poprawka −−− naturalne dodatnie

wredulus_pospolitus: Dobra ... to może w ten sposób podejdę −−− to jest moja propozycja 'powrzucania' liczb do kolejnych grup. Postaraj się odpowiedzieć "dlaczego", "co je łączy" i spróbuj je zapisać w takiej postaci jak podałem wyżej −−− to może pomóc Ci w zauważeniu powiązania. I w końcu −−− podaj jakie liczby by były w miejscu znaku zapytania.

świruś: 32, 243, 5⁵ jest za duże 48, 80, 120 itd...

wredulus_pospolitus: pytanie −−− czy widzisz 'co je łączy'

świruś: można je zapisać używając 2,3,5 do jakiejś potęgi

świruś: pierwsze trzy liczby to 2, 3 i 5 podnoszone do potęgi np. 2³=8 3³=27 5³=125 itd... z kolejnymi grupami większa potęga kolejne to podwojenia liczb z poprzednich grup

świruś: można jeszcze tak np. 2²=4 2⁰*3²=9 2⁰*3⁰*5²=25 2¹*3¹=6 jakby suma wykładników w trzeciej grupie to zawsze 2 w czwartej grupie to zawsze 3 itd....

www: https://omj.edu.pl/uploads/attachments/3etap18r.pdf

świruś: www widziałam to już wcześniej, ale też chciałam spróbować, żeby ktoś mi pomógł

wredulus_pospolitus: "jakby suma wykładników w trzeciej grupie to zawsze 2" <−−− to jest to co chciałem żebyś zauważyła W każdej grupie −−− suma potęg będzie taka sama i równa "Numer grupy − 1" Możemy też zauważyć, że w każdej grupie najmniejszą liczbą w tejże grupie będzie liczba 2ⁿ. A to wynika z tego że każda liczba w grupie składa się z iloczynu 'n' liczb pierwszych, a najmniejszą liczbą pierwszą jest 2 ... stąd 2ⁿ będzie najmniejszą liczbą Już rozumiesz do czego zmierzam?

świruś: że tych grup będzie 9? bo największe to 2⁹=512

świruś: nie wiem czy o to chodziło?

świruś: jutro konkurs kuratora:(

wredulus_pospolitus: 9 +1 = 10 oto mi chodziło

świruś: okii to super

świruś: wyszło tak samo jak w tym rozwiązaniu co przysłał www

świruś: tym z omj

świruś: dziękuję bardzo

świruś: jeszcze jedno pytanie, skąd wiemy, że to najmniejsza możliwa liczba grup w tym zadaniu? może da się utworzyć mniej?

wredulus_pospolitus: świrusku ... zauważ co łączy wszystkie liczby w danej grupie i jaka jest różnica pomiędzy grupami. Rozkładając wszystkie liczby na czynniki pierwsze mamy je podzielone w ten sposób, że każda liczba mająca w swoim rozkładzie DOKŁADNIE 'n' liczb pierwszych znajduje się w grupie 'n+1' i znajduje się z wszystkimi innymi liczbami mającymi dokładnie 'n' liczb pierwszych w swoim rozkładzie. W ten sposób mamy PEWNOŚĆ, że nie zdarzy się taka sytuacja, że w tej samej grupie znajdą się dwie takie liczby, że jedna z nich dzieli drugą (bo przecież to jest możliwe tylko jeżeli przy rozkładzie na czynniki pierwsze mają one RÓŻNĄ ilość liczb pierwszych). Dodatkowo wybierając losowo jakąś liczbę z grupy 'n+1', wiemy że jeżeli z jej rozkładu "wymażemy" dowolną liczbę pierwszą to otrzymamy liczbę którą mamy w grupie 'n', wymazując dwie liczby pierwsze z rozkładu otrzymamy liczbę z grupy 'n−1', itd.. W efekcie −−− możemy pokazać, że (dla dowolnego 'n') każda liczba z grupy 'n+1' ma swojego dzielnika w każdej z grup od '1' do 'n'. To daje nam pewność, że nie możemy 'uciąć' ani jednej grupy. Zauważ, że oni w swoim rozwiązaniu podeszli w ten sposób: zobaczmy jaka najwyższa potęga 2 mieści się w przedziale od 1 do 1'000. Jest to 2⁹. Ile dzielników ma liczb 2⁹? 10. (potęga zmienia się od 0 do 9) Więc mamy CONAJMNIEJ 10 grup. I później dopiero wykazali, że nie będzie ich więcej niż 10. Więc samo wykazanie, że grup jest CONAJMNIEJ 10, nie jest tak trudne. Jedna uwaga −−− w ich uwadze podali sposób kolorowania który ja Ci prezentowałem.