100 szafek Takie Tam: Na korytarzu znajduje się 100 szafek. Znudzony pan odźwierny postanowił otworzyć wszystkie szafki. Następnie co drugą zamknął. Kolejno, przełączył (otworzył jeśli była zamknięta albo zamknął jeśli była otwarta) co 3 z nich. Kontynuował to w sumie 100 razy w taki sposób, że w przejściu numer k przełączał każdą k−tą szafkę. Ile szafek było otwartych na końcu?

ala: to chyba wariat ?

Blee: szafka nr 1: została tylko otwarta szafka nr 2: została otwarta później zamknięta szafka nr 3: została otwarta i później zamknięta szafka nr 4: została otwarta, zamknięta i później otwarta szafka nr 5: została otwarta i później zamknięta szafka nr 6: została otwarta, zamknięta, otwarta i zamknięta każdą z liczba od 2 do 100 rozkładasz na czynniki i sprawdzasz ile ma dzielników. W zależności od ich liczby dana szafka będzie otwarta bądź zamknięta.

Blee: więc wszystkie szafki o numerach (symbole to liczby pierwsze): p są zamknięte p*q są zamknięte p²*q są zamknięte p*q*r są zamknięte co wyczerpuje możliwości

Blee: tfu, jeszcze: p²*q*r są zamknięte p³ są zamknięte p⁵ są zamknięte więc tak naprawdę −−− otwarte będą jedynie: nr 1 oraz o numerze p²*q² (czyli: 36, 64, 100), p² (4,9,16,25,49), p⁴ (16,81) całą reszta będzie zamknięta

Blee: dobra, jeszcze raz. Liczby nie większe od 100 mogą być postaci: p −−− zamknięta p² p³ −−− zamknięta p⁴ p⁵ −−− zamknięta p⁶ pq −−− zamknięta p²q −−− zamknięta p³q −−− zamknięta p⁴q −−− zamknięta p⁵q −−− zamknięta p²q² p³q² −−− zamknięta pqr −−− zamknięta p²qr −−− zamknięta co szybko wykazujesz z szybkiego liczenia liczby dzielników liczby n = p^aq^br^c liczba dzielników liczby n wynosi wtedy (a+1)*(b+1)*(c+1) jeżeli liczba dzielników jest liczbą parzystą to znaczy, że szafka jest zamknięta (bo parzystą razy ją 'dotykano' wliczając to pierwsze przejście otwierające wszystkie szafki).

Takie Tam: A ile będzie otwartych szafek dla n szafek?

Bleee: Wszystko zależy od n. Podałem Ci w jaki sposób dojść do odpowiedzi. W zależności od liczby n mogą dojść kolejne rozkłady (np. p²q²r). Nalezy zauważyć że otwarte będą tylko i wyłącznie te szafki których w rozkładzie WSZYSTKIE liczby pierwsze są podnoszone do parzystej potęgi (tylko wtedy liczba dzielnikow będzie nieparzysta).

Takie Tam: To będzie podłoga ze √n w takim razie.

Blee: Tak też będzie tylko trzeba to jeszcze wykazać (co akurat nie jest trudne