bult-plat-histogram van verhaaltjescombi
Opgave - BxMO 2012 dag 1 vraag 4
Gisteren zaten er $ n \ge 4$ ridders aan een ronde tafel. Ieder van de ridders heeft
alleen onthouden wie zijn twee buren waren, maar niet welke van de twee links van hem zat en
welke van de twee rechts. Vandaag willen we deze groep ridders weer zo om de tafel plaatsen dat
iedereen dezelfde buren heeft als gisteren (waarbij het mogelijk is dat iemand z'n rechterbuur
van gisteren vandaag zijn linkerbuur is). Je mag enkele ridders ondervragen over zijn buren:
zo'n ridder zal dan zijn twee buren van gisteren aanwijzen.
$(a)$ Bepaal het minimale aantal ridders $f(n)$ dat je hiervoor naar zijn buren moet vragen, als
je je keuze voor een nieuwe ridder om te ondervragen, niet mag laten afhangen van de
antwoorden die eerder ondervraagde ridders gegeven hebben. Je moet dus van tevoren
een lijst maken met ridders die je wilt ondervragen, voordat je aan het daadwerkelijke
ondervragen begint.
$(b)$ Bepaal het minimale aantal ridders $g(n)$ dat je hiervoor naar zijn buren moet vragen,
als je je keuze voor een nieuwe ridder om te ondervragen, wel mag laten afhangen van
de antwoorden die eerder ondervraagde ridders gegeven hebben. Je mag dus eerst $1$
ridder ondervragen en daarna besluiten wie je als tweede ridder ondervraagt, enzovoorts.
- login om te reageren
Oplossing
$(a)$
opl
Indien we $n-4$ ridders vragen wie naast hen zat, is het mogelijk dat ze allemaal naast mekaar zaten, waardoor we slechts $n-4+2 = n-2$ ridders 100% zeker in de juiste volgorde naast mekaar kunnen zetten (al dan niet gespiegeld). Als we de andere twee echter indelen, kunnen we niet zeker zijn of het klopt, gezien we ze op twee verschillende manieren kunnen aan de tafel zetten, terwijl er maar één klopt.
Indien we $n-3$ ridders vragen wie naast hen zat, weten we van hoogstens $1$ ridder niet wie naast hem zat. Dit gebeurt enkel in het geval dat alle ondervraagde ridders naast mekaar zaten, waardoor we van $n-1$ ridders de plaats weten en de ene overblijvende plaats aan de tafel kunnen we dus zonder problemen invullen, want er is maar $1$ mogelijkheid. Als niet alle ondervraagde ridders naast mekaar zaten, weten we zeker hoe de ridders zaten, gezien we dan van iedereen minstens 1 buur kennen en van iedereen behalve $\le 2$ ridders beide buren.
Bijgevolg geldt: $f(n)=n-3$
$(b)$
schets
Als we alles willen te weten komen met zo min mogelijk ondervragingen, is het van belang dat we zo weinig mogelijk dezelfde info krijgen. We ondervragen dus steeds een ridder waar we nog niks van weten. Nadat we zo over iedereen info gekregen hebben, kunnen we alle aanwezigen indelen in groepjes van 3, waarbij sommige paren groepjes één element gemeenschappelijk hebben met mekaar en andere groepjes geen enkel element met een ander.
Indien alle groepjes met 2 andere groepen overlappen, krijg je de cirkel rond met $n/2$ ondervragingen indien het $n$ even is, in het andere geval met $(n+1)/2$. Echter kunnen we indien we over $1$ persoon geen info hebben, deze toch indelen, dus bij een even aantal moeten we in dit geval $n/2 - 1$ ridders ondervragen, bij een oneven aantal $(n+1)/2 - 1$, wat samen geschreven kan worden als $(n+n \pmod 2)/2-1$.
Aan het andere uiterste kunnen we ook bijna allemaal aparte groepjes vinden (met enkele overlappende groepjes indien de groep niet deelbaar is door 3). We moeten dan voor iedere volledige $3$ ridders nogmaals een ridder ondervragen om deze groepjes te verbinden (waarbij we wederom de laatste ondervraging kunnen weglaten, gezien we weten dat het een kring is).
Indien we meer overlapping hebben, hebben we minder afzonderlijke groepjes, gezien het minimumaantal in een groepje $3$ is en we dus minder groepjes kunnen vormen indien er een groep meer is die dan $3$ elementen bevat.
Indien we één afzonderlijke groep minder hebben, kost info over iedere ridder verzamelen ons één extra ondervraging, maar moeten we ook één keer minder ondervragen om de groepjes aan mekaar te verbinden.
dus $g(n)= \lceil \frac{ 2n -5}{3} \rceil$ na wat proberen
opl
We zullen bewijzen dat het juiste antwoord $g(n)= \lceil \frac{ 2n -5}{3} \rceil$ is.
Stel $A=$ aantal personen die ondervraag werden waarvoor nog geen buur gekend was
$B=$ aantal personen van wie al $1$ buur gekend is
$C=$ aantal personen van wie al $2$ buren gekend zijn
Als we van $2$ personen weten, dat ze naast elkaar zaten, noemen we dit een gekende buurrelatie.
Er zijn dan in totaal $n$ buurrelaties en men moet er minimum $n-1$ weten of $n-2$ indien er over exact $1$ ridder niks is gekend.
Wanneer we weten dat alle personen gerankschikt zijn, hebben $A+B+C$ mensen ondervraagd, we kregen $2A+B$ buurrelaties.
Het is duidelijk dat $C=0$ nodig is om zo $A+B+C$ te minimaliseren, waarbij $2A+B \ge n-2.$
deel $1$: we bewijzen dat er een strategie is die met deze $g(n)$ steeds werkt.
Onze strategie is om een ridder te ondervragen steeds waarvan we nog niks van weten wanneer er zo'n ridders zijn, uitgezonderd wanneer we slechts $2$ buurrelaties te kort hebben.
Als $n \equiv 1 \pmod{3} $ of $n=3k+1$ voor zekere $n$
Merk op dat we steeds minimum $k+1$ A-ondervragingen kunnen doen.
Als we nog $3k-2A$
B-ondervragingen verrichten, hebben we $B+A=3k-A\le 2k-1$ vragen moeten stellen, zoals gewenst.
Als $n \equiv 2 \pmod{3} $ of $n=3k+2$ voor zekere $n$
$A \ge k+1$ en $B= 3k+1-2A$ geeft terug dat we $n-1$ buurrelaties kennen, maar $A+B= n-1-A \le 2k$ personen hebben moeten ondervragen.
Als $n \equiv 3 \pmod{3} $ of $n=3k$ voor zekere $n$
analoog, We hebben hier dat $A \ge k$ en met $B=3k-1-2A$ ondervragen weten we terug alles. Dus $A+B=3k-1-A \le 2k-1$
Hiermee zien we dat de formule inderdaag geldt door op te splitsen in deze $3$ gevallen.
deel $2$: We bewijzen nu dat voor iedere strategie $h(n)\ge \lceil \frac{ 2n -5}{3} \rceil$ is.
Als $n \equiv 1 \pmod{3} $ of $n=3k+1$ voor zekere $n$, met $2k-2$ mogelijkheden kan men t nooit zeker zijn:
Omdat men duidelijk enkel met A- en B-ondervragingen kan werken,
moet $A+B= 2k-2$ en $2A+B \ge 3k-1$ wat betekent dat $A\ge k+1$.
Indien men met deze strategie pech heeft, zal iedere A-persoon $2$ onbekende buren hebben.
Bekijk het aantal mensen dat nog geen gekende buren geeft, iedere (C,)B-stap geeft dat dit aantal niet stijgt.
Bij pech wodt bij het A-vragen, dit getal met $3$ kleiner zolang dit kan, na $k$ ondervragingen is dit dus max. $1.$
Enkel in dit geval kan $h(n)$ werken met $A \ge k+1$ , maar nu hebben we wel in dit worst-case-scenario dat niemand $2$ onbekende buren geeft en moest $2A+B \ge 3k$ en dus $A \ge k+2$ wat onmogelijk is.
Contradictie met het feit dat $h(n)$ werkte in alle gevallen.
*$n=3k+2$ voor zekere $n$, met $2k-1$ mogelijkheden :
$A+B= 2k-1$ en $2A+B \ge 3k$ wat betekent dat $A\ge k+1$, maar analoog aan vorig geval kan dit in het worstcasescenario enkel wanneer voor iedereen een buur gekend is, aangezien na $k$ ondervragingen bij pech maximaal $2$ buren vrij kunnen zijn, zodat met $3k$ buurrelaties het nog niet zeker is. $A=k+2$ leidt dan terug naar een contradictie.
*$n=3k$ voor zekere $n$, met $2k-2$ mogelijkheden :
$A+B=2k-2$ en $2A+B \ge 3k-2$ betekent $A \ge k$, maar met $A=k$ ondervragingen in ons worstcasescenario hebben we van iedereen een buur gekend, zodat met $3k-2$ buurrelaties de reconstructie niet zeker is. Contradictie
We besluiten dus dat onze $g(n)$ het gevraagde minimale aantal is.