Problema tanto interessante quanto incomprensibile XD

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 17:07

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
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.

Avatar utente
auron95
Messaggi: 232
Iscritto il: 08 lug 2012, 12:20

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da auron95 » 28 ago 2012, 18:10

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.... :oops:
This is it. This is your story. It all begins here.

Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 18:11

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

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.

Avatar utente
Drago96
Messaggi: 1145
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Drago96 » 28 ago 2012, 18:14

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)?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 18:14

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.

Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 18:15

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.

Avatar utente
auron95
Messaggi: 232
Iscritto il: 08 lug 2012, 12:20

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da auron95 » 28 ago 2012, 18:37

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$).
This is it. This is your story. It all begins here.

Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 18:40

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 :)
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da xXStephXx » 28 ago 2012, 18:50

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.

Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Problema tanto interessante quanto incomprensibile XD

Messaggio da Iceman93 » 28 ago 2012, 18:51

Ok, risolto :) Boh, per me era bellino :D
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.

Rispondi