Topic verdwenen? = probleem vd fotograaf

Algemene info over deze site. Suggesties e.d. kunnen hier ook geplaatst worden.
Plaats reactie
Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Topic verdwenen? = probleem vd fotograaf

Bericht door barto » 13 feb 2013, 14:38

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.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Topic verdwenen?

Bericht door David » 13 feb 2013, 15:07

Het onderwerp is verwijderd. Er staat geen reden bij.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Topic verdwenen?

Bericht door barto » 13 feb 2013, 19:13

Ok, dat zal wel iemand per ongeluk hebben gedaan. Kan gebeuren. :|
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: Topic verdwenen?

Bericht door wnvl » 13 feb 2013, 22:08

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 :(

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: Topic verdwenen?

Bericht door wnvl » 13 feb 2013, 22:29

Overigens de oplossing van het secretaris probleem vind je hier

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

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Topic verdwenen?

Bericht door barto » 13 feb 2013, 23:16

De Catalan getallen kon ik me nog wel herinneren :wink:
Ik ga eens denken over dat project Euler probleem.
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Topic verdwenen?

Bericht door arie » 14 feb 2013, 12:30

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) ?

Gebruikersavatar
barto
Vergevorderde
Vergevorderde
Berichten: 654
Lid geworden op: 07 jun 2011, 16:02

Re: Topic verdwenen?

Bericht door barto » 14 feb 2013, 14:03

[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).
Given that, by scientifical reasons, the state of an object is completely determined by the physical influence of its environment, the probability to roll six with a dice is either one or zero.

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Topic verdwenen?

Bericht door arie » 14 feb 2013, 15:52

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):
Afbeelding

- 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

SafeX
Moderator
Moderator
Berichten: 14278
Lid geworden op: 29 dec 2005, 11:53

Re: Topic verdwenen? = probleem vd fotograaf

Bericht door SafeX » 01 mar 2013, 12:29

Marco gefeliciteerd met deze heugelijke dag!

Plaats reactie