Springen naar inhoud

vierkanten


  • Log in om te kunnen reageren

#1

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 07 juli 2012 - 17:02

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.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 07 juli 2012 - 17:20

http://desmond.image...jpg&res=landing

#3

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juli 2012 - 22:59

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"?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#4

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 08 juli 2012 - 12:55

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.e...ics/lights_out/

#5

physicalattraction

    physicalattraction


  • >1k berichten
  • 3104 berichten
  • Moderator

Geplaatst op 17 juli 2012 - 09:57

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?

#6

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 17 juli 2012 - 10:28

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

#7

Onwetend

    Onwetend


  • >250 berichten
  • 307 berichten
  • Verbannen

Geplaatst op 17 juli 2012 - 11:31

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.

#8

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 17 juli 2012 - 14:16

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.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#9

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 21 juli 2012 - 21:08

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


hier zijn de criteria:

criteria:
1. ieder rood hokje moet aan een wit hokje grenzen
2. er moeten zo weinig mogelijk rode hokjes zijn

Geplaatste afbeelding

#10

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 22 juli 2012 - 09:05

Je verdeelt je rooster in 3x3 blokken en kleurt daarvan telkens het middelste vakje in? Dat is het efficientst en dus minimaal.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#11

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 22 juli 2012 - 09:29

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

#12

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 22 juli 2012 - 12:32

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!

Veranderd door Math-E-Mad-X, 22 juli 2012 - 12:33

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#13

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 22 juli 2012 - 17:33

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

Veranderd door arnerob, 22 juli 2012 - 17:37


#14

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 23 juli 2012 - 07:35

Victory is mine!

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

#15

arnerob

    arnerob


  • 0 - 25 berichten
  • 13 berichten
  • Gebruiker

Geplaatst op 25 juli 2012 - 09:48

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures