Problema tanto interessante quanto incomprensibile XD
Problema tanto interessante quanto incomprensibile XD
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
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
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Problema tanto interessante quanto incomprensibile XD
E' Alice che sceglie n e k giusto? Perchè leggendo il testo del problema vengono mooolti dubbi....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)
![Embarassed :oops:](./images/smilies/icon_redface.gif)
This is it. This is your story. It all begins here.
Re: Problema tanto interessante quanto incomprensibile XD
"Alice può dividere a in due fattori n e k"
Si, è lei XD
Per altri dubbi, chiedi pure...
Si, è lei XD
Per altri dubbi, chiedi pure...
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Problema tanto interessante quanto incomprensibile XD
"Lui" è un typo, volevi srivere "lei" (Alice)?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)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Problema tanto interessante quanto incomprensibile XD
Ah scusami, ho scritto lui al posto di lei, non l'avevo notato XD Ok si sceglie Alice...
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Problema tanto interessante quanto incomprensibile XD
Chiedo venia XD E comunque magari aveva deciso di diventare un "lui" u.u
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Problema tanto interessante quanto incomprensibile XD
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$).
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$).
This is it. This is your story. It all begins here.
Re: Problema tanto interessante quanto incomprensibile XD
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 ioauron95 ha scritto: Se quindi Bruno prende un primo congruo a -1 modulo 4 è sicuro di vincere.
![Smile :)](./images/smilies/icon_smile.gif)
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Problema tanto interessante quanto incomprensibile XD
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.
Ultima modifica di xXStephXx il 28 ago 2012, 18:59, modificato 2 volte in totale.
Re: Problema tanto interessante quanto incomprensibile XD
Ok, risolto
Boh, per me era bellino ![Very Happy :D](./images/smilies/icon_biggrin.gif)
![Smile :)](./images/smilies/icon_smile.gif)
![Very Happy :D](./images/smilies/icon_biggrin.gif)
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.