[L03] Equilatero?

[Gerald Lambeau]

Sia $n$ un intero positivo. Numeriamo i vertici di un $3n$-agono regolare con i numeri da $1$ a $3n$. Determinare il più piccolo intero positivo $m$ (con $m \le n$) tale che, comunque si scelgano $m$ vertici tra $1$ e $n$, altri $m$ tra $n+1$ e $2n$ e ancora altri $m$ tra $2n+1$ e $3n$, allora ne esistono $3$ che formano un triangolo equilatero.

[Roob]

Prima di tutto è evidente che tre vertici formano un triangolo equilatero se e solo se sono del tipo [tex]i, i+n, i+2n[/tex] ([tex]1\leq i\leq n[/tex]), altrimenti le distanze tra i vertici sarebbero diverse tra loro.
Creiamo quindi [tex]n[/tex] insiemi che chiameremo [tex]V_i=\{i, i+n, i+2n\}[/tex], con [tex]1\leq i\leq n[/tex]
Prendendo in totale almeno [tex]2n+1[/tex] vertici per pigeonhole in almeno uno dei [tex]V_i[/tex] ci saranno [tex]3[/tex] elementi, e avremo quindi un triangolo equilatero.
Per avere in totale almeno [tex]2n+1[/tex] vertici serve che in ognuno dei tre sottoinsiemi ci siano almeno [tex]\displaystyle \frac {2n+1}{3}[/tex] elementi, da cui [tex]m=\displaystyle \left\lceil \frac {2n+1}{3} \right\rceil[/tex]

[Gerald Lambeau]

Dovresti anche mostrare che per $m$ più piccolo è possibile che non ci siano triangoli equilateri.

[Roob]

Ah, vero. Allora:
Caso 1
[tex]n=3k[/tex].
In questo caso [tex]\left\lceil \frac {2n+1}{3}\right\rceil=\left\lceil \frac {6k+1}{3}\right\rceil=2k+1[/tex]. Serve quindi una configurazione con [tex]2k[/tex] vertici da ogni sottoinsieme. Basta prendere per il primo i vertici da [tex]1[/tex] a [tex]2k[/tex], nel secondo quelli da [tex]4k+1[/tex] a [tex]6k[/tex], nel terzo quelli da [tex]6k+1[/tex] a [tex]7k[/tex] e da [tex]8k+1[/tex] a [tex]9k[/tex].
Caso 2
[tex]n=3k+1[/tex]
In questo caso [tex]\left\lceil \frac {2n+1}{3}\right\rceil=\left\lceil \frac {6k+3}{3}\right\rceil=2k+1[/tex]. Anche adesso servono [tex]2k[/tex] vertici in ogni sottoinsieme. Basta prendere per il primo i vertici da [tex]1[/tex] a [tex]2k[/tex], nel secondo quelli da [tex]4k+2[/tex] a [tex]6k+1[/tex], nel terzo quelli da [tex]6k+3[/tex] a [tex]7k+2[/tex] e da [tex]8k+3[/tex] a [tex]9k+2[/tex]
Caso 3
[tex]n=3k+2[/tex].
In questo caso [tex]\left\lceil \frac {2n+1}{3}\right\rceil=\left\lceil \frac {6k+5}{3}\right\rceil=2k+2[/tex]. Servono [tex]2k+1[/tex] vertici in ogni sottoinsieme. Basta prendere per il primo i vertici da [tex]1[/tex] a [tex]2k[/tex] e [tex]3k+1[/tex], nel secondo quelli da [tex]4k+3[/tex] a [tex]6k+2[/tex] e [tex]6k+3[/tex], nel terzo quelli da [tex]6k+5[/tex] a [tex]7k+4[/tex], da [tex]8k+5[/tex] a [tex]9k+4[/tex] e [tex]9k+6[/tex].

Se di tutto questo non si capisce niente ho diviso ognuno dei sottoinsiemi in altre tre parti, ognuna lunga [tex]k[/tex], più [tex]1[/tex] o [tex]2[/tex] eventuali vertici di resto, e li ho presi in modo da non avere tre vertici congrui modulo [tex]n[/tex], se non fosse che è uscita una cosa un poco bruttina

[Gerald Lambeau]

Tranquillo, si capisce. Tutto giusto!