Roosterpuntdriehoek [15+]

[barto]

Een driehoek wordt in het vlak gevormd door twee vaste roosterpunten,

\(O(0,0)\)

en

\(P(a,b)\)

, en een derde variabel roosterpunt,

\(Q(x,y)\)

. Wat is, in functie van

\(a\)

en

\(b\)

, de minimale waarde dat de oppervlakte van

\(\bigtriangleup OPQ\)

kan aannemen?
(Dus

\(a,b\in\mathbb Z_0\)

en

\(Q\notin OP\)

.)

De vraag is een veralgemening van Vraag 25, Ronde 2 van de Vlaamse Wiskunde Olympiade van 1987.

[wnvl]

Eerste idee.

Het minimum van

\(\frac{1}{2}\left | ka+lb \right |\)

met k en l geheel. Het minimum moet wel groter dan 0 zijn.

ggd(a,b)/2 ?

[op=op]

Ik heb geen idee wat je met

\(\mathbb{Z}_0\)

bedoelt.

min(a,b)/2.

[barto]

\(\mathbb Z_0\)

: de gehele getallen zonder 0...
wnvl: ggd(a,b)/2 is goed.

Zelfde vraag voor een viervlak: O(0,0,0) en P(a,b,c) liggen vast en Q,R zijn variabele roosterpunten. Wat is de minimale inhoud van OPQR? (a,b,c verschillend van 0)

En wat voor OPQRS?
(misschien komt die inhoudsformule van hier nog van pas, ik weet het zelf niet: viewtopic.php?f=13&t=5758)

[toonijn]

\(\frac{1}{6}\begin{vmatrix}0 & 0 & 0 & 1\\a & b & c & 1\\x_1 & y_1 & z_1 & 1\\x_2 & y_2 & z_2 & 1\end{vmatrix}=-\frac{1}{6}\begin{vmatrix}a & b & c\\ x_1 & y_1 & z_1\\x_2 & y_2 & z_2\end{vmatrix}=\frac{1}{6}(-a\begin{vmatrix}y_1 & z_1\\ y_2 & z_2\end{vmatrix}+b\begin{vmatrix}x_1 & z_1\\ x_2 & z_2\end{vmatrix}-c\begin{vmatrix}x_1 & y_1\\ x_2 & y_2\end{vmatrix})\)

Als we hier kunnen uitgaan van een 3-voudige lineaire combinatie is her resultaat dus:

\(\frac{1}{6}\gcd(a,b,c)\)

[barto]

akkoord, en eenvoudig uitbreidbaar naar hogere dimensies. 8)

[toonijn]

Om uit te gaan van 3-voudig lineair combineren, klein bewijsje:

ggd(a,b,c) = ggd(ggd(a,b), c) = ggd(xa+yb, c) (met xa+by de kleinste lineaire combinatie)
= z(xa+yb) + uc
= zxa + zyb + uc
=

\(ax_1 + bx_2 + cx_3\)

(hernoemen)

[wnvl]

= zxa + zyb + uc
=

\(ax_1 + bx_2 + cx_3\)

(hernoemen)

Ik zeg niet dat het verkeerd is (ik weet het niet).

Maar die laatste stap lijkt mij louche.

x_1=zx en x_2=zy

x_1 en x_2 moeten dus een veelvoud zijn van z en zijn niet vrij te kiezen.

[toonijn]

x_1=zx en x_2=zy

x_1 en x_2 moeten dus een veelvoud zijn van z en zijn niet vrij te kiezen.

Analoog zou je evengoed kunnen stellen dat x_2 en x_3 veelvouden moeten zijn, of x_1 en x_3

Het zegt ook niet wat x_1, x_2 en x_3 zijn. Het zegt dat er bestaan waarbij de ggd verkregen wordt.

Bij een gewone lineaire combinatie zijn x en y (in ggd(a,b)=ax+by) ook niet vrij te kiezen. Het zegt dat er bestaan.

[wnvl]

\(\frac{1}{6}\begin{vmatrix}0 & 0 & 0 & 1\\a & b & c & 1\\x_1 & y_1 & z_1 & 1\\x_2 & y_2 & z_2 & 1\end{vmatrix}=-\frac{1}{6}\begin{vmatrix}a & b & c\\ x_1 & y_1 & z_1\\x_2 & y_2 & z_2\end{vmatrix}=\frac{1}{6}(-a\begin{vmatrix}y_1 & z_1\\ y_2 & z_2\end{vmatrix}+b\begin{vmatrix}x_1 & z_1\\ x_2 & z_2\end{vmatrix}-c\begin{vmatrix}x_1 & y_1\\ x_2 & y_2\end{vmatrix})\)

Als we hier kunnen uitgaan van een 3-voudige lineaire combinatie is her resultaat dus:

\(\frac{1}{6}\gcd(a,b,c)\)

Wat ik wil bedoelen is dat er een verband bestaat tussen de coëfficiënten van a, b en c in de lineaire combinatie. Doordat in de determinanten dezelfde getallen terugkomen. Dit verhindert misschien dat het mogelijk is om de ggd te vormen. Dat ontbreekt m.i. in je bewijs.

[toonijn]

Ja 'k begrijp wat je wilt zeggen. Is er een mogelijkheid om dit probleem te verhelderen?

[barto]

ggd(a,b,c)|xa+yb+zc : triviaal toch?
Voor een streng bewijs:
ggd(a,b,c)|ggd(a,b)|xa+yb dus ggd(a,b,c)=ggd(ggd(a,b),c)|ggd(xa+yb,c)|xa+yb+zc
Want dat laatste is een lineaire combinatie van xa+yb en c.

Dit geeft echter geen antwoord op het tweede probleem...
Te bewijzen is dat

\(\left\{\begin{matrix} y_1z_2-y_2z_1=u\\ x_1z_2-x_2z_1=v\\ x_1y_2-x_2y_1=w \end{matrix}\right.\)

oplossingen heeft voor elke (u,v,w).

[wnvl]

Te bewijzen is dat

\(\left\{\begin{matrix} y_1z_2-y_2z_1=u\\ x_1z_2-x_2z_1=v\\ x_1y_2-x_2y_1=w \end{matrix}\right.\)

oplossingen heeft voor elke (u,v,w).

Met alle variabelen gehele getallen.

Dat is inderdaad de kern van het probleem.
Ik heb geen idee hoe je dit aanpakt.

[barto]

Neem

\(y_1z_2=f_1\)

,

\(y_2z_1=f_2\)

, ... dus je geeft alle mogelijke producten (3*2=6) een naam.
Dat geeft een nieuw, lineair stelsel in

\(f_1,...,f_6\)

en heeft oneindig veel oplossingen in gehele getallen.
Op te lossen is nu

\(\left\{\begin{matrix} y_1z_2=f_1\\ y_2z_1=f_2\\ x_1z_2=f_3\\ x_2z_1=f_4\\ x_1y_2=f_5\\ x_2y_1=f_6 \end{matrix}\right.\)

voor minstens één waarde van (f_1,...,f_6).

Als dit de goede richting uitgaat, tenminste.

[barto]

De oplossing voor dat laatste is

\(y_1=\frac{f_1}{z_2}=\frac{f_1x_1}{f_3}=\frac{f_1f_5}{f_3y_2}=...=\frac{f_1f_5f_4y_1}{f_3f_2f_6}\)

en dat geeft geen oplossing. Analoog voor de andere variabelen, dus dit is een dood spoor.

\(\left\{\begin{matrix} y_1z_2-y_2z_1=u\\ x_1z_2-x_2z_1=v\\ x_1y_2-x_2y_1=w \end{matrix}\right.\)

dus,

\(\gcd(y_1,y_2)|u\)

,

\(\gcd(z_1,z_2)|u\)

, en analoog voor v,w.
Nu moet het verder gaan met deelbaarheid, aangenomen dat au+bv+cw=ggd(a,b,c).