| |
© h.hofstede (h.hofstede@hogeland.nl)
|
|
|
Uitputting. |
| |
|
|
|
De bewijsmethode van
"uitputting" is zonder twijfel de saaiste van allemaal.
Kort samengevat:
|
| |
|
|
|
|
gewoon alle mogelijkheden proberen!
|
|
| |
|
|
|
Nou, meer kan ik er
niet over zeggen.
Hoogstens een voorbeeldje geven...Toon aan dat elk Pythagoreïsch
drietal een vijfvoud bevat.
Effe Checke:
3-4-5,
5-12-13,
7-24-25,
9-40-41,
Het lijkt inderdaad te kloppen.
Je kunt dat zien door de vergelijking a2 + b2
= c2 MODULO 5 te bekijken, en dan gewoon
alle gevallen langs te gaan (uitputting).
Nou is een kwadraat modulo 5 altijd gelijk aan 1 of 4.
(x2 mod 5) = (x mod 5) • (x
mod 5) en kijk maar naar alle mogelijkheden: (x mod
5 = 0 hoeft niet, want dan is x een vijfvoud en zijn we
al klaar)
|
| |
|
|
|
|
| x mod 5 |
x2 mod 5 |
| 0 |
hoeft niet |
| 1 |
1 • 1 = 1 mod 5 = 1 |
| 2 |
2 • 2 = 4 mod 5 = 4 |
| 3 |
3 • 3 = 9 mod 5 = 4 |
| 4 |
4 • 4 = 16 mod 5 = 1 |
|
|
| |
|
|
|
|
Laten we met die 1 en 4 maar wéér alle mogelijkheden
langsgaan:
|
| a2 mod 5 |
b2 mod 5 |
(a2 + b2)mod
5 |
| 1 |
1 |
2 |
| 1 |
4 |
0 |
| 4 |
1 |
0 |
| 4 |
4 |
3 |
|
In de laatste kolom staat echter géén 1 of 4, dus de
laatste kolom is geen kwadraat modulo 5, dus kan nooit gelijk
zijn aan c2.
q.e.d. |
| |
|
|
|
| Een van de beroemdste bewijzen
door uitputting is het bewijs van Appel en Haken voor het
vierkleurenprobleem. Meer daarover kun je hier lezen. |
| |
|
|
|
| |
|
|
|
|
OPGAVEN |
| |
|
|
|
| 1. |
Er zijn geen gehele getallen waarvoor geldt a2
+ b2 - 8c = 6
Toon dat aan door een willekeurig geheel getal te schrijven als 4n of 4n
+ 1 of 4n + 2 of 4n + 3 en bekijk de kwadraten
modulo 8. |
| |
|
|
|
| 2. |
(te danken aan
Paul Erdös).
Elk geheel getal kan op oneindig
veel manieren geschreven worden als ±12 ±
22 ± 32 ± ... ± k2
Dat ga je (hopelijk) in deze opgave aantonen. |
| |
|
|
|
| |
a. |
Laat
zien door te proberen dat het op minstens één manier kan
voor de getallen 0, 1, 2, 3. |
| |
|
|
|
| |
Het
getal 4 kun je schrijven als 4 = (k + 1)2 - (k + 2)2
- (k + 3)2 + (k + 4)2 |
| |
|
|
| |
b. |
Laat
zien dat dat zo is. |
| |
|
|
|
| |
c. |
Gebruik
deze eigenschap en vraag a) om te laten zien dat je
alle getallen op minstens één manier als
±12 ±
22 ± 32 ± ... ± k2
kunt schrijven |
| |
|
|
|
| |
d. |
Gebruik
het feit dat 4 - 4 = 0 om te laten zien dat je alle getallen
op oneindig veel manieren kunt schrijven als ±12 ±
22 ± 32 ± ... ± k2
|
| |
|
|
|
| 3. |
Stelling: n7 - n is
altijd deelbaar door 7
voorbeeldjes:
17 - 1 = 0 = 0 • 7
27 - 2 = 126 = 18 • 7
37 - 3 = 2184 = 312 • 7
47 - 4 = 16380 = 2340 • 7
enz. |
| |
|
|
|
| |
a. |
Toon
aan dat n7 - n = n(n - 1)(n2 + n + 1)(n
+ 1)(n2 - n + 1) |
| |
|
|
|
| |
Als je
n door 7 deelt dan kan de rest van die deling zes
waarden aannemen. |
| |
|
|
|
| |
b. |
Toon
voor elk van die zes waarden met het resultaat van a) aan
dat de stelling klopt. |
| |
|
|
|
| |
|
 |
|
| |
|
|
|
|
© h.hofstede (h.hofstede@hogeland.nl)
|