Wykreślanka
Jeszcze raz „tegorocznie”, ale bardzo krótko i chyba nietrudno.
Poniższe zadanie wypadło z artykułu o tzw. problemie rachmistrza, który przygotowałem do marcowego Świata nauki, ponieważ jest z tym problemem zbyt luźno związane, czyli tylko „współdziałaniem” dwóch działań, dodawania i mnożenia.
Z ciągu liczb naturalnych od 1 do 2016 wykreślono najmniej liczb tak, aby wśród pozostałych żadna nie była iloczynem dwóch innych. Jaka była suma wykreślonych liczb?
Komentarze
Jak rozumieć zdanie: „liczba nie jest iloczynem dwóch innych”?
Jeśli a=b*c, to czy może być:
a=b?
b=c?
a=c?
W ciągu liczb naturalnych od 1 do 2016 każda liczba jest inna.
mp
990
2+3+…+44=989
lub
2+3+…+43+45=990
Ja bym po pierwsze zostawił liczbę 1, bo ani ona nie będzie iloczynem dwóch innych liczb, ani czynnikiem, który dałby w wyniku liczbę inną niż drugi czynnik.
Dość oczywistym rozwiązaniem jest wyrzucić kolejne liczby aż do 44, bo 45×46 = 2070 i każdy inny iloczyn będzie jeszcze większy. 44 zostawić nie można, bo 44×45 = 1980. Można natomiast wyrzucić zamiast 44 – 45, a nawet zamiast 44 – 1980. Iloczyn 44×46 = 2024. Byłyby więc trzy rozwiązania, dające 43 liczby: od 2 do 44, od 2 do 43 i 45, od 2 do 43 i 1980. Nieco trudniej udowodnić, że to rozwiązania najlepsze. Jednak jeśli pozostawimy jakąś inną liczbę, np. 43, to 43×45 = 1935, a 43×46 = 1978 (a 43×44 jeszcze mniej). Zostawiając na naszej liście 43, musielibyśmy wyrzucić z niej co najmniej 2 inne liczby, a więc byłoby to posunięcie nieopłacalne, z każdą mniejszą liczbą oczywiście robiłoby się nieopłacalne jeszcze bardziej, w końcu gdyby naszła nas chęć pozostawienia 2, musielibyśmy na pewno z listy usunąć każdą inną liczbę parzystą >4 do 2016 lub wynik z jej podzielenia przez 2, a więc albo 6 albo 3, albo 8 albo 4, etc.
Suma liczb od 2 do 44 = 989, jak zamienimy 44 na 45, to mamy 990, a jak na 1980, to 2925.
Z ciągu wystarczy wykreślić 43 liczby: 2, 3, 4, …, 43, 44.
Wtedy iloczyn dwóch dowolnych liczb pozostawionych w ciągu jest albo postaci 1 * n = n (moje pytanie miało rozwiać wątpliwości, czy to jest możliwe), albo a * b, gdzie a,b >= 45, zatem wtedy a * b >= 2025.
Z drugiej strony musimy wykreślić minimum 43 liczby, bowiem dla każdego i = 1, 2, 3, …, 43, z trójki liczb (a, b, a*b) dla a=45-i, b=44+i, przynajmniej jedna musi zostać wykreślona, a wszystkie te liczby są różne i wszystkie należą do ciągu 1, 2, 3, …, 2016.
Suma wykreślonych liczb to 2 + 3 + 4 + … + 43 + 44 = 989
Proponuję 990, czyli sumę liczb od 1 do 44.
Wykreślenie liczb od 2 do 44 załatwia sprawę. Wydaje mi się, że pozostawienie którejkoelwiek z nich powoduje konieczność wykreślenia conajmniej jednej innej. Zatem 43 liczby to najmniejsza liczba wykreślonych liczb 🙂 Ich suma to 989.
Jeśli jednak zamiast 44 usuniemy 45, to też mamy 43 usunięte liczby i sumę usuniętych 890. Czyżby dwa rozwiązania?
Starczy wykreślić wszystkie liczby mniejsze od pierwiastka z 2016, który to wynosi około 44,9.
Czyli sumujemy liczby od 1 do 44, otrzymując 44*(44+1)/2 = 990
Jeżeli dobrze zrozumiałem warunki zadania, to wykreślono liczby od 2 do 44. Ich suma wynosi 989.
Pozostałe liczby tworzą zbiór Z={i: (2<=i<=2016) oraz (i jest iloczynem nieparzystej liczby czynników pierwszych z powtórzeniami)}. Przykład: 72=2^3*3^2 ma 5 czynników pierwszych więc należy do Z. Suma liczb wykreślonych jest równa 1010771.
„Wykreślanka”- tylko od której strony zacząć to wykreślanie?
mrugam teraz do Gospodarza 😉
Najlepiej po bożemu, czyli od… 😉
m
Dzięki apartado! Olśnilo mnie.
Pierwiastek z 2016 to ~44,9.
Czyli wystarczy wykreślić elementy od 1 do 44 i już żaden iloczyn dwóch z pozostałych liczb do 2016 nie ma szans zmieścić się w tym zbiorze.
A suma 1 do 44 to 990.
Zostają {45,46,…,2016}, wykreślamy {1,2,…,44}, 1+2+…+44=990. Siekiera wystarczyła tu w zupełności 🙂
Moje pierwsze, błędne rozwiązanie jest dobre dla zmodyfikowanej następująco treści zadania:
„Z ciągu liczb naturalnych {1,2,…….} wykreślono pewną ilość liczb tak, aby wśród pozostałych żadna nie była iloczynem dwóch innych. Podaj przykładową konstrukcję tego zbioru”
Można konstruować takie zbiory na wiele sposobów krok po kroku przyjmując, że pewne początkowe liczby należą do szukanego zbioru. Trudniej jednak jest podać konstrukcję Z tak, aby z góry można było stwierdzić, czy dana liczba należy do Z bez wyliczania wcześniejszych od niej elementów. Mnie się to przypadkiem udało ale ciekawe czy jest wiele innych tego typu konstrukcji Z ?
@budfy
Ja nawet uważam, że 3 rozwiązania, bo możemy zostawić i 44, i 45, a usunąć ich iloczyn – 1980.
Nie żebym krytykował, ale właściwie liczba 2016 nie odegrała w zadaniu jakiejś szczególnej roli 🙂