162. Un problema che non vorresti ti capitasse in gara

[Troleito br00tal]

Ok, mi automodero: basta spam troleito

[Gottinger95]

AHAHAHAH sei malvagio e basta

EDIT: ok basta spam, però un hint me lo merito dai (anche tra qualche giorno, se vostra grazia ritiene)

[Troleito br00tal]

Vada per l'hint numero 2.

[Gottinger95]

Eh? Sarà che ho dormito tre ore stanotte, ma...cosa?

[Troleito br00tal]

È arrivata l'ora di hintare:

Testo nascosto:

Oltre ai due hint che ho già dato:

ti dico che in gara questo problema sicuramente non verrebbe... prova ad immedesimarti in chi l'ha creato e a cercare di risolverlo dall'altra parte!

[jordan]

Non voglio venire a rompere, ma c'era il limite di una settimana per i problemi della staffetta

[Troleito br00tal]

E quindi che faccio? Do un altro hint? Posto un altro problema?

[Troleito br00tal]

Io proporrei di lasciare questo irrisolto, se volete io ho un altro problema che può essere postato, oppure lo può postare jordan, oppure gottinger95.

[jordan]

Potresti postare la tua soluzione? Ci ho provato anch'io, inutilmente..

[Troleito br00tal]

Ecco la soluzione.

La risposta è, in realtà, no. Perché non ho dato hint notevoli? Perché se avessi rivelato già quale fosse stata la risposta il problema sarebbe diventato facilissimo (e piuttosto noioso).

Troviamo quindi un controesempio!

Un controesempio carino che mi è venuto in mente è $n=(8!+8)^2$.

Osservazioni: come ha detto Gottinger95, $g(n) \le \sqrt{n}$. Inoltre, le varie iterazioni di un generativo $y$ sono necessariamente multipli di $y$, da cui gli elementi generativi possono essere solo i numeri $\le \sqrt{n}$.

Controesempio: vogliamo dimostrare che non è possibile che $1;2;...;8!+8$ siano generativi nell'insieme $S((8!+8)^2)=(1;2;...;(8!+8)^2)$. In realtà ci basta imporre che $8!+8;8!+7;...;8!$ siano generativi e contare un po' tutto, notando che:
-i multipli di $8!+k$ dove $0 \le k \le 8$ sono $8!+16-k$;
-non esistono numeri in $S((8!+8)^2)$ che sono multipli di tre numeri tra $8!;...;8!+8$;
- dati due numeri $8!+k$ e $8!+j$ hanno esattamente $(k;j)$ multipli in comune in $S((8!+8)^2)$.

Adesso enuncio il fulcro della dimostrazione: il numero di multipli tra i numeri $8!+8;...;8!$ è minore di $(8!+8)+...+(8!)$, pertanto, questi $9$ numeri non possono essere tutti generativi.

Unendo questa con le precedenti osservazioni otteniamo che i multipli dei numeri $8!+8;...,8!$ in $S((8!+8)^2)$ sono:
$8!+8$ (multipli di $(8!+8)$) $+8!+9$ (multipli di $(8!+7)$) ecc... ovvero $9 \cdot 8! + 108$ meno $(8;7)$ (multipli comuni fra $8$ e $7$), $(8;6)$,...,$(7;4)$,... ecc..., ovvero meno $74$, da cui i multipli di almeno uno fra $8!+8;...;8!$ sono $9 \cdot 8!+34$, ma $(8!+8)+...+(8!)=9 \cdot 8!+36$.
Pertanto, poiché ci sono più iterazioni necessarie perché $8!;...;8!+8$ siano generativi di quanti siano i loro multipli $(9 \cdot 8! + 36 > 9 \cdot 8! + 34)$, questo è un controesempio.

Perché ho messo questo problema? A parte per la soddisfazione di aver trovato un problema con un bound che si rivela falso dopo moltissimo, perché forse sono stronzo.

Comunque, il primo hint era il no che ho dato di risposta a gottinger95 (Q: mi dai un hint? A: no), e poi vabbè, gli altri erano abbastanza autoreferenziali.

Detto questo, spero di non venire bannato per olocausto algebrico e bon.

Il problema mi è venuto in mente in circostanze strambe e random (ero al lago con amici a fare cose a caso). Sinceramente non conosco problemi simili (per fortuna).

Spero che vi sia piaciuto ^_^ e almeno sono stato coerente al mio nome (e poi nel titolo vi avevo avvertito)

[jordan]

Soluzione inaspettata e molto interessante, complimenti.

Visto che hai detto di averne un altro buono, procedi col prossimo!

[Gottinger95]

hahahahah grasse risate da parte mia bello comunque, ero convinto che fosse vero, e invece...non ho proprio pensato a un controesempio!