generalizzazione di un vecchio Balkan

[mattilgale]

allora

presi due interi positivi primi tra loro p e q, trovare tutti gli N interi positivi tali che dati due $ a,\ b\in \mathbb{Z} $ tali che a+b=N esattamente uno tra a e b è rappresentabile nella forma

$ \displaystyle mp+nq $ con $ m,\ n\in \mathbb{Z}^+ $

[HiTLeuLeR]

presi due interi positivi primi tra loro p e q, trovare tutti gli N interi positivi tali che dati due $ a,\ b\in \mathbb{Z} $ tali che a+b=N esattamente uno tra a e b è rappresentabile nella forma $ \displaystyle mp+nq $ con $ m,\ n\in \mathbb{Z}^+ $

Scusami, non capisco - è colpa mia. Si tratta di determinare i) ogni N > 0 naturale per cui esiste almeno una coppia (a,b) di interi (positivi, negativi o nulli) tale che a+b = N ed uno soltanto fra a e b è rappresentabile come combinazione lineare in $ \mathbb{Z}^+ $ di p e q? Oppure ii) ogni N > 0 naturale tale che, comunque scelta una coppia (a,b) di interi (positivi, negativi o nulli) per cui a+b = N, uno e uno solo fra a e b si rappresenta come combinazione lineare in $ \mathbb{Z}^+ $ di p e q?

[mattilgale]

ogni $ N\in \mathbb{Z} $ tale che per ogni coppia (a,b) di interi tali che a+b=N uno e uno solo di a e b si rappresenta come combinazione lineare di p e q in $ \mathbb{Z}^+ $

[HiTLeuLeR]

Appena qualche osservazione.

Siano $ \Gamma_{p,q} = \{mp + nq: m, n \in \mathbb{N}\} $ e $ \Gamma_{p,q}^+ = \{mp + nq: m, n \in \mathbb{N}^+\} $. Diciamo che un intero N > 0 soddisfa la proprietà P, e scriviamo in tal caso P(N), sse, comunque scelta una coppia (a,b) $ \in\mathbb{Z}^2 $ per cui a + b = N, risulta $ a \in \Gamma_{p,q}^+ $ e $ b \not\in \Gamma_{p,q}^+ $ oppure $ a \not\in \Gamma_{p,q}^+ $ e $ b \in \Gamma_{p,q}^+ $. Poniamo quindi $ \Lambda_{p,q} = \{N \in \mathbb{N}^+: P(N)\} $. Si tratta di fatto di descrivere in modo estensivo l'insieme $ \Lambda_{p,q} $. Per via del teorema di Sylvester, se $ a > pq - (p+q) $ è un intero, allora $ a \in \Gamma_{p,q} $. Dunque $ a \in \Gamma_{p,q}^+ $, se $ a > pq $. Ne viene che $ N \not\in \Lambda_{p,q} $, se N > 2pq + 2. Inoltre $ N $ è dispari, se $ N \in \Lambda_{p,q} $, perché altrimenti, posto a = b = N/2, nessuno o entrambi fra a e b appartengono a $ \Gamma_{p,q}^+ $. Infine $ N \ge 2(p+q) - 1 $, in quanto diversamente esistono a, b interi positivi entrambi < p+q tali che a + b = N, e allora $ a,b\not\in \Gamma_{p,q}^+ $, i.e. $ N \not\in \Lambda_{p,q} $. Da qui $ \Lambda_{p,q} \subseteq \{N \in 2\mathbb{N}+1: 2(p+q)-1 \le N \le 2pq+1\} $.

Sicuro, Mattilgale, che esista in generale una forma decente per descrivere com'è fatto l'insieme $ \Lambda_{p,q} $? Posso chiederti ancora qual è la traccia originale del Balkan che ti ha ispirato questa generalizzazione?

EDIT: vedi oltre.

[mattilgale]

ERA UNA CAZZATA (non è la prima trall'altro)

[HiTLeuLeR]

però mi ero scordato di dire che a e b devono essere distinti... sorry

Vabbè, grosso modo non c'è grande differenza! Solo che forse dovresti editare il post che contiene la formulazione del problema - non si sa mai... Per parte mia, vedo di ritoccare, alla luce dei nuovi elementi, il precedente intervento sul topic.

[HiTLeuLeR]

Conclusioni!

Perciò, in particolare $ \Lambda_{p,1} \subseteq $ {2p+1,2p+2}. Siano $ a,b\in\mathbb{Z} $ tali che $ a\ne b $ ed a+b = 2p+1 oppure a+b = 2p+2. Wlog, possiamo ammettere a > b. Allora necessariamente $ a \ge p+1 $ nel primo caso e $ a \ge p+2 $ nel secondo, per cui comunque $ b \le p $. Ne risulta in ambedue le circostanze $ a \in \Gamma_{p,q}^+ $ e $ b \not\in \Gamma_{p,q}^+ $, cosicché $ (2p+1), (2p+2) \in \Lambda_{p,1} $. Da qui e dal precedente, $ \Lambda_{p,1} = \{2p+1, 2p+2\} $, e per simmetria $ \Lambda_{1,q} = \{2q+1,2q+2\} $. Ammettiamo perciò d'ora in avanti $ \min(p,q) > 1 $. Fissato $ N \in \mathbb{N}^+ $, poniamo $ a = 3pq $ e $ b = N - a $, di modo che a+b = N. Visto quanto stabilito, se $ N \in \Lambda_{p,q} $, banalmente $ b \not\in\Gamma_{p,q}^+ $, perché b < 0. Dunque a forza $ a \in \Gamma_{p,q}^+ $, e quindi esistono m, n interi positivi tali che $ mp + nq = 3pq $. Tuttavia gcd(p,q) = 1, per cui $ m = m_0 p $ ed $ n = n_0 q $, per opportuni $ m_0, n_0 \in \mathbb{N}^+ $. Ne segue $ 3 = m_0 p + n_0 q \ge 4 $. Assurdo! Se pertanto p e q sono entrambi $ \ge 2 $, allora $ \Lambda_{p,q} = \emptyset $. Questo è quanto.

[mattilgale]

errore 1) (MIO!!!) devo confessare che EFFETTIVAMENTE mi sono sbagliato, il caso a=b=N/2 va considerato, pertanto N deve essere NECESSARIAMENTE DISPARI... sorry, l'uncio cambiamento è
$ \Lambda_{p,1}=\left\{2p+1\right\} $

errore2) $ 2q\cdot p+p\cdot q=3pq $ l'errore è qui

Ne segue $ 3 = m_0 p + n_0 q \ge 4. $

perché in realtà è solo la somma $ m_0+n_0 $ ad essere =3

[HiTLeuLeR]

Eh, vedo... Edito per la seconda volta la prima parte della soluzione che andavo proponendo, tenuto conto della tua ultima rettifica sulla rettifica già formulata... :S In quanto alle conclusioni, temo vadano del tutto riviste!

[mattilgale]

invito anche qualcun altro a cimentarsi con questo esercizio che a mio parere è molto istruttivo!!!

[mattilgale]

UP! ^^^

piccolo hint
considerate la classe di a e b mod p e tentate di ricavarne qualcosa

[what]

Allora...

(il caso in cui uno fra p,q è uguale a 1 è facile, ed è già stato risolto da hitleuler. suppongo quindi p,q>1)

innanzitutto dimostro che il massimo intero non rappresentabile come combinazione lineare "positiva" di p e q è pq.

1-pq non è scrivibile in quella forma
infatti se $ pq=mp+nq $ allora $ m\equiv 0 \pmod q \longrightarrow m\geq q \longrightarrow mp+nq>pq $ assurdo

2-ogni numero maggiore di pq è scrivibile in quella forma
i numeri $ p,2p,...,qp $ formano un sistema completo di residui modulo q (e sono tutti minori di pq+1), quindi aggiungendo ad ognuno di essi multipli di q si ottengono tutti i numeri maggiori di pq.

è inoltre evidente che il minimo intero scrivibile in quella forma è p+q.

------

ora mostriamo che se N dev'essere uguale a pq+p+q.
se $ N=pq+p+q+k $ (con k intero positivo) allora posso porre $ a=p+q, b=pq+k $, entrambi rappresentabili nella forma mp+nq.
Dunque $ N\leq pq+p+q $.

se $ N=pq+p+q-k $ (sempre con k positivo) allora pongo $ a=p+q-k, b=pq $, entrambi non rappresentabili nella forma mp+nq.
Quindi $ N \geq pq+p+q $.

Perciò l'unica possibilità è che sia $ N=pq+p+q $.

Ci resta da dimostrare che un tale N sia soluzione per ogni p,q.

Siano a,b interi tali che $ a+b=N=pq+p+q $.
Dimostriamo che non è possibile che sia a che b siano entrambi esprimibili come combinazione lineare positiva di p,q.
Infatti supponiamo per assurdo che esistano interi positivi $ m,n,r,s $ tali che $ a=mp+nq, b=rp+sq $.
Allora si avrebbe $ a+b=(m+r)p+(n+s)q=pq+p+q $$ \longrightarrow (m+r)p \equiv p \pmod q \longrightarrow m+r\equiv 1 \pmod q $
Quindi $ m+r \geq q+1\longrightarrow a+b\geq (q+1)p+2q $, assurdo.

Dimostriamo ora che non è possibile che nè a nè b siano entrambi esprimibili in quel modo.
Se uno fra (wlog) $ a\leq p+q-1 \longrightarrow b\geq pq+1 $ allora a non è scrivibile mentre b sì, quindi sono a posto.
Analogamente se $ a\geq pq+1 $ sono a posto, quindi mi resta da analizzare il caso $ p+q\leq a,b \leq pq $
Per il teorema di Bezout, posso scrivere $ a=mp+nq $ con m,n interi. Posso poi "aggiustarmi" m,n in modo tale da ottenere $ 1\leq m \leq q $ (infatti mi basta aggiungere e sottrarre pq).

Ora, se n è positivo sono a posto; altrimenti, si avrebbe $ b=N-a=pq+p+q-a=(q+1-m)p+(1-n)q $.
Per quanto detto prima, $ q+1-m \geq 1, 1-n\geq 1 $, e quindi b è scrivibile.

Ricapitolando, $ N=pq+p+q $ è l'unica soluzione.


ciao

[mattilgale]

finalmente risolto... non era impossibile...

posto la mia soluzione leggermente diversa...
che N può essere solo pq+p+q lo dimostro come what, poi osservo che a è rappresentabile nella forma mp+nq se e solo se

$ a\geq p+\omega_a\cdot q $ con $ \omega_a\equiv \frac{a}{q}\ (p) $ e $ 1\leq \omega_a\leq p $

ora se a è rappresentabile allora $ N-a\leq (p+1-\omega_a)q $ e poiché $ 1\leq p+1-\omega_a\leq p $allora $ p+1-\omega_a=\omega_{N-a} $

quindi $ b\leq \omega_b q $ quindi b non è nella forma mp+nq

formalizzandola meglio è finita