OliForum Matematico

Due amici, Alice e Bruno, decidono di fare il seguente gioco.
Bruno sceglie un numero intero positivo a≥3, e Alice disegna i vertici di un poligono convesso di a lati (solo i vertici).
A questo punto, Alice può dividere a in due fattori n e k, con n, k ∈ N, n≥3 (chiaramente sceglierà n e k nel modo per lui più conveniente), e compie la prima mossa. Una mossa consiste nel collegare tra loro due vertici del poligono.
Il gioco finisce quando almeno (n+k) vertici sono collegati ad almeno un altro vertice (in altre parole, almeno (n+k) vertici non risultano isolati), e vince chi ha compiuto l'ultima mossa. In particolare, se risulta che k=1, e quindi n+k>nk, il gioco finirà quando tutti i vertici saranno stati collegati ad almeno un altro di essi.
Determinare la/le tipologia/e di numeri a che consentono a Bruno di avere la certezza di vincere la partita (significato di tipologia: i numeri 3,5,7,9… sono della tipologia 2k+1).

Io ho una soluzione, magari tra un po' di giorni la scrivo XD

Iceman93 ha scritto:Alice può dividere a in due fattori n e k, con n, k ∈ N, n≥3 (chiaramente sceglierà n e k nel modo per lui più conveniente)

E' Alice che sceglie n e k giusto? Perchè leggendo il testo del problema vengono mooolti dubbi....

"Alice può dividere a in due fattori n e k"

Si, è lei XD

Per altri dubbi, chiedi pure...

Iceman93 ha scritto:Alice può dividere a in due fattori n e k, con n, k ∈ N, n≥3 (chiaramente sceglierà n e k nel modo per lui più conveniente)

"Lui" è un typo, volevi srivere "lei" (Alice)?

Ah scusami, ho scritto lui al posto di lei, non l'avevo notato XD Ok si sceglie Alice...

Chiedo venia XD E comunque magari aveva deciso di diventare un "lui" u.u

Consideriamo il caso in cui Alice scelga a e 1: nessuno ovviamente lascerà all'altro una situazione in cui mancano solo 2 o meno vertici ancora isolati (in quel caso vincerebbe l'avversario) quindi arrivati a tre vertici isolati entrambi attenderebbero collegando tra loro i vertici già collegati. Siccome le mosse sono $\binom{a-3}{2}$ Bruno deve scegliere a in modo che questa quantità sia pari: così Alice parte per prima, Bruno farà l'ultima mossa tra questi a-3 vertici e Alice sarà costretta a collegare 1 o 2 vertici isolati, e così Bruno vince.

Sicuramente quindi $a-3\equiv 0$ o $a-3 \equiv 1 \pmod4$, cioè $a\equiv 0 $ o $ a\equiv -1 \pmod4$.
Se quindi Bruno prende un primo congruo a -1 modulo 4 è sicuro di vincere.

Se ci sono altri numeri "buoni" non lo so, devo ancora pensarci....

P.S. sicuro che la condizione $n\geq 3$ non valga anche per $k$? Anche perchè se no Alice può "dribblare" la condizione prendendo $k=2$ e $n=\frac{a}{2}$ invece di $n=2$ e $k=\frac{a}{2}$ (che alla fine è la stessa cosa, tranne se $a\leq 4$).

auron95 ha scritto: Se quindi Bruno prende un primo congruo a -1 modulo 4 è sicuro di vincere.

Io, nella mia soluzione, ho scritto che tutti i numeri congrui a 3 mod 4 sono buoni... e questa tesi è stata avvalorata anche da un mio amico... vabbè, dai, ci penso su anche io

Praticamente continuando in quel modo, con numeri congrui a 1 o a 2 modulo 4 vince Alice. Con numeri congrui a 3 vince sicuramente Bruno. Con numeri multipli di 4 dipende.. Se sono anche multipli di 8, ad Alice basta prendere 2 ed il risultato della divisione che sarà comunque multiplo di 4 ottenendo come somma un numero del tipo 4k+2 e vincendo. Se il numero è multiplo di 4 ma non di 8, ovvero 4*dispari, allora Alice deve sperare che nel numero dispari che moltiplica 4 riesca a racimolare un fattore del tipo 4k+1. Ciò è sempre possibile tranne quando il dispari è un numero primo del tipo 4k+3, perchè se il dispari non è primo significa che contiene più di un fattore. Se ha almeno un fattore del tipo 4k+1 il problema non si pone. Se invece ha solo fattori del tipo 4k+3, non essendo primo basta prenderne 2 e il prodotto viene 4k+1. Quindi insomma se il dispari non è un primo del tipo 4k+3 vince Alice perchè prende un multiplo di 4 ed un fattore del tipo 4k+1 con una divisione opportuna. Se il dispari è un primo del tipo 4k+3 Alice perde, perchè il numero 4p lo può smistare solo come 2,2p 4,p 4p,1 e in tutti i casi viene un multiplo di 4 facendo vincere Bruno.

Ok, risolto Boh, per me era bellino