Czwórkami
W tym wpisie mowa jest wyłącznie o liczbach całkowitych dodatnich.
Każdą liczbę większą od 3 można przedstawić w postaci dodawania czterech liczb.
Każdą liczbę większą od 9 można przedstawić w postaci dodawania czterech różnych liczb.
Każdą liczbę większą od 17 można przedstawić w postaci dwóch dodawań czterech liczb, w których wszystkie osiem liczb (składników) jest różnych.
Każdą liczbę X>25 można przedstawić w postaci S>2 dodawań czterech liczb złożonych z 4S różnych składników.
Oznaczmy przez SX największą liczbę dodawań czterech liczb złożonych z 4SX różnych składników – takich, że suma każdego z tych dodawań równa jest X.
Na przykład, jeśli X=28, to SX=3, a tercet dodawań może wyglądać tak:
28=1+6+7+14=2+5+9+12=3+4+10+11
lub nieco inaczej:
28=1+7+8+12=2+5+10+11=3+4+6+15.
X=11 jest najmniejszą liczbą, dla której SX równe jest iloczynowi cyfr liczby X, bo 11 może być wynikiem dodawania tylko jednego (w dodatku jedynego) kwartetu różnych liczb: 1+2+3+5.
Jaka jest najmniejsza 3-cyfrowa liczba o takiej samej własności?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
A imię jego 114.
Chyba za bardzo się pośpieszyłem, bo 114 można przedstawić także w postaci 5 dodawań, a to sporo zmienia 😉 .
Do dwóch razy sztuka: 514
173
125 da się pokazać jako sumę 4 liczb w 10 wariantach:
1+2+3+119; 4+5+6+110; 7+8+9+101; …; 28+29+30+38.
@Apartado
Liczbę 114 można przedstawić jako sumę 4 liczb w 9 wariantach.
Będę strzelał: 125.
Ponieważ nie widzę ujawnionego mojego rozwiązania 173, więc uznając je za poprawne 🙂 pokażę, jak je znalazłem:
Wydaje się, że optymalne jest rozpoczęcie od wartości składników zbliżonych do X/4. Np. dla 28 to będzie liczba 7: (5+6+8+9)/4=7. Na dwóch pierwszych pozycjach poprzedzając 5+6 zmieszczą się jeszcze 3+4 oraz 1+2. Ostatecznie otrzymamy Sx=3:
1+2+9+16 = 28
3+4+8+13 = 28
5+6+7+10 = 28
Rozwijając ten schemat można zauważyć, że Sx zwiększa się o 1 kiedy dodajemy wiersz z dwoma następującymi składnikami:
Sx=1, X/4=2,5
1+2+3+4=10
Sx=2, X/4=4,5
1+2+7+8=18
3+4+5+6=18
Sx=3, X/4=6,5
1+2+11+12=26
3+4+9+10=26
5+6+7+8=26
itd…
W ostatnim wierszu mamy wtedy liczby:
(2 Sx-1)+(2 Sx)+(2 Sx+1)+(2 Sx+2)=8 Sx+2=X.
Stąd możemy obliczyć dla których X powiększa się Sx:
Teraz tylko należy rozłożyć Sx na czynniki pierwsze i sprawdzić, dla którego X jego cyfry zgadzają się z tym rozkładem:
rozkład Sx X X+1 X+2 X+3 X+4 X+5 X+6 X+7 13 106 107 108 109 110 111 112 113 2, 7 14 114 115 116 117 118 119 120 121 3, 5 15 122 123 124 125 126 127 128 129 2, 4, 8 16 130 131 132 133 134 135 136 137 17 138 139 140 141 142 143 144 145 2, 3, 3 18 146 147 148 149 150 151 152 153 19 154 155 156 157 158 159 160 161 2, 2, 5 20 162 163 164 165 166 167 168 169 3, 7 21 170 171 172 173 174 175 176 177 2, 11 22 178 179 180 181 182 183 184 185Odnalezienie rozwiązania nie jest ani trudne, ani żmudne, gdyż np. dla Sx=15 w liczbie X musiałoby wystąpić 3 i 5. Tymczasem widzimy, że w wierszu tym liczby X nie zawierają trójki. Z kolei dla Sx=16 wszystkie liczby zawierają cyfrę 3, a nie powinny, itd… W ten sposób dochodzimy do liczby 173 leżącej w wierszu Sx=21, które rozkłada się na 3 i 7. Bingo.
Najmniejsza liczba czterocyfrowa o zadanych właściwościach to 1299.
Oj, chyba nie…
mp
Nie wycelowałem dość starannie, poprawka: 135.
Czwórek jest 16
mp
@mp Oj, chyba nie…
Hmm, nadal nie widzę innej możliwości (1299). Oświeci mnie Pan?
Już oświeciłem… się. Ma Pan rację.
mp
Podejrzewam, że to 173 (21 czwórek).
Mam też przekonanie graniczące z pewnością, że nie ma takiej liczby 4 cyfrowej (bo nie da się zrobić iloczynu dającego ponad 124 z czterech cyfr – tyle par jest dla 1000)
@OlaGM liczbę 114 można przedstawić w postaci 14 czwórek 🙂
Oczywiście pomyłka co do drugiego zdania… pomyślę jaka to mogłaby być liczba.
Słabo celuję.. to pewnie z powodu astygmatyzmu. Ale do trzech razy sztuka: 173.
Przynajmniej mam pewność co do oszacowania S(173) ≥ ∏(173) = 21. Mam też mocne przeświadczenie, że zachodzi równość.
Liczbę tę wytypowałem na podstawie hipotezy potwierdzonej przykładami, że S(X) = T(X), gdzie T(X) := Entier(X/8) + If(Mod(X/4)=0;-1). Liczba 173 jest pierwszą z liczb 3-cyfrowych spełniającą warunek T(X) = ∏(X).
Pierwszą liczbą 4-cyfrową X spełniająca warunek T(X) = ∏(X) jest X=1299. To mocna sugestia, że S(X) można wyrazić prostym wzorem T tj. część całkowita z dzielenia X przez 8 co w przypadku podzielności X przez 4 pomniejszamy o jeden. Ale jeszcze nie dowód.
Postawię hipotezę, że nie ma takiego przypadku równości funkcji S i iloczynu cyfr wśród liczb 5-cyfrowych, a najmniejsze z nich z różnicami ±1 to:
S(26875)=3359 2*6*8*7*5=3360
S(36884)=4609 3*6*8*8*4=4608
Hipoteza skorygowana brzmi:
S(X) można wyrazić prostym wzorem jako część całkowitą z dzielenia X przez 8, którą w przypadku podzielności X przez 8 należy pomniejszyć o jeden.
Błąd tej formuły stwierdziłem na przykładzie liczby 172 o tyle przyjemnej, że należy do liczb dla których można b. łatwo znaleźć zestaw rozkładów 4-składnikowych wspólnie różnowartościowych, w liczebności maksymalnej S. S(172)=21 a formuła poprzednio (wyjątek przy podzielności przez 4) dawała 20, stąd korekta.
Ad „Postawię hipotezę, że nie ma takiego przypadku…”
Poprawiłem wartość S(36884) = 4610, więcej o 2 od iloczynu.
Najmniejszą liczbę 5-cyfrową z iloczynem cyfr mniejszym o 1 od S typuję tak:
S(48397)=6049; 4*8*3*9*7=6048
Ponieważ nie tylko ja wkręciłem się w to zadanie, to poniżej wszystkie liczby. Jestem prawie pewny, że żadnej nie pominąłem. chyba…
Jakoś wciągnął mnie ten temat. Dla parzystych X można łatwo znaleźć maksymalny zestaw rozkładów 4 składnikowych, wspólnie różnowartościowych.
Należy zacząć od rozkładu „środkowego” X=a+b+c+d (dla porządku: a<b<c<d), w którym wszystkie składniki są możliwie bliskie X/4 oraz a i d są tej samej parzystości, przeciwnej niż b i c.
Następnie w kolejnych wierszach wyliczamy kolejne rozkłady pomniejszając o dwa składniki a i b oraz zwiększając o dwa składniki c i d. Oczywiście kończymy na ostatnim wierszu z liczbami dodatnimi. Stąd też pomysł na wzór (przybliżający!) wartość S(X), tj. w Excelu:
T(X) = ZAOKR.DÓŁ(X/8;0)+JEŻELI(MOD(X;8)=0;-1;)
Weźmy jako przykład X=184. T=22; 184/4 = 46;
Tablica wierszy rozkładów [p; n; n; p]:
44; 45; 47; 48;
42; 43; 49; 50;
40; 41; 51; 52;
38; 39; 53; 54;
36; 37; 55; 56;
. . . . . . . . . . .etc . . . . . . . . . . . . . .
Tablica różnic wierszy rozkładów:
−; −; −; −;
-2; -2; 2; 2;
-2; -2; 2; 2;
-2; -2; 2; 2;
-2; -2; 2; 2;
. . . . . . . . . . .etc . . . . . . . . . . . . .
Dostaniemy zestaw 22 odp. rozkładów tj. S(184) ≥22. Można znaleźć inne zestawy ale chyba nie liczniejsze, bo dobór składników jest optymalny (minimalne różnice). Wydaje się więc pewne, że procedura ta pozwala przy okazji wyliczyć S(X) dla X parzystych, np. S(184)=22.
Mnie zaintrygowało X nieparzyste, gdzie jest trudniej ale i tu rysują się wyraźne prawidłowości. Wspomagając się algorytmicznie stwierdziłem także w tym przypadku istnienie stałej Tablicy różnic wierszy, oto jej fragment:
w. 1) −; −; −; −;
w. 2) -2; -3; 2; 3;
w. 3) -2; -2; 1; 3;
w. 4) -2; -2; 3; 1;
w. 5) -2; -2; -1; 5;
w. 6) -2; -2; 5; -1;
w. 7) -2; -2; 1; 3;
w. 8) -2; -2; 3; 1;
w. 9) -2; -2; -5; 9;
w. 10) -2; -2; 9; -5;
w. 11) -2; -2; 1; 3;
w. 12) -2; -2; 3; 1;
w. 13) -2; -2; -1; 5;
w. 14) -2; -2; 5; -1;
w. 15) -2; -2; 1; 3;
w. 16) -2; -2; 3; 1;
w. 17) -2; -2; -13; 17;
w. 18) -2; -2; 17; -13;
w. 19) -2; -2; 1; 3;
w. 20) -2; -2; 3; 1;
w. 21) -2; -2; -1; 5;
w. 22) -2; -2; 5; -1;
w. 23) -2; -2; 5; -1;
w. 24) -2; -2; 1; 3;
w. 25) -2; -2; 3; 1;
Wiersz 2) jest jednorazowy. W pozostałych od w. 3) składniki a i b zawsze pomniejszamy o 2. Co do c i d to mamy stały powtarzalny blok 6 wierszy różnic (z liczb -1,1,3,5), po nim zmienny powtarzalny blok 2 wierszy różnic (pierwszy z -5 i 9; drugi z -13 i 17; kolejny z ???).
Przykładowo, korzystając z Tablicy różnic wierszy dla X=125, T(X)=15, dostaniemy zestaw 15 rozkładów z dodatnimi składnikami.
Dla X=185 dostaniemy tą metodą zestaw 22 rozkładów, jak mi się wydaje, optymalny. I tu mam niestety zagwozdkę, bo T(185) = 23. Tak to jest z prostymi liczbami naturalnymi – nic tu nie jest proste ani naturalne.
128
Ok., to rzutem na taśmę: 173, czyli 21 sum. Następne jest 227, potem 292 i to koniec wśród 3-cyfrowych. Wśród 4-cyrowych jest tylko jedna, 1299.
Zastanawia mnie brak rozwiązań czysto „siłowych”; mamy rozwiązania niemal wyłącznie analityczne.
@apartado
Były próby, oj, były. Jednak kurier nie zdążył na czas z dostarczeniem komputera kwantowego. Wichura go zatrzymała, czy coś…
Wydaje mi się, że nikt nie przedstawił takiego rozumowania jak moje, więc je dopiszę. Wychodzi od siłowego, o które tak jakby upomniał się Apartado.
Jeśli czwórek ma być dajmy na to 30, tworzymy kolumny cyfr:
1 | 31 | 90 | 120
2 | 32 | 89 | 119
…
29 | 59 | 62 | 92
30 | 60 | 61 | 91
Pierwsze dwie kolumny rosną z góry na dół, a ostatnie dwie rosną z dołu do góry. Wszystkie rzędy dają tę samą sumę: 1+31+90+120=242. To najmniejsza liczba, która daje 30 czwórek. Pierwszy rząd można algebraicznie zapisać:
1 + x + 1 + 3x + 4x = y
8x + 2 = y
x = (y-2)/8
x – liczba czwórek liczby y
(x zaokrąglone w dół, oczywiście)
Bardzo ładnie. Wzór końcowy w punkt!
mp
Jeśli natkniemy się na zadanie/test „wpisz kolejną, logicznie pasującą liczbę”…
11,21,31,41,…
… to teraz dzięki wzorowi OliGM (potwierdzenie dokonań xswedc) z łatwością i z niczym nie zmąconą pewnością siebie, wpisujemy 173.
Ponieważ rozważamy najważniejszy problem matematyki, to pozwolę sobie na jeszcze jeden komentarz.
Jak napisała OlaGM, wydaje się, że znalazła inne rozwiązanie niż moje. W przykładach ja wypełniałem dwie pierwsze kolumny wierszami:
a OlaGM kolumnami:
(pozostałe x łatwo się uzupełnia)
Jednak patrząc troszkę szerzej widać, że znaleziony przez OlaGM wzór jest identyczny z wyprowadzonym przeze mnie. To oznacza, że oba sposoby są równoważne i są wariantami tej samej metody. Takich wariantów może być więcej. Aby przykłady były małe, pokażę dla X=34:
wariant wg xswedc:
wariant wg OlaGM:
Ale innych wariantów można natrzaskać całkiem sporo, np:
lub:
itd…
Nasuwa się więc kluczowe dla świata pytanie: ile różnych wariantów można skonstruować dla danego X?
xswedc, OliGM, Markoniusz
Świetne rozwiązania, gratuluję! Czuję niedosyt, że nie udało mi się tego rozwiązać (a dużo myślałem o tym zadaniu na spacerach z psem – widocznie trzeba było wziąć kartkę do ręki zamiast smyczy).
Był nawet moment, kiedy chciałem się posłużyć komputerem i zacząłem zgłębiać algorytmy szukania sum podzbioru (deep-first search, Schroeppel and Shamir, etc) – totalnie ślepa uliczka i armata na muchę.
173=
1+21+70+81
2+28+63+80
3+45+54+71
4+43+47+79
5+33+36+99
6+26+58+83
7+29+37+100
8+42+56+67
9+31+55+78
10+40+57+66
11+48+53+61
12+41+44+76
13+39+59+62
14+22+68+69
15+20+65+73
16+18+64+75
17+19+30+107
23+38+52+60
24+25+50+74
27+46+49+51
32+34+35+72
Komentarz:
Warianty z sumami nieparzystymi są chyba bardziej zawikłane, niż te opisane(?).
Dla liczby 173 niekwantowy komputer proponuje takiego dzikusa jak powyżej(z lekka go posortowałem).
Jak widać mamy tu „luki”- nie wszystkie kolejne liczby są wykorzystane.
Takich układów jest dużo, co powoduje, że:
1. Dla badanej liczby łatwo jest znaleźć przynajmniej jeden z nich.
2. „Dość łatwo” jest stwierdzić że nie można „rozłożyć” badanej liczby na więcej sposobów niż iloczyn jej cyfr.
W przypadku 173 niekwantowy komputer nie potrafił znaleźć „rozkładu” na więcej niż 21 sposobów i uznał, że liczba 173 jest tą poszukiwaną.
@xswedc
To kluczowe dla świata pytanie jest bardzo interesujące. Też mnie nurtuje. Można da się znaleźć jakąś zależność.
@Apartado
Luki w wypadku 173 są obowiązkowe, bo 173 nie jest najmniejszą liczbą, która daje 21 czwórek (21*8 + 2 = 170 jest). Dla 170 luk by nie było, bo 170*21 = sumie liczb od 1 do 84, no i wtedy każda jest niezbędna.
@Xswedc
Szukałam jakiejś zależności, ale na razie nie mam pomysłu. Dla 18 i 19 są cztery pary czwórek, dla 20 jest trzynaście par czwórek, dla 21 – dwadzieścia dwie pary czwórek.