Sia dato un numero naturale $n$. Determinare il minor numero $k$ tale che per ogni scelta di $k$ naturali $a_i$, esista almeno un valore di:
\begin{equation}
b_1a_1+b_2a_2+...+b_ka_k
\end{equation}
che è multiplo di $n$, dove $b_i$ è un valore a proprio gradimento tra $-1;0;1$
Su gentile osservazione del dottor kalu (e non solo), almeno un valore tra i $b_i$ NON deve essere $0$
Più o meno, niente.
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Più o meno, niente.
Ci provo ma non ne sono sicuro..
Dovrebbe essere $k= \lfloor \log_{2}{ n} \rfloor +1$
Prima dimostro che è sufficiente:
se tra gli $a_i$ c'è uno che è multiplo di $n$ basta porre $b_i=1$ e azzerare tutti gli altri, se ci sono due $a$ congrui tra loro modulo $n$, basta porre ad uno il coefficiente $1$, all'altro il coefficiente $-1$ e azzerare tutti gli altri.
In caso contrario ogni $a_i$ ha resto diverso dagli altri e nessuno ha resto $0$.
A questo punto considero tutti i modi possibili in cui posso sommare gli $a_i$ tra di loro che sono $\displaystyle 2^{ \lfloor \log_{2}{ n} \rfloor +1}-1$ (escludendo il caso in cui non ne sommo nessuno). Se tra queste somme c'è una congrua a $0$ modulo $n$, allora fisso a $0$ i coefficienti degli $a$ che non facevano parte della somma e fisso a $1$ quelli degli $a$ che facevano parte della somma. Altrimenti i resti possibili che possono avere queste somme sono $n-1$, ma il numero di somme ottenute è maggiore o uguale a $n$. Quindi per il principio dei cassetti ci sono due somme congrue tra loro modulo $n$.
Quindi faccio la differenza tra queste due somme ottenendo una cosa che è congrua a $0$ modulo $n$.
Quindi se un elemento compare in emtrambe le somme o non compare in nessuna delle due gli metto coefficiente $0$. Se compare solo nel "minuendo" gli metto coefficiente $1$, se compare solo nel sottraendo gli metto coefficiente $-1$.
Se invece $k$ è minore di $\lfloor \log_{2}{ n} \rfloor +1$ basta usare come controesempio il caso in cui gli $a_i$ sono potenze di $2$.
Ovvero $a_1=2^0, a_2=2^1,...,a_k=2^{k-1}$. In questo caso il massimo valore che posso ottenere operando con questi $a$ è minore di $n$ in valore assoluto e si prova che non può essere manco $0$ (basta dividere per l'MCD e rimarrà un $1$ scoperto che renderà la somma dispari). Quindi non si possono scegliere i coefficienti in modo da ottenere un risultato divisibile per $n$.
Dovrebbe essere $k= \lfloor \log_{2}{ n} \rfloor +1$
Prima dimostro che è sufficiente:
se tra gli $a_i$ c'è uno che è multiplo di $n$ basta porre $b_i=1$ e azzerare tutti gli altri, se ci sono due $a$ congrui tra loro modulo $n$, basta porre ad uno il coefficiente $1$, all'altro il coefficiente $-1$ e azzerare tutti gli altri.
In caso contrario ogni $a_i$ ha resto diverso dagli altri e nessuno ha resto $0$.
A questo punto considero tutti i modi possibili in cui posso sommare gli $a_i$ tra di loro che sono $\displaystyle 2^{ \lfloor \log_{2}{ n} \rfloor +1}-1$ (escludendo il caso in cui non ne sommo nessuno). Se tra queste somme c'è una congrua a $0$ modulo $n$, allora fisso a $0$ i coefficienti degli $a$ che non facevano parte della somma e fisso a $1$ quelli degli $a$ che facevano parte della somma. Altrimenti i resti possibili che possono avere queste somme sono $n-1$, ma il numero di somme ottenute è maggiore o uguale a $n$. Quindi per il principio dei cassetti ci sono due somme congrue tra loro modulo $n$.
Quindi faccio la differenza tra queste due somme ottenendo una cosa che è congrua a $0$ modulo $n$.
Quindi se un elemento compare in emtrambe le somme o non compare in nessuna delle due gli metto coefficiente $0$. Se compare solo nel "minuendo" gli metto coefficiente $1$, se compare solo nel sottraendo gli metto coefficiente $-1$.
Se invece $k$ è minore di $\lfloor \log_{2}{ n} \rfloor +1$ basta usare come controesempio il caso in cui gli $a_i$ sono potenze di $2$.
Ovvero $a_1=2^0, a_2=2^1,...,a_k=2^{k-1}$. In questo caso il massimo valore che posso ottenere operando con questi $a$ è minore di $n$ in valore assoluto e si prova che non può essere manco $0$ (basta dividere per l'MCD e rimarrà un $1$ scoperto che renderà la somma dispari). Quindi non si possono scegliere i coefficienti in modo da ottenere un risultato divisibile per $n$.
-
Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
