Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

Hekjesdenken


In Puzzels, door wiskundemeisjes

IBM Research zet elke maand een wiskundig vraagstuk op hun site. Je hebt nog tot 1 augustus om over volgende probleem na te denken...


hekje

Given a square piece of property of unit side you wish to build fences so that it is impossible to see through the property, ie there is no sightline connecting two points outside the property and passing through the property that does not intersect a fence. The fences do not have to be connected and several fences can come together at a point. What is the minimum total length of fencing required and how is it arranged? For example you could place fencing along all four sides. This would have total length 4 but is not the best possible. The fences can be placed in the interior of the property, they aren't restricted to the boundary.

hekje

De puzzelmaker heeft zelf geen bewijs dat zijn eigen oplossing minimaal is. Hoe goed kunnen jullie het doen?

(Ionica)

19 reacties op “Hekjesdenken”

  1. Maarten:

    Aha, prikkelend!
    Mijn eerste inval is een kruis (verbind de tegenoverliggende hoekpunten). Dat heeft lengte wortel 8, wat in ieder geval een stuk kleiner is dan 4. Maar het kan zeker beter, ik kom nu tot 1 + wortel 3 met een zeshoekige structuur. Of dit minimaal is weet ik niet.

  2. koen:

    Mijn eerste gedacht zijn de 2 diagonalen als hek te nemen. Maar dit is puur intuitief, geen idee of dit de minimale oplossing is, waarschijnlijk niet. Daar moet ik nog een beetje verder voor denken :)

  3. wynolt:

    ik zit nu op 2,707...

  4. Gieljan:

    Ik kom ook op 2 + Sqrt[1/2] uit. Blauw zijn de hekken; de twee lange zijdes zitten uiteraard op de grens van het vierkant ipv een fractie erbinnen, maar dit ziet er wat beter uit.
    Oplossing Giel

  5. Ionica:

    @Maarten: Hoe doe je die zeshoekige structuur? Kun je daarbij echt nergens langs de zijden over het land kijken?

    Voor de rest: mijn kamergenoot Sierk heeft een betere oplossing gevonden dan Gieljan (maar die ga ik natuurlijk niet posten)...

  6. Johan:

    Ik heb een oplossing waar ongeveer 2.64 uitkomt. :).

  7. Sander:

    1 + wortel 3 had ik als beste connected oplossing, maar deze was zeker niet zeshoekig.

    Ik zit nu op 2.6389... voor mijn laatste oplossing.

  8. Johan:

    Ik denk in dat wij dezelfde oplossing gevonden hebben, Sander. ;)

  9. Maarten:

    @ Ionica
    Mijn "zeshoekige" oplossing is een boom (type graaf) met vijf kanten en hoekpunten (0,1), (1,1), (0,0), (1,0), (1/2, 1 / ( 2 sqrt(3))) en (1/2, 1- 1 / (2 sqrt(3))). Deze is samenhangend en zeshoekig in de zin dat de hoeken allemaal 120 graden zijn.
    De oplossing van Gieljan is korter, slim gevonden! Niet zo vreemd eigenlijk, want mijn hekjes hebben een iets sterkere eigenschap. Namelijk dat je niet van een zijde van het viekant naar een andere zijde kunt lopen (eventueel over een krom pad) zonder een hek tegen te komen. Waarschijnlijk is dit probleem allang opgelost in de percolatietheorie, maar daar weet ik helaas erg weinig van :-(

  10. Sander:

    @Maarten: Die had ik ook voor m'n samenhangende oplossing. Het is de Steiner tree van de vier hoekpunten.

  11. anonieme valsspeler:

    Werkt het als je in het midden een grote + neerzet en dan verder het cartesisch produkt erbij doet van twee Cantorverzamelingen? Zal wel niet...

    Een variant op Banach-Tarski misschien?

  12. Maarten:

    @ Sander en Johan
    Met 2,6389 wordt hoogstwaarschijnlijk
    sqrt (2) + sqrt (3/2) bedoeld. In de bijbehorende oplossing is het punt (x,x) verbonden met drie hoekpunten, waarbij
    2 x = 1 - 3^(-1/2). Ik ben er inmiddels wel van overtuigd dat dat optimaal is. Heeft iemand al een bewijs? Een opzetje:
    1) een minimale oplossing bestaat uit lijnstukken
    2) de hoeken die de lijnstukken in een minimale oplossing maken zijn allemaal veelvouden van 60 graden, ook als de lijnstukken elkaar niet snijden
    3) onder voorwaarden 1) en 2) zijn er slechts een paar lokaal minimale oplossingen, modulo symmetrie
    4) bereken de lengten voor deze gevallen
    Overigens lijken 1) - 3) me niet zo simpel, dus ik laat het graag aan iemand anders over om dit hard te maken ;-)

  13. Thijs:

    Maarten, vanwaar substelling 2? Komt dat uit symmetrieoverwegingen over een ander argument?

  14. Maarten:

    @Thijs
    Nou, als ik het kon bewijzen dan deed ik dat wel ;-) Maar ik heb er wel een idee bij. Stel dat je drie lijnstukken hebt, van punten P1, P2 en P3 naar een punt S, zodanig dat de onderlinge hoeken niet allemaal 120 graden zijn. Dan kan je S een beetje verschuiven zodat
    |P1 - S| + |P2 - S| + |P3 - S|
    kleiner wordt. Kijkend naar de oplossing van Sander en Johan denk ik dat iets dergelijks ook geldt voor lijnen die niet snijden.

  15. Henkie:

    ik begrijp die oplossing niet, Maarten. Als je slechts 3 hoekpunten verbindt, dan is aan de opgave toch nog niet voldaan? Ik interpreteer je oplossing waarschijnlijk niet juist. Kan je anders eens een afbeelding van die oplossing tonen? Ik ben benieuwd

  16. Thijs:

    Maarten, wat je zoekt heb ik gister gevonden. Namelijk het Fermat point, de optimale S om de lijnstukken te verbinden, en zolang geen van de hoeken van de driehoek >120 graden is, maken de drie 'hekjes' een onderlinge hoek van 120 graden. Ik zou trouwens niet weten waarom die hoek van n*60 graden ook geldig zou moeten zijn voor lijnen die 'niets met elkaar te maken hebben', dwz, elkaar niet snijden.

  17. Matthijs Coster:

    Toevallig lees ik momenteel "the Colossal book of short puzzles and problems" (p. 461), waarin honderden puzzels van Martin Gardner worden beschreven. Een van de puzzels gaat over een "opaque square". De bovengenoemde oplossing wordt eveneens beschreven. Als je op "opaque square" googlet kom je ook diverse oplossingen tegen. Ook kom je de "opaque cube" tegen. Dat is eigenlijk leuker om eens eerst zelf over na te denken.

  18. Marco:

    Heeft iemand zijn oplossing al naar IBM gestuurd? Als jouw naam in de lijst komt weet je dat niemand een betere oplossing heeft.

  19. Ionica:

    Inmiddels is de oplossing al geplaatst bij IBM:
    http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2007.html
    Het is inderdaad dezelfde!

    En (nog interessanter) er staat een nieuw probleem:

    Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
    For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
    Describe, in a single sentence, the sequence {f(n)/f(n-1)} for positive integer n-s.
    Show your proof to this sentence.

Plaats een reactie


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