Cesenatico 2012 6

[Omar931]

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.

[EISguys]

Provo a rispondere

Prima la soluzione poi il ragionamento. Le coppie di numeri interi $(a,b)$ che soddisfano i requisiti sono tutte quelle per cui
$a!=b$
e
$1<=b<=2*a$

Quindi, solo per citare le prime:
$(1,2)$
$(2,1), (2,3), (2,4)$
$(3,1), (3,2), (3,4), (3,5), (3,6)$
...


Ecco come ho ragionato.
Cerco di dimostrare (contrariamente a quanto richiesto) che non esistono coppie di numeri $(a,b)$ che soddisfano le richieste. Siccome nel testo c'è la congiunzione "o", significa che per negare la condizione, devo poter negare contemporaneamente entrambe le affermazioni. Quindi dovrò dimostrare che se per l'intero a non viene soddisfatta la condizione, non esiste nessun b che soddisfi le condizioni.

Cominciamo semplicemente dal caso $a=1$.
Affiché non ci siano numeri interi dello stesso colori la cui differenza è uguale a 1, significa che non possono esserci numeri adiacenti di quel colore.
Quindi i numeri interi potranno essere colorati in questo modo, per esempio:
$...A B B B A B A B B A B B B B B B B B A...$
ma non in questo modo $...B A A B...$

Un altro modo per dire la stessa cosa è che ogni numero colorato di A, deve essere preceduto e succeduto da un numero colorato B. Questo significa che la "catena degli interi" è formata da tanti pezzetti del tipo
$...B A B...$
legati, al più, da catene di sole $B$.
Ma se la struttura è di questo tipo, si vede che, nell'elemento di catena che è sicuramente presente (avendo richiesto $a!=1$) $...B A B...$, esiste sempre una coppia di numeri B, tali che la loro differenza è 2.

Quindi la coppia (1,2) soddisfa alle richieste del quesito, perché se non fosse vero che non vengono soddisfatte le richieste per l'1, lo saranno per forza per il 2. Se invece saranno soddisfatte per l'1, la coppia sarà già "valida" senza dover fare ulteriori considerazioni sul 2.
Non possiamo dire altro perchè non sappiamo a priori quanti numeri di colore B si interporranno tra un segmento e l'altro.

Analogamente si può pensare per il caso $a!=2$.
Stavolta diciamo che i numeri di colore A potranno essere adiacenti o separati tra loro da più di 1 numero B. I singoli frammenti che possono comporre allora la catena di interi sono del tipo:

$...B B A B B...$
oppure
$...B B A A B B...$

In tal caso sarà sempre possibile trovare 2 interi di colore B la cui differenza è
- 1 (ci sono sempre due B adiacenti)
- 3 (ci sono sempre due B distanti 3 numeri)
- 4 (ci sono sempre due B distanti 4 numeri)
Non posso chiedere di più perchè la catena più piccola $...B B A B B...$ è composta al più da 5 elementi.

Generalizzando al caso $a!=n$, i frammenti possibili di catena saranno del tipo:
[tex]... \underbrace{B..B} A \underbrace{B..B} ...[/tex]
$.....n.....n$

[tex]... \underbrace{B..B} A A \underbrace{B..B} ...[/tex]
$.....n.......n$

[...etc...]

[tex]... \underbrace{B..B} \underbrace{A..A} \underbrace{B..B} ...[/tex]
$.....n....n...n$


Da cui si vede che utilizzando solo i primi $n$ numeri $B$ di ogni catena è possibile ottenere tutti i numeri $b$ tra $1$ e $n-1$.
Sfruttando poi la presenza delle $A$ si posso ottenere tutte le possibili altre differenze (per esempio per ottenere $b=n+1$ dalla prima stringa basta fare la differenza tra il primo intero $B$ dopo la $A$ e il primo intero $B$ della stringa, mentre per ottenerlo dall'ultima stringa basta fare la differenza tra il primo $B$ subito dopo le $A$ e quello subito prima le $A$).
Il massimo $b$ che si può ottenere è dettato dalla stringa più corta (con una sola $A$) ed è uguale alla differenza tra l'ultimo numero B e il primo B della stringa, cioè $2*n$.
Sempre a causa della presenza delle $A$ è evidente che l'unico $b$ che non si può ottenere è per $b=n$, cioè per $b=a$.

Spero sia tutto chiaro...e giusto!!
ciao ciao

[Quinzio]

"Omar93":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.

Intanto farei una considerazione: o la sequenza è periodica o non lo è.
Se non è periodica, ad esempio, 1A 2B 3A 4B ecc. oppure che segue l'andamento delle cifre di $\pi$, cioè 3A 1B 4A ecc. mi viene da dire che prima o poi trovo sempre la differenza cercata.
Se esiste un pattern ripetitivo, allora suppongo che le sequenze più esigenti siano del tipo xA xB xA xB ecc. con x numero intero. In questo caso se ad es. x=5 non riesco a trovare due caratteri distanti 5, 15, 25, ecc., se x=6 non trovo due A o B distanti 6, 18, 30, ecc.
Se x=1 non trovo due A o B distanti 1, 3, 5, 7,... cioè i dispari. Se x=2 non ne trovo due distanti 2, 6, 10, 14,...
Quindi direi la soluzione è: tutte le coppie di un pari e un dispari.

Ci ho preso ???

[EISguys]

mm..la mia soluzione è incompleta!
L'altra sera ho dimostrato che esiste anche la coppia (1,4) contrariamente a quanto avevo affermato in precedenza...appena ho un po' più di tempo ci penso meglio.
Comunque il ragionamento fatto prima resta valido. Quindi direi che confermo le coppie di numeri già dette, ma ce ne sono di più..ci penserò..

byeeee

[Quinzio]

Omar.... c'è una soluzione certa a questo quesito ?

[giannirecanati]

Considero \(\displaystyle (a,b) \) una coppia che non funziona, cioé per cui esiste una colorazione. Prendo \(\displaystyle x>b \) un numero colorato di \(\displaystyle A \). allora \(\displaystyle x+a \) è necessariamente \(\displaystyle B \), \(\displaystyle x+a+b \) è necessariamente \(\displaystyle A \) e \(\displaystyle x+a+b−a \) è necessariamente \(\displaystyle B \); in particolare sia \(\displaystyle x+a \) che \(\displaystyle x+b \) sono colorati di \(\displaystyle B \). Ragionando in modo simile (ma scambiando \(\displaystyle A \) con \(\displaystyle B \) e partendo da \(\displaystyle y=x+a \) o \(\displaystyle y=x+b \) ottengo che sia \(\displaystyle x+2a \) che \(\displaystyle x+2b \) sono colorati di \(\displaystyle A \). In questo modo è facile provare induttivamente che il colore di \(\displaystyle x+ja \) (rispettivamente \(\displaystyle x+kb \)) è \(\displaystyle A \) se \(\displaystyle j \)(rispettivamente \(\displaystyle k \)) è pari ed è \(\displaystyle B \) altrimenti. Ora quando queste due successioni si incontrano per la prima volta? Ovviamente nel punto \(\displaystyle x+mcm(a,b) \) e ora è facile concludere che questo NON genera un assurdo solo se \(\displaystyle a \)e \(\displaystyle b \) sono divisi dalla stessa potenza di \(\displaystyle 2 \). Basta ora esibire un esempio di colorazione che funziona per le coppie del tipo \(\displaystyle (2k(2n+1),2k(2m+1)) \).