76. The Game

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

76. The Game

Messaggioda cip999 » 21/11/2016, 22:46

Facciamo ripartire la staffetta...

Ana ha trovato un intero $k \ge 2$! Decide quindi di sfidare l'amico (amica?) Banana al gioco The Game: all'inizio scrivono sulla lavagna un intero $n \ge k$; poi, iniziando da Ana, muovono a turno. Una mossa consiste nel cancellare il numero $m$ scritto sulla lavagna e scrivere al suo posto un intero $m'$ tale che:
    (i) $k \le m' < m$
   (ii) $(m, \: m') = 1$.
Perde chi non può più muovere.
Diciamo che un intero $n \ge k$ è anico se Ana ha una strategia vincente quando il numero iniziale è $n$, bananico altrimenti.
Si considerino due interi $n_1, \: n_2 \ge k$ con la proprietà che ogni primo $p \le k$ divide $n_1$ se e solo se divide $n_2$. Si mostri che $n_1$ e $n_2$ sono o entrambi anici o entrambi bananici.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: 76. The Game

Messaggioda Veritasium » 02/12/2016, 18:33

Testo nascosto:
Premessa ovvia: banalmente il gioco finisce perchè a ogni mossa il numero scritto diminuisce, quindi ogni numero $\ge k$ è univocamente anico o bananico.

Lemma: Sia [tex]k \ge 2[/tex] un intero positivo e siano $p_1, ..., p_s (s \ge 1)$ primi $\le k.$ Sia $\upsilon$ il più piccolo intero $\ge k$ tale che i primi $\le k$ che compaiono nella sua fattorizzazione sono tutti e soli i $p_i.$ Allora nella fattorizzazione di $\upsilon$ compaiono tutti e soli i $p_i$ (ovvero non esiste $q > k$ primo tale che $q \mid \upsilon$).
Dimostrazione: la tesi del lemma è equivalente a $\upsilon = \prod_{i = 1}^{s} p_i^{\alpha_i}$ per opportuni $\alpha_i \ge 1$. Se $\prod_{i = 1}^{s} p_i \ge k$ la tesi è ovvia, quindi supponiamo che questo prodotto sia $< k$.
Supponiamo che il lemma sia falso, ovvero che esista $q > k$ primo tale che $q \mid \upsilon \Longrightarrow \upsilon > k\prod_{i = 1}^{s} p_i$. Sia $(x_1, ..., x_n) = (\lambda_1, ..., \lambda_n)$ la $n-$upla per cui si ottiene il minimo positivo di $y = k - \prod_{i = 1}^{s} p_i^{x_i}$ e sia $M = \prod_{i = 1}^{s} p_i^{\lambda_i}$ e sia $P = \prod_{i = 1}^{s} p_i.$ Allora preso uno qualsiasi dei $p_i,$ sia esso $p_j,$ vale $\upsilon' = Mp_j > k$ ma anche $\upsilon' = Mp_j \le MP < kP < \upsilon,$ assurdo perchè $\upsilon$ non sarebbe il minimo. Il lemma è dimostrato.

Back to the main problem: per ogni $x \ge k$ sia $\upsilon(x)$ il più piccolo intero positivo $\ge k$ tale che $p \mid x \iff p \mid \upsilon(x) \ \forall \ p \le k.$
Notiamo che, per il lemma, l'insieme dei primi $p$ che dividono $\upsilon(n)$ è coincidente con l'insieme dei primi $p \le k$ che dividono $n.$ $(1)$
Mostriamo che, per ogni $n \ge k,$ $n$ e $\upsilon(n)$ sono entrambi anici o entrambi bananici, il che banalmente implica la tesi visto che se $n$ e $n'$ sono tali che $p \mid n \iff p \mid n' \ \forall \ p \le k$ allora $\upsilon(n) = \upsilon(n')$ (perchè, per come è definito, $\upsilon(x)$ dipende unicamente dai fattori primi $\le k$).

Per comodità, diciamo che, fissato $k,$ un intero $m$ è vincente se il giocatore che si trova a fare una mossa con $m$ scritto alla lavagna ha una strategia vincente, perdente altrimenti. Ne consegue che un intero è vincente se e solo se è anico e perdente se e solo se è bananico. Definiamo l'essere vincente o perdente di un numero il suo stato.
Procediamo per induzione forte sulla proposizione per ogni $n \ge k, n$ e $\upsilon(n)$ hanno il medesimo stato.
Per $k$ è ovvio visto che $k = \upsilon(k)$.
Supponiamo ora di averlo dimostrato per $k, ..., n - 1$ e dimostriamolo per $n.$
Se $\upsilon(n)$ è vincente, allora esiste $k \le l < \upsilon(n)$ tale che $(\upsilon(n), l) = 1$ e $l$ è perdente. Essendo $(\upsilon(n), l) = 1,$ per $(1)$ segue $(\upsilon(n), \upsilon(l)) = 1$ e quindi $(n, \upsilon(l)) = 1$ sempre perchè per $(1)$ tutti i primi che dividono $\upsilon(l)$ sono $\le k$ ed essendo che $(\upsilon(n), \upsilon(l)) = 1$ nessuno di questi divide $n,$ visto che tutti quelli che lo dividono dividono anche $\upsilon(n).$ Ma inoltre $\upsilon(l) \le l < \upsilon(n) \le n$ da cui la mossa che consiste nel cancellare $n$ e scrivere $\upsilon(l)$ è giocabile, ed essendo che $l$ è perdente lo è per ipotesi induttiva anche $\upsilon(l),$ da cui $n$ è vincente.
Se $\upsilon(n)$ è perdente, tutti gli $k \le y < \upsilon(n) : y = \upsilon(m) \wedge (y, \upsilon(n)) = 1$ per qualche $m$ sono vincenti, perchè se uno ($y_0$) fosse perdente la mossa che consiste nel cancellare $\upsilon(n)$ e scrivere $y_0$ sarebbe giocabile e quindi $\upsilon(n)$ sarebbe vincente. Supponiamo ora per assurdo che $n$ sia vincente; allora esiste $k \le N < n, (N, n) = 1$ perdente. Distinguiamo $2$ casi:

Caso 1: $\upsilon(N) < \upsilon(n).$
Per il passo induttivo $\upsilon(N)$ è perdente, ma vale anche $(\upsilon(N), \upsilon(n)) = 1$ poichè altrimenti per $(1)$ c'è $p \le k$ che divide entrambe, ma allora dividerebbe anche sia $n$ che $N$, assurdo. Da cui la mossa che consiste nel cancellare $\upsilon(n)$ e scrivere $\upsilon(N)$ è giocabile ed essendo $\upsilon(N)$ perdente, $\upsilon(n)$ è vincente, contraddicendo le ipotesi.

Caso 2: $\upsilon(N) > \upsilon(n)$ (chiaramente non può valere l'uguaglianza poichè $n$ e $N$ sono coprimi).
Essendo sempre $(\upsilon(n), \upsilon(N)) = 1,$ la mossa che consiste nel cancellare $\upsilon(N)$ e scrivere $\upsilon(n)$ è giocabile, ed essendo $\upsilon(n)$ perdente per quanto supposto, $\upsilon(N)$ è vincente, il che è assurdo per il passo induttivo visto che si era posto $N$ perdente.

Questo completa il passo induttivo e la proposizione dimostrata, per quanto visto prima, implica la tesi del problema.
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: 76. The Game

Messaggioda cip999 » 03/12/2016, 16:58

Bene!
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti