Gauss, czyli tam i z powrotem

Według legendy pod koniec XVIII wieku działa się następująca rzecz. Pewien nauczyciel kazał swoim uczniom dodać wszystkie liczby od 1 do 40, aby mieć przez dłuższą chwilę spokój. Wszyscy, z wyjątkiem jednego, wykonywali pracowicie kolejne dodawania i zazwyczaj popełniali błędy...

Tym wyjątkowym uczniem był Carl Friedrich Gauss, który rozumował następująco:

|---|---|---|---|---|---| |1--|2--|-3-|⋯--|39-|40-| |40 |39 |38 |⋯ |2 | 1 | 2(1+ 2+ ...+ 40) = 40 ⋅41 -------------------------

(lewą stronę równości otrzymujemy, sumując liczby w wierszach, a prawą - w kolumnach), więc $1+ 2+ ...+ 40 = 12⋅40 ⋅41 = 820.$ Podobne rozumowanie stosujemy w zadaniach 1-3. Idea jest taka, żeby parować składniki lub czynniki: najmniejszy z największym, drugi najmniejszy z drugim największym itd.

Powyższy trik można nieco uogólnić - przecież tabela może mieć więcej niż dwa wiersze, a parowanie najmniejszych z największymi też nie jest koniecznością.

Dla przykładu rozważmy ciąg liczbowy $(a1,a2,...,an)$ i niech $|Sk = a1 + a2 +...+ ak$ dla $k = 1,2,...,n.$ Wówczas

S + S + ...+ S = a + 2a + 3a + ...+na , 1 2 n n n−1 n−2 1

(1)

co można wykazać za pomocą poniższej tabelki, po lewej stronie. Ta tożsamość rozwiązuje zadania 4 i 5.

|--|---|----|---| |3-|--|--|--|--|--|--|--| |--|---|---| |a1|---|----|---| |--|--|--|--|--|--|--|--|--|--|---|---| |a1|a2-|----|---| |2-|--|--|--| |--|--|--| |--|---|---| | | | ⋱ | | -1----- ---- ---- ---- ----- ----- |a-|a--|...-|a--| |--|--|--|--|--|--|--|--|--|--|---|---| --1---2-------n-- ----1--2--3--4--5--6--7--8--9---10--11--

Podobne rozumowanie możemy stosować, zliczając wierszami i kolumnami pary liczb naturalnych spełniające określone warunki, gdyż każda taka para ma swoje miejsce w odpowiedniej tabeli.
Przykładowo policzmy wierszami i kolumnami pary $(a,b),$ dla których $b |p a,$ gdzie $p$ jest ustaloną liczbą pierwszą, zaś $a ∈{1,2,...,n}$ (w tabeli wyżej, po prawej: $n = 11$ i $p = 2$ ). Pozostawimy Czytelnikowi zauważenie, że doprowadza to nas do twierdzenia Legendre'a: liczba pierwsza $p$ występuje w rozkładzie liczby $n!$ na czynniki pierwsze z wykładnikiem

2 3 ⌊n/p ⌋+ ⌊n/p ⌋ +⌊n/p ⌋+ ...

Takie podejście jest skuteczne w zadaniach 6 i 7.