Disjunkte undermengder med samme sum

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Disjunkte undermengder med samme sum

Innlegg stensrud » 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.
stensrud offline
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Bosted: Cambridge

Re: Disjunkte undermengder med samme sum

Innlegg Gustav » 02/01-2015 02:05

Ser riktig ut. Du kunne kanskje nevnt at du bruker skuffeprinsippet (pigeonhole principle) i argumentasjonen.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4283
Registrert: 12/12-2008 12:44

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 3 gjester