Wiskundeforum

Naar aanleiding van een probleem op de VWO was ik terug op zoek gegaan naar het topic Secretaris in Wiskundige puzzels. Maar ik kan dit niet meer vinden. Ik heb de link nog teruggevonden in mijn browsergeschiedenis:
viewtopic.php?t=7893&f=28#p46317. Ik vraag me af of het aan mijn browser ligt of dat dit per ongeluk is verwijderd door iemand?

Voor de geïnteresseerden, de aanleiding was VWO 2004-2005 ronde 2, vraag 18:
Een fotograaf zal een familiefoto maken van de 8 leden van het gezin Van Paemel, die allen een verschillende lichaamslengte hebben. Hij wil hiervoor deze acht personen in twee rijen van vier plaatsen, zodat in beide rijen de lichaamslengte toeneemt van links naar rechts en zodat achter elke persoon op de eerste rij een grotere persoon plaatsneemt.
Op hoeveel manieren kan hij de gezinsleden plaatsen?
A) 14
B) 16
C) 18
D) 20
E) 22
Je kan best "8" vervangen door 2n en "4" door n.

Het onderwerp is verwijderd. Er staat geen reden bij.

Ok, dat zal wel iemand per ongeluk hebben gedaan. Kan gebeuren.

Doet me denken aan een recent project euler probleem.

http://projecteuler.net/problem=412

Deze link zal je helpen.

http://en.wikipedia.org/wiki/Young_tableau

Ik had het zelf ook niet gevonden

Overigens de oplossing van het secretaris probleem vind je hier

http://en.wikipedia.org/wiki/Catalan_number

De Catalan getallen kon ik me nog wel herinneren
Ik ga eens denken over dat project Euler probleem.

Nog 2 vragen:

[1] Lukt het je om te bewijzen dat het hier gaat om Catalan-getallen?

[2] Lukt het je om het oorspronkelijke probleem (met 2n = 8\) met de hand op te lossen (dus zonder de theorie van de Catalan-getallen) ?

[1] ja hoor.
Je vertrekt van de rij .
Je kiest er n getallen uit die op de achterste rij komen en op de voorste rij.
Te bewijzen: op elk moment in de rij zijn er minstens evenveel v's als a's.
Bewijs: veronderstel van niet, dan is er op een bepaald moment (na 2m+1 getallen voor de eerste keer) één a meer dan dat er v's zijn.
want dan zou bij de eerste 2m getallen er 2 a's meer zijn en dan is onze situatie niet de eerste keer dat ze voorkomt. Dus , echter zodat wat niet mocht. Het te bewijzen is dus waar.
(nogal omslachtig, maar dat is om het strikt te bewijzen)

[2] Ik zou gewoon de mogelijkheden uitschrijven, omdat redeneren al snel voor problemen zorgt, het is vrij complex.
Dat is ook wat men hier op p.5 suggereert: http://www.q-e-d.be/doc/Voorronden.pdf
Het zal nog vrij vlug gaan eens je de systematiek doorhebt van de Catalan getallen (zonder te weten wat ze zijn).

ad [1]:

Mooi!
Alternatief bewijs: neem een bekend probleem waarvan het bewezen is dat het gaat om Catalan-getallen, en construeer vervolgens een 1-op-1 afbeelding van ons fotograafprobleem naar dat bekende probleem.

Voorbeeld:
Zie de wiki pagina waar wnvl naar verwees:
http://en.wikipedia.org/wiki/Catalan_number
Daar is bewezen dat het aantal monotone paden dat niet boven de diagonaal komt in een n*n rooster gelijk is aan C(n):


- nummer de pijlen van 1 t/m 8 volgens de volgorde van het pad
- het nummer van de horizontale pijlen plaats je achtereenvolgens van links naar rechts op de eerste rij in je fotograafprobleem
- het nummer van de verticale pijlen plaats je achtereenvolgens van links naar rechts op de tweede rij in je fotograafprobleem
Elk mogelijk monotoon pad vormt nu precies een opstelling van 8 personen op 2 rijen, in de juiste volgorde van links naar rechts.
Komt het pad boven de diagonaal <=> er staat een groter nummer op de eerste rij dan op de corresponderende plaats in de tweede rij (er is dan immers een hoger horizontaal pijlnummer bij een lager aantal plaatsingen op de eerste rij).

NOOT: dit is soms een handige en snelle bewijsmethode, maar je bewijs rust hierbij volledig op het bewijs van het eerste (=bekende) probleem. Mocht dit laatste achteraf onjuist blijken, dan moet je jouw stelling alsnog op een andere manier bewijzen.


ad [2]:

In wedstrijdsituaties leek me gestructureerd uitschrijven ook veel sneller:
Voor 2n = 8 geldt:
1 en 8 liggen vast:
- - - 8
1 - - -

7 heeft 2 mogelijkheden:
- - 7 8
1 - - -
of:
- - - 8
1 - - 7

In het eerste geval zoeken we nog x en y zodat
y x 7 8
1 - - -
een toegestane foto-opstelling is.

als x=6 zijn er voor y 4 mogelijkheden (5,4,3 of 2)
als x=5 zijn er voor y 3 mogelijkheden (4,3 of 2)
als x=4 zijn er voor y 2 mogelijkheden (3 of 2)
voor x=3 en x=2 zijn er geen oplossingen.
In totaal levert deze variant dus 9 oplossingen.

In het tweede geval:
- - - 8
1 - - 7
zijn dit precies het aantal oplossingen voor het 2n=6 probleem.
Dit zijn er 5 (nog sneller door uitschrijven te vinden).

In totaal dus 9+5 = 14 mogelijkheden


PS: leuk pdf document

Marco gefeliciteerd met deze heugelijke dag!