Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

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?

24 reacties op “Jeanine op kamp (3)”

  1. ace:

    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.

  2. Johan B.:

    Dit is geen bewijs dat het niet met minder dan n kan, ace. :).

  3. ace:

    Nee, maar ik ben dan ook geen wiskundige. ;-)

  4. Eline:

    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?

  5. Johan B.:

    Om ziek te kunnen worden, moeten er minstens 2 vakjes naast je al ziek zijn, Eline.

  6. Eline:

    Ow! Zie je, ik wist gewoon dat ik wat miste, het was zo'n makkelijk raadsel ;)

  7. Relinde:

    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?

  8. SvdB:

    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.

  9. ace:

    @SvdB: Ja verrek, je hebt gelijk!

  10. Reijer:

    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.

  11. Reijer:

    Ach laat maar, het stond er expliciet bij :).

  12. Albert Hendriks:

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

  13. Johan B.:

    Tja, Hendiks, volgens mij gaat het in jouw voorbeeld van 8 naar 8.

  14. Johan B.:

    Sorry, typefoutje, ik bedoelde natuurlijk Hendriks

  15. Albert Hendriks:

    Hmm, in dat geval begrijp ik het niet: hoe tel je "De som van de omtrekken van alle aaneengesloten zieke gebieden"?

  16. Johan B.:

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

  17. Marco:

    Zijn er geen mooiere kleurtjes voor de spoilerbalken dan zwart? Dit ziet er een beetje treurig uit zo...

  18. Johan B.:

    Is stel roze met een bloemetjesmotief voor. :).

  19. ismay b:

    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

  20. N.H.:

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

  21. KvD:

    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.

  22. leo:

    Ik hou het op een dubbele diagonaal d.w.z. 2n besmette vakjes vanuit 1 hoek naar de tegenoverliggende.

  23. hendrik th van asselt:

    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)

  24. Roderik:

    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.

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.