Disjunkte undermengder med samme sum
Lagt inn: 01/01-2015 17:50
Heisann, kunne noen kikket på dette beviset og sett om det holder?
Bevis at fra en mengde som inneholder 10 forskjellige tosifrede positive heltall, er det mulig å velge ut to disjunkte undermengder som har lik sum.

Antall mulige undermengder av en mengde med ti medlemmer er lik $ \sum_{i=0}^{10} \binom{10}{i} = 2^{10}=1024 $, men undermengdene som lages ved $ \binom{10}{0} $ og $ \binom{10}{10} $ kan ikke brukes til å tilfredstille betingelsene, så vi utelukker disse, og står igjen med 1022 undermengder. Den høyeste verdien en undermengde av $ T = [t_1,t_2,t_3,\dots,t_{10}:t_m \in \mathbb{N} \land 99 \geq t_m \geq 10] $ kan ha er $ 99+98+97+\dots+90 = 945$, og den laveste er $ 10 $, slik at antall mulige verdier en undermengde av $ T $ kan ha er $ 936 $.
Det følger av dette at det finnes en sum som minst $ \lceil \frac{1022}{936}\rceil = 2 $ undermengder har. Hvis disse to undermengdene $ A $ og $ B $ er disjunkte, er vi ferdige. Hvis ikke, definerer vi to nye undermengder av $ T $, $ U $ og $ V $, slik:
$ U = A-(A\cap B) $
$ V = B-(A\cap B) $
$ U $ og $ V $ er disjunkte undermengder av $ T $ som har samme sum, og vi er ferdige.
Bevis at fra en mengde som inneholder 10 forskjellige tosifrede positive heltall, er det mulig å velge ut to disjunkte undermengder som har lik sum.

Antall mulige undermengder av en mengde med ti medlemmer er lik $ \sum_{i=0}^{10} \binom{10}{i} = 2^{10}=1024 $, men undermengdene som lages ved $ \binom{10}{0} $ og $ \binom{10}{10} $ kan ikke brukes til å tilfredstille betingelsene, så vi utelukker disse, og står igjen med 1022 undermengder. Den høyeste verdien en undermengde av $ T = [t_1,t_2,t_3,\dots,t_{10}:t_m \in \mathbb{N} \land 99 \geq t_m \geq 10] $ kan ha er $ 99+98+97+\dots+90 = 945$, og den laveste er $ 10 $, slik at antall mulige verdier en undermengde av $ T $ kan ha er $ 936 $.
Det følger av dette at det finnes en sum som minst $ \lceil \frac{1022}{936}\rceil = 2 $ undermengder har. Hvis disse to undermengdene $ A $ og $ B $ er disjunkte, er vi ferdige. Hvis ikke, definerer vi to nye undermengder av $ T $, $ U $ og $ V $, slik:
$ U = A-(A\cap B) $
$ V = B-(A\cap B) $
$ U $ og $ V $ er disjunkte undermengder av $ T $ som har samme sum, og vi er ferdige.