Zbiory dwa
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ę.
Komentarze
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;3;5;7;89;641 suma 747
2;3;5;7;641;809 suma 1467
2)
2+5+7+61+83+409=567
2+3+5+67+89+401=567
2,47,59,61,83
2,67,59,41,83
suma 252
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.
@ 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…
🙂
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}
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
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
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.
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.
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.
Jeszcze jedno rozwiązanie dla cyfr od 1 do 9: 2, 5, 7, 43, 61, 89. Suma niezmiennie 207.
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
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
5,47,29,61,83=225
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)
2, 5, 43, 7, 61, 809=927
i pas
2,3,5,41,67,89 207;
2,5,7,61,83,409 567; lub
2,3,5,67,89,401 567.
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.
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
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