Przeskocz do treści

Delta mi!

Kącik początkującego olimpijczyka

Rachunki

Gauss, czyli tam i z powrotem

Bartłomiej Bzdęga

o artykule ...

  • Publikacja w Delcie: marzec 2020
  • Publikacja elektroniczna: 1 marca 2020
  • Wersja do druku [application/pdf]: (427 KB)

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...

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.