Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

15.02.2018
czwartek

Zbiory dwa

15 lutego 2018, czwartek,

Projekt Euler https://projecteuler.net/ to znana strona z zadaniami dla programistów. Zaglądam na nią czasem raczej w poszukiwaniu inspiracji niż w celu rozwiązywania, bo programowanie od dawna nie jest moją mocną stroną, choć kiedyś było. Ostatnio wpadł mi w oko problem 118 – tym bardziej, że kiedyś sam coś podobnego wymyśliłem. Jego opis najwygodniej zacząć od przykładu, czyli zbioru liczb: {7,29,461,853}. Ten zbiór ma dwie istotne własności:
– jego elementami są tylko liczby pierwsze;
– wszystkie elementy składają się z dziewięciu cyfr, z których każda jest inna (od 1 do 9).
Eulerowskie zadanie polega na ustaleniu, ile jest zbiorów o takich własnościach. Programu nie pisałem, lecz skorzystałem z gotowca i ustaliłem, że odpowiedź brzmi 44680, czyli całkiem sporo.
Zadanie to można ograniczyć, a równocześnie rozszerzyć tak, że powstaną dwa zadania dla nieprogramistów.

1) jaki jest zbiór liczb o opisanych własnościach, których suma jest najmniejsza?
2) różni się od zadania (1) tylko tym, że różnych cyfr jest dziesięć – dochodzi zero.

Zadania nie są trudne, ale trochę liczenia i główkowania wymagają.

Na marginesie: gdyby w zadaniu (1) chodziło o największą sumę, to zdaniem komputera rozwiązaniem byłby zbiór dwuelementowy {2, 98765431}. Zdaniem komputera, bo sprawdzania na piechotę czy 8-cyfrowa liczba jest pierwsza nikomu nie życzę.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 22

Dodaj komentarz »
  1. Proponuję:
    1) 2+3+5+41+67+89=207
    2) 2+41+67+89+503=702
    Da się niżej? Podpowie mi Pan? Żebym wiedziała, czy dłużej nad tym posiedzieć, bo to tak na chybcika znalazłam 🙂

    Da się drugie.
    mp

  2. 2;3;5;7;89;641 suma 747
    2;3;5;7;641;809 suma 1467

  3. 2)
    2+5+7+61+83+409=567
    2+3+5+67+89+401=567

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. 2,47,59,61,83
    2,67,59,41,83
    suma 252

  6. Na początek bez zera:
    Kombinowałem, że trzeba dać liczby góra dwucyfrowe i z nieparzystymi na cyfrach jedności oraz parzystymi dziesiątek, przy czym 5 nie do pary zostaje jako singiel. Wymyśliłem 5, 29, 41, 67, 83, suma 225. Potem zauważyłem, że można zamienić, tak by było 23 i 89. No ale jak 23, to lepiej 2 i 3: 2, 3, 5, 41, 67, 89, suma 207. Można zamienić na 47 i 61, tak więc mamy dwa rozwiązania. Twierdzę, że mniej się nie da, bo 4, 6 i 8 muszą być tak czy owak co najmniej na pozycji dziesiątek. A wszystkie pozostałe cyfry mamy na pozycji jedności, c.n.d.

  7. @ timon & wiąz

    No pięknie się wyścig rozwija – aż kusi żeby się zadopingować komputerem i też powalczyć, ale tzw. wrodzona uczciwość nie pozwala…
    🙂

  8. 1) Są 3 zbiory realizujące minimalną sumę, która wynosi 207 (o ile nie pomyliłem się w rachunkach…):
    – {2, 3, 5, 41, 67, 89}
    – {2, 3, 5, 47, 61, 89}
    – {2, 5, 7, 43, 61, 89}

    2) Minimalna suma to 567, realizowana przez 2 zbiory:
    – {2, 3, 5, 67, 89, 401}
    – {2, 5, 7, 61, 83, 409}

  9. 2;3;5;41;67;89
    2;5;7;43;61;89
    Suma 207
    2,5,89,103,467
    Suma 666 – Liczba Bestii
    Zestawy znalezione bez użycia komputera

  10. Zadanie 1 ma 3 rozwiązania o sumie 207
    2,3,5,47,61,89
    2,5,7,43,61,89
    2,3,5,41,67,89

    Zadanie 2 ma 2 rozwiązania o sumie 567
    2,3,5,67,89,401
    2,5,7,61,83,409

  11. Jak jest 0, to w najlepszym przypadku musi być drugą cyfrą liczby 3-cyfrowej. Na przykład 10n, gdzie n – cyfra nieparzysta. Wszystkie cyfry można by zagospodarować tak: jedna liczba 3-cyfrowa, ile się da 1-cyfrowych, i reszta 2-cyfrowe. Ale liczba 10n zabiera za dużo cyfr nieparzystych, przy układaniu kolejnych jest kłopot z 5, nie da się. Z kolei 20n nie może być, bo nie ma takiej liczby pierwszej. 30n ten sam problem co 10n. Dochodzimy do 401 i robi się samograj: 401, 2, 3, 5, 67, 89. Nie można cyfr jedności zamieniać, więc jedno rozwiązanie, suma 567. Z ewentualnych wariantów typu 10n plus 2pq też nic nie da złożyć (kłopot z 5), więc rozwiązanie będzie jak wyżej.

  12. A jednak można pozamieniać cyfry jedności, tylko w sposób bardziej wyrafinowany: 409, 2, 5, 7, 61, 83. Suma oczywiście dalej 567.

  13. 1) Na razie Zad 1). Najwcześniej cyfry parzyste dodatnie występują w liczbach pierwszych na pozycji dziesiątek, są to w kolejności:
    4: 41; 43; 47
    6: 61; 67
    8: 83; 89
    A chcemy „dokupić” te cyfry jak najtaniej. Dostaniemy przy okazji także trzy spośród cyfr 1; 3; 7; 9 na pozycji jedności, tylko trzeba je różnicować by się nie powtarzały, np.
    47; 61; 89 lub 41; 67; 89 lub 43; 61; 89 (9 trzeba brać przy okazji bo tak taniej).

    Pozostaje dorzucić brakujące cyfry, ale to już taniocha bo one same są pierwszakami: 2;3;5 lub 2;5;7.

    Dlatego wydaje się, że minimalna cena tj. suma liczb w zadaniu 1) to:
    207 = 2+3+5+47+61+89 = 2+3+5+41+67+89 = 2+5+7+43+61+89.

  14. Jeszcze jedno rozwiązanie dla cyfr od 1 do 9: 2, 5, 7, 43, 61, 89. Suma niezmiennie 207.

  15. 2) Cyfry 0 nie da się kupić tanio bo pojawia się najpierw w liczbach: 103; 107; 109 (pomijam liczby o zdublowanych cyfrach).
    Wraz z nimi dostajemy chcąc nie chcąc cyfrę 1 oraz jedną z: 3; 7; 9; czyli dwie z czterech cyfr nieparzystych towarzyszących kłopotliwym cyfrom 4; 6; 8 (zad1). Musimy więc zrezygnować z taniości aby uniknąć powtórzeń cyfr nieparzystych.
    Wniosek: trzeba szukać pierwszego wystąpienia kłopotliwych cyfr 0;4;6;8 we własnym towarzystwie (wystąpień z cyframi 2 i 5 nie znajdziemy, bo to byłyby liczby złożone).
    Pierwsze takie wystąpienia są w liczbach 401 i 409. Pozostaje dobrać wystąpienia 6 i 8 bez dublowania cyfr i dołączyć pozostały drobiazg.

    Jak się wydaje, minimalna cena tj.suma liczb w zadaniu 2 to:
    567 = 2+3+5+67+89+401 = 2+5+7+61+83+409

  16. Na dopingu komputerowym:

    1+2+5+43+67+89=207
    i trochę więcej innych z tą samą sumą na przykład:
    2+5+7+43+61+89=207

    zbiór z zerem (chyba tylko dwie możliwości):
    5+29+67+83+401=585
    5+23+67+89+401=585

    Wbrew zapowiedziom Gospodarza wydaje mi się, że zadania są jednak trudne dla zawodników z kategorii kartka + ołówek.

    Program który napisałem ma cechy romantyczne, więc teraz ta odwieczna niepewność, czy komentarz będzie ujawniony 😉

    Ujawniłbym wcześniej tylko rozwiązanie z zerem.
    mp

  17. 5,47,29,61,83=225

  18. Z zerem znalazło się też:

    2+3+5+67+89+401=567
    2+5+7+61+83+409=567
    (być może więcej układów dla tej sumy, ale to z pewnością ustalą programy nieromantyczne)

  19. 2, 5, 43, 7, 61, 809=927
    i pas

  20. 2,3,5,41,67,89 207;
    2,5,7,61,83,409 567; lub
    2,3,5,67,89,401 567.

  21. 2,3,5,41,67,89= 207;
    2,5,7,61,83,409=567; lub
    2,3,5,67,89,401= 567.
    Tak jest bardziej czytelnie.

  22. Zad 1: 2, 3, 5, 47, 89, 61, co daje sumę 207
    Mniej się nie da, bo 4, 6 i 8 nie mogą być cyframi jedności i muszą być co najmniej dziesiątkami

  23. Zad 2: 2, 3, 5, 67, 89, 401, co daje sumę 567
    żeby upchnąć 0 musi być co najmniej jedna liczba trzycyfrowa.
    Zaczynamy od 10a, gdzie a jest cyfrą jedności trzycyfrowej liczby, 4, 6 i 8 muszą być na miejscu dziesiątek co daje nam 4b, 6c i 8d. Żadną z cyfr a, b, c, d nie może być 2 ani 5 czyli brakuje nam cyfr (zostało 3, 7, 9) -> sprzeczność
    Teraz bierzemy na warsztat 20a, 4b, 6c, 8d. Cyfry a, b, c, d muszą być ze zbioru {1,3,7,9}, 5 jest oddzielną liczbą pierwszą. Żadna z liczb 201, 203, 207, 209 nie jest liczbą pierwszą -> sprzeczność
    Teraz bierzemy 40a, 6b, 8c. Cyfry a, b, c muszą być ze zbioru {1,3,7,9], 2 i 5 są oddzielnymi liczbami pierwszymi. Łatwo znajdziemy rozwiązanie:
    401, 67, 89, 2, 3, 5.
    Jest to jedyne rozwiązanie bo żadna z liczb 403, 407, 409, 63, 69 nie jest liczbą pierwszą

    409 jest.
    mp

css.php