listopad 2024

Data ostatniej modyfikacji:
2024-12-10

Zad. 1. Czy można w taki sposób ponumerować wierzchołki 2024-kąta foremnego liczbami naturalnymi (niekoniecznie kolejnymi), by silnia każdej liczby naturalnej od 1 do 2024 (włącznie) wystąpiła jako iloczyn numerów pewnych dwóch sąsiednich wierzchołków?

Zad. 2. Ania wybiera liczbę całkowitą od 1 do 50, a Basia ma za zadanie ją odgadnąć. W tym celu Basia może wybrać dowolną liczbę całkowitą n i zadać Ani pytanie: „Czy twoja liczba jest mniejsza od n?″. Basia zadaje takie pytania aż do ustalenia tajemniczej liczby. Ile razy Basia musi zadać to pytanie, by mieć gwarancję odgadnięcia liczby Ani?

Zad. 3. Zasady gry z poprzedniego zadania zmieniły się i pytanie Basi teraz brzmi: „Czy twoja liczba jest podzielna przez n?″. Ile wynosi liczba takich pytań gwarantująca odgadnięcie liczby Ani?

 

Wyniki: 

W tym miesiącu za nadesłane rozwiązania punktów nie przyznano.

 

Odpowiedzi: 

Zad. 1. Takie numerowanie nie jest możliwe.

Załóżmy nie wprost, że takie numerowanie istnieje. Wówczas każda silnia od 1! do 2024! pojawia się dokładnie raz jako iloczyn numerów dwóch sąsiednich wierzchołków. To oznacza, że iloczyn wszystkich liczb przypisanych wierzchołkom musi być pierwiastkiem kwadratowym iloczynu wszystkich silni od 1! do 2024!. Dzieje się tak, ponieważ każda liczba przypisana do wierzchołka jest uwzględniana dokładnie dwa razy (przy dwóch sąsiadujących bokach). Jednak iloczyn wszystkich silni od 1! do 2024! nie jest kwadratem liczby całkowitej. Jest tak, ponieważ liczby pierwsze z przedziału (1012, 2024] występują w rozkładzie tego iloczynu dokładnie raz, a liczba będąca kwadratem musi mieć w rozkładzie na czynniki pierwsze wszystkie wykładniki parzyste. Otrzymujemy sprzeczność, co dowodzi, że takie numerowanie wierzchołków 2024-kąta foremnego jest niemożliwe. 

Zad. 2. Aby zminimalizować liczbę pozostałych liczb do sprawdzenia, należy wybierać n w środku przedziału niesprawdzonych liczb. Dzięki temu możliwy zakres zmniejsza się za każdym razem o połowę (zaokrąglając w górę). Przebieg tej strategii wygląda następująco: 50 → 25 → 13 → 7 → 4 → 2 → 1. W efekcie do ustalenia wybranej liczby potrzeba dokładnie sześciu pytań.

Zad. 3. Najpierw pokażemy, że minimalna liczba pytań wynosi co najmniej 15. Istnieje 15 liczb pierwszych mniejszych od 50. Gdyby Basia zadała 14 pytań, a Ania za każdym razem odpowiedziała „nie”, nie moglibyśmy stwierdzić, czy wybraną liczbą jest liczba pierwsza, o którą Basia jeszcze nie zapytała, czy jedynka. Dlatego 14 pytań nie wystarcza.

Teraz przedstawimy strategię pozwalającą ustalić szukaną liczbę przy użyciu 15 pytań: Basia najpierw pyta o podzielność przez 2, 3, 5 i 7.

  • Jeśli Ania na wszystkie te pytania odpowie „nie”, oznacza to, że szukana liczba nie jest liczbą złożoną (dlaczego?). W takim przypadku pozostaje 11 liczb pierwszych oraz jedynka, co daje łącznie 12 możliwości. Na ich sprawdzenie wystarczy 11 dodatkowych pytań.
  • Jeśli Ania odpowie „tak” tylko na pytanie o 2, wśród możliwych liczb zostaje dokładnie 11 (potęgi liczby 2 i ich kombinacje z pozostałymi pierwszymi mniejszymi od 50). Wystarczy 10 pytań, by je wyeliminować.
  • Jeśli Ania odpowie „tak” tylko na pytanie o 3, pozostaje 5 liczb (potęgi liczby 3 i ich wielokrotności z zakresu do 50), co wymaga maksymalnie 4 pytań.
  • Jeśli Ania odpowie „tak” w innej konfiguracji, szukana liczba musi być wielokrotnością iloczynu potwierdzonych liczb pierwszych. Iloczyn ten wynosi co najmniej 5, co oznacza, że szukana liczba ma co najwyżej 10 możliwych wartości. Na ich sprawdzenie wystarczy pozostała liczba pytań.

Z powyższego wynika, że 15 pytań zawsze wystarcza do jednoznacznego ustalenia wybranej liczby.

 

Powrót na górę strony