Ongelijkheid

[PhilipVoets]

Vraag: hoeveel getallen uit de verzameling {1,2,3,...,99} kan je maximaal kiezen zodat er geen twee getallen a en b gekozen zijn waarvoor a + b < 1 + 2sqrt(ab)?

Mijn (gedeeltelijke) oplossing:
a + b < 1 + 2sqrt(ab)
a + b - 2sqrt(ab) < 1
(sqrt(a) - sqrt(b))^2 < 1
En hier vermoedde ik dat door het kwadraat gold voor de ongelijkheid dat het teken ook kon omklappen, dus:
sqrt(a) - sqrt(b) < 1 of > 1, waardoor de vraag eigenlijk wordt gereduceerd tot: hoeveel getallen uit de genoemde verzameling kunnen paren vormen waarvoor geldt: sqrt(a) - sqrt(b) = 1, wat alleen lukt met de kwadraten, dus: 1, 4, 9, 16, 25, …, 81 (e.g., sqrt(9) - sqrt(4) = 1), dus totaal: 9, wat ook het antwoord zou moeten zijn, maar mijn kennis van hoe het ook alweer zat met regels rondom ongelijkheden is iets te roestig om hier zeker van te zijn. Toelichting is welkom, dank alvast!

[Xilvo]

Vraag: hoeveel getallen uit de verzameling {1,2,3,...,99} kan je maximaal kiezen zodat er geen twee getallen a en b gekozen zijn waarvoor a + b < 1 + 2sqrt(ab)?

Dan moet je gelijke getallen in ieder geval uitsluiten, want daarvoor geldt de ongelijkheid altijd:
\(2a<1+2 \sqrt{a^2}\)

De formule iets anders geschreven levert \(\frac{a+b}{2}-\sqrt{a b}<\frac{1}{2}\)
Dus, voor welke \(a\) en \(b\) is het rekenkundig gemiddelde minder dan een half groter dan het meetkundige gemiddelde. Die mogelijkheid wil je dus uitsluiten.

Het rekenkundig gemiddelde is altijd groter dan het meetkundige gemiddelde als a en b ongelijk zijn, dus meestal zal aan de eis (dat de ongelijkheid niet opgaat!) voldaan zijn. Alleen als a en b dicht bij elkaar liggen niet.

Als \(b=a+x\), dan ligt de grens bij ongeveer \(x=2\sqrt a\)

[PhilipVoets]

Dank, en enig idee hoe de oplossing dan "9" zou moeten zijn. Zit er nog iets in mijn redenering of slaat die de plank mis?

[Xilvo]

Dank, en enig idee hoe de oplossing dan "9" zou moeten zijn. Zit er nog iets in mijn redenering of slaat die de plank mis?

Volgens mij is die correct.

[PhilipVoets]

Dus de gedachtensprong dat zowel <1 als >1 geldt door het kwadraat klopt? Want dan blijven alleen de hele kwadraten over voor het scenario sqrt(a) - sqrt(b) = 1 en klopt het antwoord.
Ik moet zeggen dat ik de vraag ook wat “vreemd” geformuleerd vind, maar goed, ik ben ook geen wis- of natuurkundige.

[Xilvo]

Dus de gedachtensprong dat zowel <1 als >1 geldt door het kwadraat klopt? Want dan blijven alleen de hele kwadraten over voor het scenario sqrt(a) - sqrt(b) = 1 en klopt het antwoord.
Ik moet zeggen dat ik de vraag ook wat “vreemd” geformuleerd vind, maar goed, ik ben ook geen wis- of natuurkundige.

Ik zou niet verder gaan dan \((\sqrt a - \sqrt b)^2 < 1\)
Haal je het kwadraat weg, dan kan de vorm negatief worden. Dan moet ook de 1 van teken wisselen, en "<" wordt ">"

Aan de vorm hierboven mag niet voldaan worden, dus krijg je \((\sqrt a - \sqrt b)^2 \ge 1\)
De waardes die jij vindt gelden als beide leden precies gelijk zijn, dan krijg je natuurlijk een volgorde met opeenvolgende kwadraten.

[RedCat]

Het lijkt me dat ze bedoelen:
Wat is de maximale grootte van een deelverzameling S van verzameling V = {1,2,3,...,99},
zodanig dat voor elk tweetal elementen a en b in S geldt dat \((\small \sqrt{a} - \sqrt{b})^2 \ge 1\)

Dan moet gelden
\(\small \sqrt{b} \le \sqrt{a} - 1\)
of
\(\small \sqrt{b} \ge \sqrt{a} + 1\)

Als we aannemen dat a de kleinste van de twee is, dan vervalt de eerste ongelijkheid, en volgt uit de tweede:
\(\small b \ge a + 1 + 2\sqrt{a}\)
(a en b zijn beide positief, dus er ontstaan geen problemen met kwadrateren)

Als 1 = het kleinste element van V in S zit, dan geldt voor het volgende element b:
\(\small b \ge 1 + 1 + 2\sqrt{1} = 4\)
in dit geval kunnen alle elementen groter of gelijk aan 4 dus ook in S zitten.

Als we als tweede element 4 = de kleinste van de overgebleven toegestane elementen kiezen, dan geldt voor het derde element (nu is het kleinste getal a=4 in de formule):
\(\small b \ge 4 + 1 + 2\sqrt{4} = 9\)
in dit geval kunnen alle elementen groter of gelijk aan 9 dus ook in S zitten.

Zo doorgaand met steeds de kleinste mogelijkheden selecteren vinden we jouw oplossing met de kwadraten:
S = {1, 4, 9, 16, 25, 36, 49, 64, 81}
De eerstvolgende toegestane toevoeging zou dan 100 zijn, maar die zit niet in V.
Conclusie:
Er kunnen dus maximaal 9 elementen in S zitten als we aan de gestelde voorwaarde moeten voldoen.


Overigens: er zijn vele verschillende deelverzamelingen met 9 elementen mogelijk waarbij aan die voorwaarde voldaan wordt, bijvoorbeeld:
S = {2, 6, 12, 20, 30, 42, 56, 72, 90}
S = {2, 6, 12, 20, 30, 42, 56, 73, 92}
S = {3, 8, 15, 24, 35, 48, 63, 80, 99}
De volgende vragen zijn dan natuurlijk: (1) hoeveel verschillende van deze deelverzamelingen met 9 elementen bestaan er, en (2) hoeveel deelverzameling met een ongelimiteerd aantal elementen bestaan er onder de gestelde voorwaarde?
Maar dat is voor een andere keer.

[PhilipVoets]

Helder, dank! Net even de fine-tuning waar ik naar opzoek was!

[PhilipVoets]

Het lijkt me dat ze bedoelen:
Wat is de maximale grootte van een deelverzameling S van verzameling V = {1,2,3,...,99},
zodanig dat voor elk tweetal elementen a en b in S geldt dat \((\small \sqrt{a} - \sqrt{b})^2 \ge 1\)

Dan moet gelden
\(\small \sqrt{b} \le \sqrt{a} - 1\)
of
\(\small \sqrt{b} \ge \sqrt{a} + 1\)

Als we aannemen dat a de kleinste van de twee is, dan vervalt de eerste ongelijkheid, en volgt uit de tweede:
\(\small b \ge a + 1 + 2\sqrt{a}\)
(a en b zijn beide positief, dus er ontstaan geen problemen met kwadrateren)

Als 1 = het kleinste element van V in S zit, dan geldt voor het volgende element b:
\(\small b \ge 1 + 1 + 2\sqrt{1} = 4\)
in dit geval kunnen alle elementen groter of gelijk aan 4 dus ook in S zitten.

Als we als tweede element 4 = de kleinste van de overgebleven toegestane elementen kiezen, dan geldt voor het derde element (nu is het kleinste getal a=4 in de formule):
\(\small b \ge 4 + 1 + 2\sqrt{4} = 9\)
in dit geval kunnen alle elementen groter of gelijk aan 9 dus ook in S zitten.

Zo doorgaand met steeds de kleinste mogelijkheden selecteren vinden we jouw oplossing met de kwadraten:
S = {1, 4, 9, 16, 25, 36, 49, 64, 81}
De eerstvolgende toegestane toevoeging zou dan 100 zijn, maar die zit niet in V.
Conclusie:
Er kunnen dus maximaal 9 elementen in S zitten als we aan de gestelde voorwaarde moeten voldoen.


Overigens: er zijn vele verschillende deelverzamelingen met 9 elementen mogelijk waarbij aan die voorwaarde voldaan wordt, bijvoorbeeld:
S = {2, 6, 12, 20, 30, 42, 56, 72, 90}
S = {2, 6, 12, 20, 30, 42, 56, 73, 92}
S = {3, 8, 15, 24, 35, 48, 63, 80, 99}
De volgende vragen zijn dan natuurlijk: (1) hoeveel verschillende van deze deelverzamelingen met 9 elementen bestaan er, en (2) hoeveel deelverzameling met een ongelimiteerd aantal elementen bestaan er onder de gestelde voorwaarde?
Maar dat is voor een andere keer.

Als er meerdere verzamelingen S mogelijk zijn, klopt het antwoord 9 dan wel? Of moet er gekeken worden naar de opties waarbij de uitkomst een geheel getal oplevert? er bekruipt me allemaal het gevoel dat de vraag “onhandig” gesteld/geformuleerd is…

[Xilvo]

Als er meerdere verzamelingen S mogelijk zijn, klopt het antwoord 9 dan wel? Of moet er gekeken worden naar de opties waarbij de uitkomst een geheel getal oplevert? er bekruipt me allemaal het gevoel dat de vraag “onhandig” gesteld/geformuleerd is…

De vraag lijkt me duidelijk. Je vroeg naar het maximale aantal. Dat is 9, en daar zijn een paar oplossingen voor.

[RedCat]

Vraag: hoeveel getallen uit de verzameling {1,2,3,...,99} kan je maximaal kiezen zodat er geen twee getallen a en b gekozen zijn waarvoor a + b < 1 + 2sqrt(ab)?

In de combinatoriek kom je dit soort vragen tegen. Het is een korte en bondige formulering van het volgende:
We hebben een verzameling V = {1, 2, 3, ... , 99}.
Dit zijn de gehele getallen 1 t/m 99, en dit zijn de enige getallen waarmee we werken.
Hieruit gaan we er een aantal kiezen, dat wil zeggen:
we maken een deelverzameling S ⊆ V, waarbij de getallen die we gekozen hebben precies de elementen van S zijn.
Aan onze keuze is verder deze voorwaarde gesteld:
Van de gekozen getallen, dus in deelverzameling S, mogen zich geen twee getallen a en b bevinden zodanig dat
\(\small a + b < 1 + 2\sqrt{ab}\)
De vraag is dan: hoeveel getallen uit V kan je zo maximaal kiezen, dus hoe groot kan S maximaal worden?

Het aantal mogelijkheden om S te construeren doet er dus niet toe, de vraag is hoe groot S maximaal kan worden.
(met |S| = 9 kom ik overigens uit op 19683 verschillende deelverzamelingen).

[PhilipVoets]

Helder, grootste deel was me al duidelijk Dank!
Als 1 = het kleinste element van V in S zit, dan geldt voor het volgende element b = 4, in dit geval kunnen alle elementen groter of gelijk aan 4 dus ook in S zitten. De vraag is nog even: als alle getallen 4 of hoger in S kunnen zitten, waarom dan alleen 4 zelf in S opgenomen wordt en horen niet bijvoorbeeld ook 5, 6, etc. in S? Die voldoen toch ook aan >4? Ik snap de redenering voor b = 4, maar niet direct voor b is 4 of groter.. Dan zou ik op een antwoord veel groter dan 9 uitkomen

[RedCat]

Hoe kleiner het getal dat je kiest, hoe kleiner het volgende getal dat je kiest mag zijn.
Als we na de 1 als tweede getal het getal 4 kiezen, dan hebben we voor het derde getal keuze vanaf 9
Zouden we na de 1 als tweede getal het getal 5 kiezen, dan hebben we voor het derde getal keuze vanaf 11
Zouden we na de 1 als tweede getal het getal 6 kiezen, dan hebben we voor het derde getal keuze vanaf 12

Dit geldt voor elk getal: hoe kleiner we een getal kiezen, hoe kleiner we ook het volgende getal mogen kiezen.
We willen steeds het kleinste getal kiezen, om op die manier zo veel mogelijk getallen in S te krijgen.

Anders bekeken: zouden we na het eerste getal 1 het tweede getal 81 (of hoger) kiezen, wat ook groter is dan 4, dan mogen we helemaal geen derde getal meer toevoegen en blijven we zitten met een verzameling S met grootte |S| = 2
En we zoeken juist de grootst mogelijke afmeting van S.

Merk nog op: als we eenmaal als tweede getal 4 gekozen hebben, dan mogen we 5, 6, 7 en 8 niet meer als derde getal toevoegen aan S. De 9 is vanaf dan de eerstvolgende mogelijkheid.

[PhilipVoets]

Dank, duidelijk, alleen wat die laatste alinea betreft; waarom niet? Mag je 1 niet tweemaal gebruiken voor een getallenpaar a en b (e.g., a = 1 en b = 4 en a = 1 en b = 5 als twee verschillende getallenparen binnen dezelfde deelverzameling S die allebei aan de gestelde voorwaarde voldoen)? Want je gebruikt 4 ook dubbel/in twee getallenparen; 1 en 4 en daarna 4 en 9.

[RedCat]

Bij de constructie van S kijk je telkens na de keuze van een getal (a) wat het eerstvolgende grotere getal (b) mag zijn,
maar bij het testen van de voorwaarde moeten we naar ALLE mogelijke tweetallen {a, b} in S kijken: geen enkel tweetal in S mag in strijd zijn met de voorwaarde. Dit betekent dat we bij het testen van S voor elk getal alle combinaties met de andere getallen moeten bekijken.

Voorbeeld:
De eerste keuze 1 blokkeert alleen 2 en 3: b=4 is de eerstvolgende mogelijke keuze:
Stel je maakt S = {1, 2}, dan zijn er een a=1 en b=2 waarvoor \(\small (a+b = 3) < (1+2\sqrt{ab}\approx 3.83)\)
Stel je maakt S = {1, 3}, dan zijn er een a=1 en b=3 waarvoor \(\small (a+b = 4) < (1+2\sqrt{ab}\approx 4.46)\)
De aanwezigheid van 1 maakt geen bezwaar tegen getallen van 4 of groter.

We kiezen als tweede getal 4: S = {1, 4}
Deze keuze 4 blokkeert voor ons derde getal de 5, 6, 7 en 8.
Stel je maakt S = {1, 4, 5}, dan zijn er een a=4 en b=5 waarvoor \(\small (a+b = 9) < (1+2\sqrt{ab} \approx 9.94)\)
Er is in dit geval dus een tweetal elementen in S te vinden (4 en 5) dat in strijd is met de voorwaarde.
We testen dus alle mogelijke tweetallen in S: {1, 4} is OK, {1, 5} is OK, {4, 5} is strijdig, dus deze S voldoet niet.

Het element 1 heeft geen problemen met 5: de 1 staat alle getallen van 4 of hoger toe,
Het element 4 mogen we niet combineren met 5: de 4 staat alleen getallen van 9 of hoger toe.
Samen staan de 1 en 4 dus alle getallen van 9 of hoger toe, vandaar dat het kleinste eerstvolgende grotere getal 9 is.