vierkanten

[arnerob]

hallo,

Ik zoek de oplossing van dit probleem (dat ik tegenkwam tijdens het spelen van een computerspel):

Je hebt een vierkant, onderverdeeld in hokjes, aan iedere zijde evenveel. Een aantal hokjes (zo weinig mogelijk) moeten gemarkeerd worden zodat aan ieder gemarkeerd hokje een niet-gemarkeerd grenst (dus niet schuin).

Ik heb geprobeerd met vierkanten van verschillende grote, maar ik zou graag een algemene oplossingsmethode kennen.

[arnerob]

http://desmond.imageshack.us/Himg838/scaled.php?server=838&filename=vierkanten.jpg&res=landing

[Drieske]

Het spel zegt me iets, maar niet genoeg om de exacte regel(s) te herinneren. Wel weet ik dat er sowieso bij jou nog wat ontbreekt: zo weinig mogelijk is natuurlijk steeds 0 en als dat niet mag 1. Dus: wat is die bijkomende regel? Het gehele veld "bereiken"?

[arnerob]

Het doel is dat ieder blokje 1 aan een blokje 0 grenst. Het 'lights out' probleem lijkt hier een beetje op maar heeft een ander doel, en dus een andere oplossing. http://www.whitman.edu/mathematics/lights_out/

[physicalattraction]

Het komt er in principe op neer dat je met "kruisen" van vijf hokjes je hele grid moet overdekken. Bij een voldoende groot grid komt het erop neer dat je het aantal hokjes telt, dit deelt door vijf en dan nog gaat prutsen aan de randen.

Opmerking moderator

@arenrob: kun je je plaatjes hier als bijlage uploaden, i.p.v. op een externe site te zetten?

[EvilBro]

Moet het probleem niet gesteld worden als:

Je hebt een vierkant, onderverdeeld in hokjes, aan iedere zijde evenveel. Een aantal hokjes (zo weinig mogelijk) moeten gemarkeerd worden zodat aan ieder niet-gemarkeerd hokje een gemarkeerd grenst (dus niet schuin).

[Onwetend]

Ik begrijp het probleem (ook) niet helemaal. Wat is nu de bedoeling?

Als het zo is dat 2 vierkanten niet recht aan elkaar mogen grenzen lijkt me dit simpel:

je verdeelt het aantal hokjes op de omtrek (= (4x de zijde - 4)) in 2, zodat telkens een wit hokje op een rood hokje volgt

het aantal vierkanten is dan geiljk aan 1/2 x ((aantal hokjes zijde) x 4 - 4 )

Als het zo is dat 2 rode hokjes niet recht of schuin aan elkaar mogen grenzen, moeten er tussen 2 rode hokjes niet 1 wit hokje maar 2 witte hokjes.

dan is het aantal rode hokjes dus gelijk aan 1/3 x ((aantal hokjes zijde) x 4 - 4 )

Het eerste vierkant in jouw plaatje sluit aan bij de eerste situatie, het tweede en derde plaatje sluit aan bij de tweede situatie.

Als ik echter deze zin lees:

Een aantal hokjes (zo weinig mogelijk) moeten gemarkeerd worden zodat aan ieder gemarkeerd hokje een niet-gemarkeerd grenst (dus niet schuin).

krijg ik het idee dat het het beste is om in elk vierkant maar 1 hokje rood te markeren. Je voldoet dan aan de regels wat betreft grenzen en je hebt zo weinig mogelijk blokjes.... maar dat is vast niet wat je bedoelt.

[Drieske]

Volgens mij zie je het iets te simpel, Onwetend... Het gaat niet over een configuratie, maar over de minimale. Die lijkt me anders in jouw 2 situaties. Maar sowieso moet TS gewoon duidelijker verwoorden wat hij nu juist zoekt.

krijg ik het idee dat het het beste is om in elk vierkant maar 1 hokje rood te markeren. Je voldoet dan aan de regels wat betreft grenzen en je hebt zo weinig mogelijk blokjes.... maar dat is vast niet wat je bedoelt.

Als je echt over minima wilt praten, dan is, zoals ik al eerder zei (zie post #3), dat eigenlijk 0. Maar onze opmerking ligt in dezelfde lijn: er moet een eis gelegd worden zodat je verplicht wordt iets te kleuren.

[arnerob]

@onwetend: dan vind je meestal geen goeie oplossing zoals bvb 5x5 (groen grenst niet aan een rood blokje)

hier zijn de criteria:

criteria:

1. ieder rood hokje moet aan een wit hokje grenzen

2. er moeten zo weinig mogelijk rode hokjes zijn

[317070]

Je verdeelt je rooster in 3x3 blokken en kleurt daarvan telkens het middelste vakje in? Dat is het efficientst en dus minimaal.

[arnerob]

Je verdeelt je rooster in 3x3 blokken en kleurt daarvan telkens het middelste vakje in? Dat is het efficientst en dus minimaal.

met grenzen bedoel ik: niet schuin

[Math-E-Mad-X]

criteria:

1. ieder rood hokje moet aan een wit hokje grenzen

Ik neem aan dat het omgekeerde ook moet gelden: ieder wit hokje moet aan een rode grenzen.

Anders is de oplossing simpel: nul rode hokjes!

[arnerob]

Ik neem aan dat het omgekeerde ook moet gelden: ieder wit hokje moet aan een rode grenzen.

Anders is de oplossing simpel: nul rode hokjes!

ja, sorry, ik bedoelde dat het omgekeerde moest gelden

ieder wit hokje moet aan een rode grenzen

[EvilBro]

Victory is mine!

Je moet volgens mij meer te weten zien te komen over saturated domino coverings.

[arnerob]

dank je wel, ik heb het nog niet volledig gelezen, maar de inleiding zag er veelbelovend uit