Zoek de fout

Examenroosters, algemene discussies, ...

Moderator: Praesidium

User avatar
Robbe
WOZ
Posts: 2161
Contact:

Zoek de fout

Post#1 » Sat May 19, 2007 10:52 am

Ik opende mijn terminal nog eens en ik kreeg dit bewijs voorgeschoteld door fortune:
  • Theorem: All positive integers are equal.
  • Proof:
    Sufficient to show that for any two positive integers, A and B, A = B. Further, it is sufficient to show that for all N > 0, if A and B (positive integers) satisfy (MAX(A, B) = N) then A = B.

    Proceed by induction: If N = 1, then A and B, being positive integers, must both be 1. So A = B.

    Assume that the theorem is true for some value k. Take A and B with MAX(A, B) = k+1. Then MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1). Consequently, A = B.
"I'm not afraid of falling, I'm afraid of landing" -- Sam
How To Ask Questions The Smart Way

Zingen? UKA-n dat ook!

User avatar
Foundation
Posts: 622

Re: Zoek de fout

Post#2 » Sat May 19, 2007 4:41 pm

Robbe wrote:... MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1).
Deze gevolgtrekking klopt niet. Kan enkel als MAX gedefinieerd zou zijn als EQUAL. Maar dan zoudt ge aan het bewijzen zijn dat elk getal gelijk is aan zichzelf.

Of zoiets...

User avatar
Dave
WOZ
Posts: 816

Post#3 » Sat May 19, 2007 8:08 pm

is idd een nogal foutieve gevolgtrekking, nice try though :D

joeri
Posts: 41

Re: Zoek de fout

Post#4 » Sun May 20, 2007 1:07 am

Foundation wrote:
Robbe wrote:... MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1).
Deze gevolgtrekking klopt niet. Kan enkel als MAX gedefinieerd zou zijn als EQUAL. Maar dan zoudt ge aan het bewijzen zijn dat elk getal gelijk is aan zichzelf.

Of zoiets...
Het zit iets subtieler in elkaar, we hadden namelijk voor k al bewezen dat als MAX(A, B) = k dat A = B.
Nu zeggen we:
MAX(A, B) = k + 1 <=> MAX(A-1, B-1) = k => A-1 = B-1
(Want MAX(A, B)-1 = MAX(A-1, B-1) )

Maar het is natuurlijk niet omdat A en B positieve getallen zijn dat A-1 en B-1 positieve getallen zijn, dat is de eerste reden dat het misgaat. De andere (verwante) reden is makkelijk te illustreren:
MAX(3, 5) = 5
MAX(2, 4) = 4
MAX(1, 3) = 3
MAX(0, 2) = 2
MAX(-1, 1) = 1
Kortom, het basisgeval MAX(1, 1) = 1 wordt nooit bereikt.

User avatar
Robbe
WOZ
Posts: 2161
Contact:

Post#5 » Sun May 20, 2007 1:32 pm

Ik was eerder aan het denken aan een foutief gebruik van inductie. Er is namelijk een basisgeval te weinig: N=2.
"I'm not afraid of falling, I'm afraid of landing" -- Sam
How To Ask Questions The Smart Way

Zingen? UKA-n dat ook!

joeri
Posts: 41

Post#6 » Sun May 20, 2007 2:37 pm

Robbe wrote:Ik was eerder aan het denken aan een foutief gebruik van inductie. Er is namelijk een basisgeval te weinig: N=2.
Misschien een domme vraag hoor, maar waarom zoudt ge twee basisgevallen nodig hebben?

User avatar
Robbe
WOZ
Posts: 2161
Contact:

Post#7 » Sun May 20, 2007 4:51 pm

omdat 1 basisgeval niet alles dekt? neem bijvoorbeeld het optellen van alle even of oneven getallen. Je trekt van het gegeven getal 2 af en telt dat bij het totaal. Je kan zo op 1 of op 0 komen, hence 2 basisgevallen ;)

Of zoals de Van Steen het al wel eens heeft aangehaald: als 1 vrouw blond is, zijn alle vrouwen blond. Neem een groep van 1 vrouw, dan zijn ze allemaal blond. Neem nu een populatie van n vrouwen, en neem daar een groep van n-1 vrouwen uit. Als 1 vrouw hiervan blond is, dan zijn ze allemaal blond. Neem een andere groep uit dezelfde populatie, nu met de vrouw die je daarnet niet had. Omdat n-2 vrouwen uit die groep al blond zijn, is die ene vrouw die we er net bij hebben genomen ook blond. Hier zijn we dus het basisgeval van een populatie van 2 vrouwen vergeten.

Get my point? :)
"I'm not afraid of falling, I'm afraid of landing" -- Sam
How To Ask Questions The Smart Way

Zingen? UKA-n dat ook!

User avatar
Shinta
WOZ
Posts: 1122

Post#8 » Sun May 20, 2007 7:23 pm

tstaat gewoon vol fouten :) Da van joeri vink wel mooi uitgelegd.
Remember remember the fifth of November
Gunpowder, treason and plot.
I see no reason why gunpowder, treason
Should ever be forgot...

User avatar
Dave
WOZ
Posts: 816

Post#9 » Sun May 20, 2007 7:41 pm

Shinta wrote:tstaat gewoon vol fouten :) Da van joeri vink wel mooi uitgelegd.
Idd, kben zelf te lui om het uit te werken :p
En een tegenvoorbeeldje is genoeg om de foutiviteit van de stelling aan te tonen.

User avatar
Math Wolf
Posts: 4053
Contact:

Re: Zoek de fout

Post#10 » Mon May 28, 2007 5:53 pm

Robbe wrote:Further, it is sufficient to show that for all N > 0, if A and B (positive integers) satisfy (MAX(A, B) = N) then A = B.
Dit klopt niet of is fout geformuleerd.
Robbe wrote:Assume that the theorem is true for some value k. Take A and B with MAX(A, B) = k+1. Then MAX((A-1), (B-1)) = k. And hence (A-1) = (B-1). Consequently, A = B.
[/list]
Dit klopt eveneens niet. Als B=1 (dit kan) dan B-1 = 0 (hier verlaat je de ruimte waarover je werkt en bijgevolg heb je geen eis gesteld hierop.)
2014: Jan16, Feb15, Mar16, Apr15, May14, Jun13, Jul12, Aug10, Sep9, Oct8, Nov6, Dec6
2015: Jan5, Feb5, Mar5, Apr4, May4, Jun2, Jul2, Jul31, Aug29, Sep28, Oct27, Nov25, Dec25

Return to “Algemeen”

Who is online

Users browsing this forum: No registered users and 5 guests

cron