Cesenatico 2012 problema 6

[relue123]

Determinare tutte le coppie {a, b} di interi positivi con la seguente proprietà: comunque si colorino gli interi positivi con due colori A e B, esistono sempre due interi positivi del colore A con differenza a o due interi positivi del colore B con differenza b.La mia perplessità è che non capisco come si arrivi alla forma di tale numeri in quanto nella soluzione ufficiale si dimostra che solo tali numeri soddisfano la proprietà ma non si da un modo su come trovarli.

[Tess]

Anche se può essere una tua perplessità il fatto che non si dica come costruirli, se il testo del problema ti chiede dimostrare che esistono... non vuol dire che è necessario esibire una costruzione! Anzi, in alcuni problemi, in generale, non è proprio possibile dare una costruzione!
In questo problema non è semplice "dare una forma" (credo tu intenda una cosa tipo una funzione algebrica, polinomiale, del tipo $ A=f(a,b,altri_parametri) $ ) perché dovresti fornirla per ogni possibile 2-colorazione dei naturali, e queste sono davvero tante. Allora molte volte si usa approcci meno diretti per dimostrare l'esistenza di qualche oggetto (per esempio supporre per assurdo la sua non-esistenza...).

[relue123]

allora come procederesti tu?

[jordan]

La mia perplessità è che non capisco come si arrivi alla forma di tale numeri in quanto nella soluzione ufficiale si dimostra che solo tali numeri soddisfano la proprietà ma non si da un modo su come trovarli.

Mi sono appena letto problema (e soluzione insieme, data l'ora preferirei una mezz'ora in piu' di sonno ): l'idea della soluzione è

"Vogliamo mostrare che $(a,b)$ è soluzione se e solo se $\upsilon_2(a) \neq \upsilon_2(b)$. Come ogni dimostrazione se e solo se è composta di due parti:

• $\bullet$ Se $\upsilon_2(a)=\upsilon_2(b)$ allora esiste un controesempio, e questo è sufficiente per mostrare la parte solo se ;
  $\bullet$ Se $\upsilon_2(a)\neq \upsilon_2(b)$ non è possibile costruire controesempi, e questo è sufficiente per mostrare la parte se. "

Ora, oltre l'idea di base, mi pare sia spiegata molto bene (apparte qualche problemino con la compilazione $\LaTeX$ ): era questo il problema?

[relue123]

Cosa intendi con v2(a)?Con questi tipi di problemi sono una frana.

[relue123]

Si intende la proposizione logica O che è falsa se entrambe sono vere cioè quando sono uguali in questo caso i numeri a e b?

[ma_go]

no, dire $v_2(a) = v_2(b)$ è solo un modo compatto di dire che se $2^k$ è la più grande potenza di 2 che divide $a$, è anche la più grande potenza di 2 che divide $b$. ovvero, $2^k$ divide sia $a$ sia $b$, ma $2^{k+1}$ non divide nessuno dei due. (per inciso, questo intero $k$ si chiama valutazione diadica [o 2-adica] di $a$).

viceversa, $v_2(a) \neq v_2(b)$ vuol dire che esiste un intero $k$ tale che $2^k$ divide sia $a$ sia $b$, ma $2^{k+1}$ divide solo uno dei due.

[relue123]

grazie per la delucidazione sulla simbologia.Nel momento che inizio a ragionarci,non mi vengono idee a proposito.Se qualcuno potesse scrivere le proprie idee al riguardo,li sarei grato.

[ma_go]

data la risposta di Tess, non mi (ci?) è chiaro cosa non ti sia chiaro.

[relue123]

come iniziereste a risolvere il problema perche anche con l input di tess e di jordan sono bloccato

[jordan]

come iniziereste a risolvere il problema perche anche con l input di tess e di jordan sono bloccato

Inziare provando a vedere che succede con a e b piccoli e cercare di "indovinare" la risposta; quando sei abbastanza sicuro (mettiamola così, "a intuito") che quella puo' essere definitivamente la risposta corretta, provare a mostrare le due parti del "se e solo se"..

[relue123]

grazie jordan