Divisibile per 1000

[xXStephXx]

Siano $a_1, a_2, ..., a_{10}$ dei numeri interi. Dimostrare che è possibile trovare dei numeri $x_1, x_2, ..., x_{10} $ appartenenti all' insieme ${−1,0,1}$ tali che $a_1x_1+a_2x_2+...+a_{10}x_{10}$ sia divisibile per $1000$.

E' facile eh

[j18eos]

Ci sono due cose non chiare: i numeri \(\displaystyle a_i\) sono interi e "basta"?

Ecco la seconda cosa!

Va bene questa soluzione:
\[
x_1=...=x_{10}=0
\]
oppure essendo banale è da escludere?

[xXStephXx]

Si hai ragione xD

Sono interi e basta (ma che cambia qui?) e i coefficienti non possono essere tutti nulli.

[j18eos]

"xXStephXx":Si hai ragione xD...

Ogni volta che intervengo, mi sorridi sempre a trentadue (\(\displaystyle32\)) denti ed ad occhi chiusi!, non credo che tu sia santa Teresa di Lisieux ed io una consorella antipatica alla quale la santa sorrideva sempre (click)... Però, come disse una consorella (antipatica):"Di grazia sorella (Teresa, NdT): come mai mi sorride sempre ogni volta che mi vede?"

"xXStephXx":...Sono interi e basta (ma che cambia qui?)...

Se prendo:
\[
a_1=...=a_{10}=7
\]
non trovo alcuna soluzione!

[Pachisi]

@j18eos

Basta scegliere \(\displaystyle x_1=...=x_{10}=0\)

Provo a dare una dimostrazione:

Siano \(\displaystyle n, 0\leq n\leq10\), degli \(\displaystyle x_1,...,x_{10}\) nulli, siano \(\displaystyle j, 0\leq j\leq10\), uguali a \(\displaystyle 1\) e siano \(\displaystyle i, 0 \leq i\leq10\), uguali a \(\displaystyle -1\). Inoltre, sia \(\displaystyle a_j\) la somma dei coefficienti delle \(\displaystyle x_j\) con \(\displaystyle x_j=1\) e, in modo analogo si definisce \(\displaystyle a_i\).
Abbiamo

\(\displaystyle a_j-a_i=1000k, k \in \mathbb{Z}\), ed ovviamente si posso trovare tali numeri.

Sono quasi sicuro che sia sbagliata, e scusate per la confusione, ma non sono abituato a scrivere dimostrazioni.

[giammaria2]

"j18eos":Se prendo:
\[
a_1=...=a_{10}=7
\]
non trovo alcuna soluzione!

Neanche $x_i=(-1)^i$? E comunque lascia stare le sante: c'è il rischio che si offendano e chiedano ed ottengano qualche castigo per te.

[xXStephXx]

Pachisi: non ho capito niente purtroppo. Però mi pare sbagliata.

Giammaria: ok va bene quel modo xD

J8eos: xD è la risata più semplice ed è di default xD
E poi ti sfido a trovare un mio messaggio senza xD.

[Pachisi]

xXStephXx: Provo a dare un esempio

Siano \(\displaystyle 5\) degli \(\displaystyle x_k\) nulli, siano \(\displaystyle 3\) degli \(\displaystyle x_k\) uguali a \(\displaystyle 1\) e siano \(\displaystyle 2\) degli \(\displaystyle x_k\) uguali a \(\displaystyle -1\).

Abbiamo

\(\displaystyle x_1=x_2=x_3=x_4=x_5=0\), \(\displaystyle x_6=x_7=x_8=1\) e \(\displaystyle x_9=x_{10}=-1\), e quindi

\(\displaystyle a_1\cdot{0}+a_2\cdot{0}+a_3\cdot{0}+a_4\cdot{0}+a_5\cdot{0}+a_6\cdot{1}+a_7\cdot{1}+a_8\cdot{1}+a_9\cdot{(-1)}+a_{10}\cdot{(-1)}\).

Dunque,

\(\displaystyle a_6+a_7+a_8-(a_9+a_{10})\)

Chiamando \(\displaystyle a_6+a_7+a_8=a_j\) e \(\displaystyle a_9+a_{10}=a_i\), abbiamo

\(\displaystyle a_j-a_i\), e possiamo trovare interi \(\displaystyle a_j\) ed \(\displaystyle a_i\) tali che la loro diffrerenza sia un multiplo di \(\displaystyle 1000\).

In generale, abbiamo \(\displaystyle n\) degli \(\displaystyle x_k\) nulli, \(\displaystyle m\) degli \(\displaystyle x_k\) uguali a \(\displaystyle 1\), ed \(\displaystyle l\) degli \(\displaystyle x_k\) uguali a \(\displaystyle -1\), con \(\displaystyle n+m+l=10\); si procede in modo analogo all'esempio.

[xXStephXx]

E come fai ad avere la certezza che esistono sicuramente due $a_i$ con differenza multipla di mille?

[Pachisi]

Forse ho interpretato male il problema, ma non li posso scegliere tale che la loro differenza si multipla di mille?

[j18eos]

"giammaria":...Neanche $x_i=(-1)^i$?...

Ho sbagliato, hai ragionare!

"xXStephXx":..J8eos: xD è la risata più semplice ed è di default xD
E poi ti sfido a trovare un mio messaggio senza xD.

Buono a sapersi... Mica ti offendi se non accolgo la sfida, ma ti credo sulla parola?

[xXStephXx]

J8eos fai bene a fidarti (qua son soli 3 denti però)

Pachisi: gli $a_i$ sono fissati, tu puoi scegliere solo gli $x_i$

però c'è da dire che inavvertitamente rischiavi di beccare la strada giusta xD

[Gi81]

Definiamo $I_10 = {1,2,3,4,5,6,7,8,9,10}$. Per ogni $k in I_10$ consideriamo
$S_k={[sum_{j in J} x_j ]_{1000} \ : \ J in I_10 ^^ |J|=k}$. Si ha ovviamente \(\displaystyle |S_k|\leq \binom{10}{k}\).
Osserviamo che se esistono $J_k, J_h \in I_10$ distinti con $|J_k|=k$ e $|J_h|=h$ tali che
\[ \sum_{i \in J_k} x_i \equiv \sum_{j \in J_h} x_j \ \mod 1000\]
allora esiste una soluzione al problema. (provate a dimostrarlo. se serve lo scrivo)
Ora, se per assurdo non esistessero due insiemi $J_k$ e $J_h$ con quella proprietà, si avrebbe \[ |\bigcup_{k \in I_{10}} S_k | = \sum_{k=1}^{10} |S_k| = \sum_{k=1}^{10} \binom{10}{k}= 2^{10}-1= 1023 >1000\]
chiaramente assurdo

[xXStephXx]

Ok va bene
Riassumendo: le somme possibili tra alcuni elementi sono $1024$, quindi sicuramente per pigeonhole si trovano due che divise per mille danno lo stesso resto. E la loro differenza, essendo divisibile per mille, genera una valida scelta degli $x_i$.

Probabilmente le due somme da sottrarre erano proprio gli $a_i$ e $a_j$ di cui parlava Pachisi, però un pochino immotivato