kortste weg

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
JackMol
Vast lid
Vast lid
Berichten: 84
Lid geworden op: 06 jun 2018, 21:01

kortste weg

Bericht door JackMol » 11 jan 2020, 16:29

https://snipboard.io/nIEvck.jpg

Na lange tijd zoeken kwam ik 55 (D) als antwoord uit.
Kon ik het veel sneller vinden door op logische wijze na te denken/formules te gebruiken?

arie
Moderator
Moderator
Berichten: 3583
Lid geworden op: 09 mei 2008, 09:19

Re: kortste weg

Bericht door arie » 12 jan 2020, 12:13

Afbeelding

Markeer punten met een oneven aantal lijnen rood, en met een even aantal lijnen blauw (figuur (a)).
Als het aantal lijnen van een punt even is (blauw), dan kunnen we elke keer dat we dat punt binnen komen er ook weer uit. In principe kunnen we dus alle lijnen van elk blauwe punt meenemen in ons pad.
Bij de rode punten zal er altijd de laatste lijn onbenut moeten blijven, anders lopen we vast met ons pad: als we er de laatste keer binnen komen kunnen we er niet meer uit. De enige uitzondering hierop zijn de rode punten die het beginpunt en het eindpunt van ons pad zijn.

In figuur (b) zijn alle rode punten met een kortste (rode) lijn verbonden, dat zijn de lijnen die het minste verlies opleveren voor ons pad, en die we dus bij voorkeur opofferen.

In figuur (c) maken we ons pad, te beginnen bij het rode punt A, dat zo veel mogelijk zwarte lijnen bevat. In dit geval lukt het om alle zwarte lijnen te doorlopen, en eindigen we tenslotte in het rode punt B.
De totale lengte van ons pad is 4*(4+5+4) + 3 = 55.
Behalve rode lijnstukken CD, EF en GH hebben we alle lijnstukken doorlopen.
We weten nu zeker dat we het langste pad gevonden hebben.

JackMol
Vast lid
Vast lid
Berichten: 84
Lid geworden op: 06 jun 2018, 21:01

Re: kortste weg

Bericht door JackMol » 12 jan 2020, 13:11

Bedankt voor de zeer uitgebreide uitleg!

JackMol
Vast lid
Vast lid
Berichten: 84
Lid geworden op: 06 jun 2018, 21:01

Re: kortste weg

Bericht door JackMol » 12 jan 2020, 13:14

Als je een bepaalde zijde gebruikt hebt, mag je het dan nog eens RAKEN?

arie
Moderator
Moderator
Berichten: 3583
Lid geworden op: 09 mei 2008, 09:19

Re: kortste weg

Bericht door arie » 12 jan 2020, 13:48

Het staat niet expliciet in de opgave, maar als je "elk lijnstuk één keer mag gebruiken" houdt dat in dat je met je pen niet twee of meer keer over dat lijnstuk mag gaan. Je pad mag wel meerdere keren een zelfde punt passeren.
Dit is hetzelfde als de (bekende) vraag om het huisje te tekenen zonder je pen van papier te halen en zonder dubbele lijnpassages:

Afbeelding

In feite worden dit soort problemen (en nog veel meer) bestudeerd in de grafentheorie, zie bijvoorbeeld
https://nl.wikipedia.org/wiki/Grafentheorie.

JackMol
Vast lid
Vast lid
Berichten: 84
Lid geworden op: 06 jun 2018, 21:01

Re: kortste weg

Bericht door JackMol » 12 jan 2020, 16:42

Bedankt!

Plaats reactie