Internetbureau Rotterdam 
Dit bericht is geplaatst op vrijdag 8 augustus 2008 om 10:00 in categorieën Puzzels. Je kunt de reacties volgen via een RSS 2.0 feed. Je kunt een reactie plaatsen, of een trackback van je eigen site plaatsen.
Wiskundemeisjes
Ionica & Jeanine
Jeanine op kamp (3)
In Puzzels, door Jeanine
Vandaag weer een puzzel van wiskundekamp!
Ziek
Van een nxn-schaakbord is een aantal vakjes ziek. Deze ziekte is erg besmettelijk. Als een vakje aan minstens twee zieke vakjes grenst (met een hele zijde), wordt dat vakje ook ziek. Aan het eind van de epidemie blijkt elk vakje ziek te zijn.
Hoeveel vakjes waren er aan het begin minstens ziek?
vrijdag 8 augustus 2008 om 10:37
n.
De “goedkoopste†manier om een vakje ziek te maken, is door er twee zieke vakjes naast te hebben. Wanneer de aanvankelijk zieke vakjes op een diagonaal staan, steken ze op de goedkoopste manier alle vakjes van de aangrenzende diagonaal aan, en die besmetten vervolgens op transitieve wijze de rest van het schaakbord, maar steeds eentje “naar binnenâ€. Naast een diagonaal van 10 zieke vakjes komt een diagonaal van 9 besmette vakjes, en zo voorts. Er is geen andere manier om de overgebleven vakjes te besmetten. Dus is het nodig om op de hele diagonaal zieke vakjes te hebben. De diagonaal mag overigens verschuiven over het schaakbord en dus halverwege overspringen (“omlopenâ€), maar de vakjes moeten wel aansluiten.
vrijdag 8 augustus 2008 om 11:54
Dit is geen bewijs dat het niet met minder dan n kan, ace. :).
zaterdag 9 augustus 2008 om 11:09
Nee, maar ik ben dan ook geen wiskundige. ;-)
zaterdag 9 augustus 2008 om 13:09
Een hoekvakje grenst aan de minste vakjes, en dit vakje grenst aan twee vakjes. Alle vakjes geven de ziekte dus door. Er hoeft in het begin dus maar één vakje ziek te zijn.
Zou ik zeggen. Maar wat zie ik nou over het hoofd?
zaterdag 9 augustus 2008 om 14:03
Om ziek te kunnen worden, moeten er minstens 2 vakjes naast je al ziek zijn, Eline.
zondag 10 augustus 2008 om 01:21
Ow! Zie je, ik wist gewoon dat ik wat miste, het was zo'n makkelijk raadsel ;)
zondag 10 augustus 2008 om 17:19
Hint voor een bewijs (waar ik voor de zekerheid zo'n zwart balkje over zal proberen te maken): Wat gebeurt er met de omtrek van alle zieke vakjes gedurende de epidemie?
zondag 10 augustus 2008 om 18:27
De som van de omtrekken van alle aaneengesloten zieke gebieden neemt nooit
toe wanneer er nieuwe hokjes ziek worden.
Bij een n*n bord is de totale omtrek 4*n, dus heb je ook een totale beginomtrek
van minstens 4*n nodig, waarvoor je minstens n hokjes nodig hebt.
Dit is ook altijd voldoende, want met een zieke diagonaal beginnen leidt op triviale wijze tot een geheel ziek bord.
De opmerking van ace over aansluitende zieke beginhokjes is overigens niet correct. De volgende beginsituaties bijvoorbeeld leiden uiteindelijk ook tot een volledig ziek bord.
- - - * - - - -
- * - - - - - -
- - - * - - - -
* - - - - - - -
- - - - * - - -
- - - - - - * -
- - - - * - - -
- - - - - - - *
* - - - - * - -
- * - - - - - -
- - - - - - - -
* - - - - - - -
- - - - - - - -
- * - - - - - -
- - - - - - - -
* - - * - - - *
Een andere interessante vraag is hoelang het kan duren voordat een epidemie het hele bord vult.
maandag 11 augustus 2008 om 08:29
@SvdB: Ja verrek, je hebt gelijk!
dinsdag 12 augustus 2008 om 10:35
Het lijkt erop dat iedereen ervan uitgaat dat vakjes alleen aan elkaar "grenzen" als ze een zijkant gemeenschappelijk hebben, en niet als ze slechts een hoek gemeenschappelijk hebben, dat is, ze grenzen diagonaal aan elkaar. In het laatste geval is het genoeg om te beginnen met 2 vakjes die zo liggen dat ze samen minstens een nieuw vakje besmetten.
dinsdag 12 augustus 2008 om 10:36
Ach laat maar, het stond er expliciet bij :).
donderdag 14 augustus 2008 om 22:41
Het bewijs van SvdB is volgens mij niet sluitend (of er moet iets beter worden gedefinieerd):
"De som van de omtrekken van alle aaneengesloten zieke gebieden neemt nooit toe wanneer er nieuwe hokjes ziek worden."
volgens mij gaat de som van de omtrekken van aaneengesloten gebieden van 2 naar 3 in het volgende 1x3 schaakbord:
*-*
vrijdag 15 augustus 2008 om 09:43
Tja, Hendiks, volgens mij gaat het in jouw voorbeeld van 8 naar 8.
vrijdag 15 augustus 2008 om 09:44
Sorry, typefoutje, ik bedoelde natuurlijk Hendriks
vrijdag 15 augustus 2008 om 09:49
Hmm, in dat geval begrijp ik het niet: hoe tel je "De som van de omtrekken van alle aaneengesloten zieke gebieden"?
vrijdag 15 augustus 2008 om 11:47
Wel, Appie, stel dat alle vakjes 1 cm bij 1 cm zijn. Dan is dus de omtrek van 1 vakje 4 centimeter, want er zitten 4 zijdes aan de rand. En de omtrek van 2 aaneengesloten vakjes is 6 cm (namelijk 1+2+1+2).
zaterdag 16 augustus 2008 om 10:35
Zijn er geen mooiere kleurtjes voor de spoilerbalken dan zwart? Dit ziet er een beetje treurig uit zo...
zaterdag 16 augustus 2008 om 15:10
Is stel roze met een bloemetjesmotief voor. :).
zaterdag 23 augustus 2008 om 11:38
Er moeten er 2 ziek zijn anders kunnen er geen andere ziek worden want als er 2 ziek zijn word er 1 andere ziek die kan weer samen met 1 van de andere samen werken om een andere ziek te maake
zondag 24 augustus 2008 om 16:49
je hebt drie vakjes nodig, want met 2 vakjes loopt het altijd vast! Met drie zieke vakjes is dit niet het geval, als je ze zo plaatst:
**
--
*
In een driehoekje met rechte zijdes 2 en drie dus!
Nu wordt wel heel het bord ziek :)
vrijdag 29 augustus 2008 om 10:32
2 of 3 vakjes zullen niet genoeg zijn, omdat zich uiteindelijk een rechthoek vormt in dat geval.
Een rechthoek van besmette vakjes kan geen ander vakje meer besmetten, mij lijkt het eerst gegeven antwoord van ace dus de juiste, er zijn minstens n zieken nodig.
woensdag 3 september 2008 om 09:52
Ik hou het op een dubbele diagonaal d.w.z. 2n besmette vakjes vanuit 1 hoek naar de tegenoverliggende.
donderdag 4 september 2008 om 10:07
Antwoord is 5. Gewoon uittekenen en dan zie je dat er minstens 9 vakjes nodig zijn, waarvan er 5 de ziekte hebben (een in het midden en vier op de vier hoekpunten)
woensdag 7 januari 2009 om 04:49
Het aantal benodigde vakjes is n. Het minimum van n is 0 waarbij alle (geen in dat geval) vakjes ziek zijn, dus 0 vakjes is het laagste benodigde aantal. (antwoord: 0)
Een echte wiskundige onderbouwing voor n heb ik niet, maar ik sluit me aan bij de oplossing van de diagonaal. De toevoeging van een kruisje (besmet punt) in het hoekpunt van een ander kruisje waarbij de lengte van de uit te breiden zijden van het door de epidemie gegenereerde rechthoek wordt gemaximaliseerd oogt optimaal in het geval van de diagonaal.