grootst mogelijke w =/= a x + b y + c z

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
eensteven
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 02 apr 2017, 12:10

grootst mogelijke w =/= a x + b y + c z

Bericht door eensteven » 02 apr 2017, 12:22

In EOS stond er een opgave: wat is de grootst onmogelijke bestelling bitterballen die je kan plaatsen als je mag bestellen per 6, 9 en/of 20. Met wat logisch denken kan je er eigenlijk op komen maar een vriend schreef iets in Python dat ook het juiste antwoord opleverde.

Alleszins, ik vroeg hem toen na te gaan welke set van drie natuurlijke getallen onder de 100 (n) de grootst onmogelijke bestelling oplevert. Beetje te gemakkelijk zou zijn de drie hoogste even getallen onder de 100 (dan kan je nl. nooit een oneven bestelling vormen). We sloten daarom sets met grootst gemene deler groter dan 0 uit. Ook sets waarbij een van de elementen een veelvoud is van een van de twee andere elementen, weerhielden we al a priori niet. Soit, lang verhaal kort, ze draaiden iets in python met n = 10 , 20, 40 (dat duurde al enkele minuten dus tot 100 zijn we niet gegaan) en telkens won de set [n-3 , n-2 , n-1]. Wat we ons afvroegen, kan bewezen worden dat er altijd een w =/= a (n-3) + b (n-2) + c (n-1) bestaat die groter is dan eender welke w die niet gevormd kan worden door sets 'kleiner dan' [n-3 , n-2 , n-1] en onder eerder vermelde voorwaarden?

Hopelijk duidelijk, ik ben helemaal geen wiskundige, jaren geleden dat ik me er nog mee bezig hield dus sorry als het een stomme of onbegrijpelijke vraag is...

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

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door arie » 02 apr 2017, 13:40

Je bent op zoek naar Frobenius getallen, zie bv
https://en.wikipedia.org/wiki/Coin_problem#Statement
Meer naar onderen op die pagina staat trouwens ook jullie McNugget probleem.

Het Frobenius getal van n=3 gegeven getallen, dit is F(a1, a2, a3), kan je berekenen met
het algoritme van Rödseth:
https://en.wikipedia.org/wiki/Numerical ... _algorithm

Komen jullie hiermee verder?

eensteven
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 02 apr 2017, 12:10

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door eensteven » 02 apr 2017, 19:00

Dat ziet er interessant uit, bedankt!

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

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door arie » 02 apr 2017, 22:38

Hier vond ik ook nog een Frobenius calculator:
http://mathsjavascript.free.fr/frobenius_9_page.html
Wellicht ook handig.

eensteven
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 02 apr 2017, 12:10

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door eensteven » 04 apr 2017, 15:09

Leuk inderdaad. Waar ik wel nog een beetje op mijn honger blijf zitten (maar misschien kan ik het zelf ook wel eens uitvissen), valt te bewijzen dat het Frobeniusgetal van een set met de hoogste elementen uit een bepaald bereik (dus bijv. 96, 97, 98 als we drie getallen onder de 100 in een set mogen steken) steeds het Frobeniusgetal van alle andere mogelijke sets overtreft?

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

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door arie » 06 apr 2017, 08:04

Met 3 getallen onder 100 EN gcd(a,b,c)=1 EN elk getal geen veelvoud van een ander getal,
dan is:
g(96,97,98) = 4607
g(97,98,99) = 4655
In het algemeen: neem de verzameling { N-2, N-1, N} als N het grootst toegestane getal is.

Een bewijs zal lopen via de lijnen van Theorem 6 (pg 321) in dit artikel:
http://www.emis.de/journals/DMTCS/pdfpa ... AE0162.pdf
Daar hebben ze echter alleen de voorwaarden:
1 <= a < b < N
en
gcd(a,b,N) = 1

Dit betekent dat een getal nog wel een veelvoud mag zijn van een ander getal.
Voorbeeld:
gcd(5,10,11) = 1, en g(5,10,11) = g(5,11) = 55 - 5 - 11 = 39
terwijl g(9,10,11) = 35

Als je de voorwaarden neemt:
1 <= a < b < N
en
gcd(a,b,N) = 1
en
de getallen zijn twee-aan-twee geen veelvoud van elkaar

dan verwacht ik dat je uitkomt op de verzameling A1 = {N-2, N-1, N} van Dixmier in bovenstaand artikel, waarbij voor

N even:

N oneven:

maar het bewijs hiervan laat ik verder aan jullie over.

eensteven
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 02 apr 2017, 12:10

Re: grootst mogelijke w =/= a x + b y + c z

Bericht door eensteven » 18 apr 2017, 13:49

arie schreef:maar het bewijs hiervan laat ik verder aan jullie over.
Bedankt, ik vrees echter dat dat ons petje te boven gaat, moest er toch iets uit de bus komen, lees je het hier ;-)

Plaats reactie