Stile dimostrativo - Teoria dei Numeri

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Cesenatico 2006 1:
Rosa e Savino fanno il seguente gioco con le carte napoletane( 40 carte numerate da 1 a 10, 4 semi diversi): inizialmente si dividono le 40 carte(20 per ciascuno), poi a turno appoggiano sul tavolo una carta. Quando alcune delle carte sul tavolo hanno dei valori la cui somma è 15, allora queste carte vengono eliminate dal gioco.Alla fine della partita sono rimaste due carte in mano a Savino (3 e 5), una carta sul tavolo (9), ed una in mano a Rosa. Qual è il valore di codesta carta?

Soluzione:
Testo nascosto:
La somma di tutte le carte è $4 \cdot \dfrac {10 \cdot 11}{2}= 220 \equiv 10 \pmod {15}$ , allora, detta $x$ la carta incognita, deve valere

$5+3+9+x+15k \equiv 10 \pmod {15} \iff x \equiv 8 \pmod {15}$ , quindi $x=8$ . (N.B. Una tale soluzione è accettabile perchè $0\leq x \leq 10$)
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Cesenatico 2010 1

Ad un test di matematica partecipano $N < 40$ persone. La sufficienza è fissata a $65$. I risultati del test sono i seguenti: la media di tutti i partecipanti è $66$, quella dei promossi $71$ e quella dei bocciati $56$. Tuttavia, a causa di un errore nella formulazione di un quesito, tutti i punteggi vengono aumentati di $5$. A questo punto la media dei promossi diviene $75$ e quella dei non promossi $59$.

(a) Trovare tutti i possibili valori di $N$.

(b) Trovare tutti i possibili valori di $N$ nel caso in cui, dopo l’aumento, la media dei promossi fosse diventata $79$ e quella dei non promossi $47$.

Soluzione:
Testo nascosto:
Prima di iniziare la dimostrazione, è fondamentale la seguente osservazione: sia $M$ la media aritmetica di $a_1,a_2,...,a_n$ voti . Allora se ciascun voto è aumentato di una stessa quantità intera $k$ , anche la media aritmetica aumenterà della stessa quantità $k$ ( basta vedere che alla somma totale si aggiunge $n \cdot k$ .

a) Siano $P,B$ rispettivamente il numero di promossi e bocciati prima dell'errore. Chiaramente $P+B=N$ . Dal testo è possibile impostare la seguente equazione:

$ \dfrac {71P+56B}{N}=66 \iff \dfrac {71P+56B}{P+B}=66 \iff 71P+56B=66P+66B \iff P=2B \ \ (\star)$

Sia ora $Y$ il numero di studenti con punteggio tra $60$ e $64$ che sono stati promossi dopo l'errore. Inoltre, con le stesse notazioni precedenti, siano $P',B'$ i rispettivi studenti .Chiaramente $P'=P+Y , \ \ B'=B-Y$ . Per l'osservazione iniziale, la media aritmetica dei voti dopo l'errore è $66+5=71$ . Possiamo quindi impostare un'equazione simile alla precedente:


$ \dfrac {75P'+59B'}{N}=71 \iff \dfrac {75P+75Y+59B-59Y}{P+B}=71 \iff 75P+59B+16Y=71P+71B \iff 4Y=B$ dove si è usata la $(\star)$

Allora , essendo $B= \dfrac {N}{3} \leq 13 $ gli unici $B$ che vanno bene sono $B=4,8,12$ . ed i valori di $N=12,24,36$

b) Impostiamo una equazione come nella tesi a) cambiando solamente i coefficienti:

$ \dfrac {79P'+47B'}{N}=71 \iff \dfrac {79P+79Y+47B-47Y}{P+B}=71 \iff 79P+47B+32Y=71P+71B \iff 4Y=B$ dove si è usata la $(\star)$

Abbiamo ottenuto la stessa equazione precedente, sarà possibile? Io non credo. Infatti sostituendo i rispettivi valori di $Y$ trovati, ovvero $Y=1,2,3$ rispettivamente, si ottiene che la media dei ragazzi $Y$ è $<60$ e quindi una tale situazione non può sussistere.
carlotheboss
Messaggi: 65
Iscritto il: 17/02/2016, 16:12

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da carlotheboss »

Rho33 ha scritto: Allora , essendo $B= \dfrac {N}{3} \leq 13 $ gli unici $B$ che vanno bene sono $B=4,8,12$ . ed i valori di $N=12,24,36$
Qui in teoria trovi che non puoi avere più di $3$ valori per $N$, però nessuno ti dice che esistono davvero delle configurazioni valide per quei 3 $N$, dovresti mostrarle (o perlomeno il pdf di Cesenatico, nelle soluzioni, mostra anche delle combinazioni valide per quei 3 $N$) :D
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Oh grazie, non ci avevo pensato!

Spagna 2001 4:

Un quadrato $3 \times 3$ contiene le cifre da $1$ a $9$ (come nei riquadri di un sudoku): si considerino i numeri di tre cifre che si possono leggere da sinistra verso destra, o dall’alto verso il basso. La loro somma può essere pari a $2009$?

Soluzione:
Testo nascosto:
Siano $a,b,c,d,e,f,g,h,i$ le cifre contenute nelle caselle, in quest'ordine ( cioè $a$ nella casella $c_{1,1}$ , b nella casella $c_{1,2}$ ecc..

Chiaramente i numeri di tre cifre che si formano saranno: $(100a+10b+c),(100d+10e+f),(100g+10h+i),(100a+10d+g),(100b+10e+h),(100c+10f+i)$ .

Sommandoli si ottiene che deve valere:

$200a+110b+101c+110d+20e+11f+101g+11h+2i=2009 $ Ora guardando modulo $3$ si ottiene che deve valere:

$2(a+b+c+d+e+f+g+h+i) \equiv 2 \pmod 3 \iff a+b+c+d+e+f+g+h+i \equiv 1 \pmod 3 $

Ma la somma delle cifre è : $ \dfrac {9 \cdot 10}{2}=45 \equiv 0 \pmod 3 \rightarrow $ assurdo !
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Simulazione 2013 (tris)

Trovare tutte le terne $(x,y,z)$ di interi non negativi che risolvano l'equazione :

$\dfrac {1}{x+2}+ \dfrac {1}{y+2}= \dfrac {1}{2}+ \dfrac {1}{z+2}$

Soluzione:
Testo nascosto:
Bene, come tutte le equazioni diofantee, lo risolviamo con conti e disuguaglianze :lol: Svolgendo tutti i conti e semplificando ciò che si deve semplificare si ottiene ( non li sto riportando perchè non è così utile ai fini del problema, ma in gara ovviamente lo farei!)

$4z=zxy+4x+4y+4xy$

Ora notiamo che , essendo non negativi, la terna $(0,0,0)$ ovviamente soddisfa. Bene, l'equazione è simmetrica in $x$ e $y$ quindi tutte le soluzioni che troverò lavorando con la $x$ avranno le rispettive simmetriche in $y$.

Osserviamo che, ponendo $x=0, \ \ y=z$ si ottiene un 'identità : $ 4z=4z$ da cui tutte le soluzioni nella forma $ (0,a,a)$ e le simmetriche $(a,0,a)$ soddisfano la relazione con $a \in \mathbb{N}$.

Detto ciò, supponendo che $x,y,z>0$ per come è impostata la relazione, il LHS è maggiore di ognuno degli addendi al RHS da cui:

$\bullet 4z>4x \rightarrow \ \ z>x$
$\bullet 4z>4y \rightarrow \ \ z>y$
$\bullet 4z>4xy \rightarrow \ \ z>xy$
$\bullet 4z>xyz \rightarrow \ \ 4>xy$ $(\star)$

Per la $(\star)$ distinguiamo pochi semplici casi per ottenenere:

$\bullet x=1 \ \ y=1 \rightarrow z=4$ quindi $(1,1,4)$ soddisfa.
$\bullet x=1 \ \ y=2 \rightarrow z=10$ quindi $(1,2,10)$ soddisfa così come la simmetrica $(2,1,10)$.
$\bullet x=1 \ \ y=3 \rightarrow z=28$ quindi $(1,3,28)$ soddisfa così come la simmetrica $(3,1,28)$.
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Simulazione 2014 2 generalizzato

Dato un primo $p \equiv 3 \pmod 4 $ , trovare tutte le soluzioni intere della seguente equazione diofantea :

$a^2+b^2=p(c^2+d^2)$


Soluzione:
Testo nascosto:
Iniziamo subito con un bel lemmino:

Lemmino: Dato un primo $p \equiv 3 \pmod 4$ , se $a$ è residuo quadratico modulo $p$, allora $-a$ non è residuo quadratico modulo $p$

Dimostrazione : Supponiamo per assurdo che la tesi sia falsa, allora deve valere:

$ x^2 \equiv a \pmod p \ \ $
$y^2 \equiv -a \pmod p \ \ $

Bene sommiamo le due relazioni ottenendo che:

$x^2 \equiv -y^2 \pmod p \ \ (\star) $

Sia ora $b= \dfrac {p-1}{2}= \dfrac {4k+3-1}{2}=2k+1 $ quindi il nostro $b$ è dispari. Eleviamo ambo i membri della $(\star)$ alla $b$ ( posso farlo per una nota proprietà delle congruenze) , ottenendo:

$ x^{p-1} \equiv (-1)^{\frac {p-1}{2}}y^{p-1} \pmod p \iff x^{p-1} \equiv -y^{p-1} \pmod p $ .

Ma ora, per il Piccolo teorema di Fermat deve valere:

$1 \equiv -1 \pmod p \rightarrow $ assurdo!


Ora, visto che va di moda...

BACK TO THE MAIN PROBLEM

Osserviamo subito che la quaterna $(0,0,0,0)$ è soluzione. Dimostriamo che non ce ne sono altre.

Dato che $p$ deve dividere il LHS della nostra equazione, applicando il nostro lemmino , si ottiene che $p \mid a$ e $p \mid b$ allora posso porre $ a=p \cdot k$ e $b=p \cdot h$ e sostituendo si ottiene:

$p^2k^2+p^2h^2= p(c^2+d^2) \iff p(k^2+h^2)=c^2+d^2$

Ci siamo ricondotti alla stessa equazione di partenza, chiaramente posso iterare il procedimento , allora per discesa infinita raggiungiamo l'assurdo e quindi $(0,0,0,0)$ è l'unica soluzione.
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Cesenatico 2011 2

Una sequenza di interi positivi $a_1,a_2,...,a_n$ è detta "scaletta di lunghezza $n$" se è costituita da $n$ interi positivi consecutivi in ordine crescente.

a) Dimostrare che per ogni intero positivo $n$ esistono $2$ "scalette" prive di elementi in comune e tali che $(a_i,b_i)=1 $ $\forall \ \ 1\leq i \leq n$

b) Dimostrare che per ogni intero positivo $n$ esistono $2$ "scalette" prive di elementi in comune e tali che $(a_i,b_i)>1 $ $\forall \ \ 1\leq i \leq n$

Soluzione:
Testo nascosto:
Problema molto carino e molto facile con la seguente osservazione:


Osservazione facile: dati due interi positivi $a,b$ con $a>b$ vale che $(a,b)=(a-b,b)$

Applicando la nostra osservazione al problema si ottiene che, in generale:

$(a_1+i-1,b_1+i-1)=(a_1-b_1,b_1+i-1) \ \ \forall \ \ 1\leq i \leq n$

mentre in particolare $(a_1,b_1)=(a_1-b_1,b_1)$

Ovvero, il MCD tra due termini generali della sequenze dipende unicamente dalla scelta dei termini iniziali delle due sequenze (ma và :lol: )

Ora è facile trovare delle sequenze che soddisfino:

a)Sia $p$ un primo $ >> n$ . Allora ponendo $a_i=p+i$ e $b_i=i$ si ottiene che, per l'osservazione iniziale, $(a_i,b_i)=(p+i,i)=(p,i)=1 $ perchè $p$ è primo ed in più $>>n$.

b)Se scelgo $a_i=n!+i$ e $b_i=i$ , per l'osservazione iniziale si ottiene che $(a_i,b_i)=(n!+i,i)=(n!,i)=i $

P.S. Chiaramente il tutto si può estendere a scalette generiche, basta porre $a_i=p+b_i $ nella a) mentre $a_i=b_1b_2...b_n+b_i$ nella b)
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Bulgaria 2014 4

Trovare tutte le coppie di primi $p,q$ tali che :

$p^2 \mid q^3+1 \ \ \ \ $ e $\ \ \ \ q^2 \mid p^6-1$

Soluzione:
Testo nascosto:
Come tutti i problemi di questo tipo, lo risolviamo con divisibilità e disuguaglianze!

Innanzitutto notiamo le soluzioni banali $(2,3); (3,2)$ , bene ora possiamo supporre $p,q > 3$ .

$p^2 \mid q^3+1 \rightarrow p^2 \mid (q+1)(q^2-q+1)$ ma $(q^2-q+1,q+1)=(q^2-q+1-q-1,q+1)=(q^2-2q,q+1)=(q(q-2),q+1)=(q+1,q-2)=(3,q-2)=1,3$

Quindi $p^2 \mid q+1 $ oppure $p^2 \mid q^2-q+1$ ( $2$ casi)

$ q^2 \mid p^6-1 \rightarrow q^2 \mid (p^3+1)(p^3-1) $ ma $ (p^3+1,p^3-1)=(p^3-1,2)=2$

Quindi $q^2 \mid p^3+1 $ oppure $q^2 \mid p^3-1$ ( $2$ casi)

Non ci restano che trattare $4$ comodi casi:

$ \ \ \bullet p^2 \mid q+1 $ e $ q^3 \mid p^2+1 \rightarrow q^3-1 \leq p^2 \leq q+1 \rightarrow $ assurdo!

$ \ \ \bullet p^2 \mid q^2-q+1 $ e $ q^3 \mid p^2-1 \rightarrow q^3+1 \leq p^2 \leq q^2-q+1 \rightarrow $ assurdo!

$ \ \ \bullet p^2 \mid q+1 $ e $ q^3 \mid p^2-1 \rightarrow q^3+1 \leq p^2 \leq q+1 \rightarrow $ assurdo!

$ \ \ \bullet p^2 \mid q^2-q+1 $ e $ q^3 \mid p^2+1 \rightarrow q^3-1 \leq p^2 \leq q^2-q+1 \rightarrow $ assurdo!
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Determinare tutte le soluzioni intere dell'equazione:

$y^2=x^5-4 $

Soluzione:
Testo nascosto:
Bhe, che numeri ci sono in questa diofantea? $2,5,4$ che dire, li sommiamo? Ovvio che sì, $2+5+4=11$

Guardiamo l'equazione modulo $11$ ottenendo che:

$y^2 \equiv x^5+7 \pmod {11}$

Ora, i residui quadratici modulo $11$ sono ovviamente $\dfrac {p-1}{2} +1= 6\ \ \rightarrow \ \ 0,1,3,4,5,9$

Invece i residui quinti modulo $11$ sono esattamente $\dfrac {p-1}{(5,p-1)}+1=3 \ \ \rightarrow \ \ 0,1,-1$

Ma :

$\bullet \ \ 7+0=7 \ \ \rightarrow $ non è residuo quadratico !
$\bullet \ \ 7+1=8 \ \ \rightarrow $ non è residuo quadratico !
$\bullet \ \ 7-1=6 \ \ \rightarrow $ non è residuo quadratico !

Quindi, non ci sono soluzioni!
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Stile dimostrativo - Teoria dei Numeri

Messaggio da Rho33 »

Determinare tutte le soluzioni intere dell'equazione:

$y^2=x^3+16$

Soluzione:
Testo nascosto:
Vediamo le soluzioni banali $(0,4),(0,-4)$ , d'ora in poi $x,y \not = 0$.

$x^3=(y+4)(y-4) $ ma $(y+4,y-4)=(y+4-y+4,y-4)=(8,y-4)$ quindi distinguiamo in casi:

$\bullet \ \ y=2k+1 \rightarrow \ \ (8,y-4)=1 \iff (y+4)=a^3 , (y-4)=b^3 \iff a^3-b^3=8 \rightarrow $ assurdo per Zsigmondy ( in alternativa bisogna fare i casi molto molto noiosi)

$\bullet \ \ y=2k \rightarrow \ \ x=2h \rightarrow 4 \mid y \rightarrow 4 \mid x$ Quindi posso porre $y=4y',x=4x'$ e sostituendo ottengo $y'^2=4x'^3+1 \iff 4x'^3= (y'+1)(y'-1)$ ma $(y'+1,y'-1)=(y'-1,2)=2 $ perchè $y'$ è pari . Allora entrambi i fattori sono il doppio di un cubo perfetto e ponendo $y'+1=2c^3, y'-1=2d^3 \iff c^3-d^3=1 \rightarrow $ assurdo per Zsigmondy ( in alternativa bisgna fare i casi molto molto noiosi)
Ultima modifica di Rho33 il 01/04/2016, 17:04, modificato 1 volta in totale.
Rispondi