Un numero intero $N$ è "grosso" se la seguente proprietà è soddisfatta:
Per ogni insieme di $10$ interi positivi di al più $N$ cifre, esistono $2$ sottoinsiemi disgiunti la cui somma è uguale.
a) Determinare (e dimostrare) se $N=3$ è grosso
b) Determinare (e dimostrare) se $N=2$ è grosso
Re: Numeri Grossi
Inviato: 15 feb 2019, 22:56
da Doxeno
Testo nascosto:
Per N=3 esiste l'insieme S={1,2,4,...,256,512}.
Poiché un numero può essere scritto in unico modo in base 2, considerando un sottoinsieme di S, è l'unico ad avere una certa somma degli elementi. Dunque, 3 non è grosso.
Con N=2, le possibili somme degli elementi di un sottoinsieme sono 99*10=990, però i modi di prendere un sottoinsieme diverso dall'insieme vuoto e da S sono 2^10-2=1022. Poiché 1022>990, si avranno sicuramente due sottoinsiemi distinti con la stessa somma degli elementi per pigeonhole.
Se questi non fossero disgiunti, togliendo a entrambi i sottoinsiemi la loro intersezione, si avranno comunque due insiemi con la stessa somma degli elementi, ma disgiunti. Dunque, 2 è grosso.
