Numeri Grossi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Saro00
Messaggi: 114
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Numeri Grossi

Messaggio da Saro00 » 14 feb 2019, 20:55

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
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)

Avatar utente
Doxeno
Messaggi: 28
Iscritto il: 16 lug 2018, 14:14

Re: Numeri Grossi

Messaggio da Doxeno » 15 feb 2019, 22:56

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.

Saro00
Messaggi: 114
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: Numeri Grossi

Messaggio da Saro00 » 16 feb 2019, 11:58

:)
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)

Rispondi