Verzameling

angel78

Hoi,

Kan iemand mij helpen met het volgend probleempje?

S is een deelverzameling van (1, 2, .....,1989) zodat geen twee elementen 4 of 7 verschillen. Wat is de maximale grootte van S?

(Ik heb geprobeerd het uit te schrijven, om zo een algemene formule te bedenken, maar het lukt mij niet)

Alvast bedankt voor jullie reakties,

angel 78

PeterPan

S = {3,6,9, ..., 3k, ...,1989}, dus S bevat 663 elementen.

N.B. S = {3k, k=1..663} of S = {3k-1, k=1..663} of S = {3k-2, k=1..663}.

Hint: Elk ontbrekend element van S kan op een maximaal aantal manieren worden gevormd door bij een element van S 4 of 7 bij of af te tellen. Stel dus S bevat minstens 664 elementen. Dan ...

angel78

Hoi Peter Pan,

Hartelijk dank voor je reactie. Ik had het niet zo bekeken, maar nu merk ik dat met jouw oplossing alles klopt als een bus!!

Bedankt, Angel

eendavid

Peterpan,

ben ik verkeerd met volgend tegenvoorbeeld?

S=(1,2,3,4,12,13,14,15,23,24,25,26,...), dus

S={11k+n|k=0..180,n=1..4} levert 4*181=724 elementen.

Ik vind geen bewijs dat dit het beste is. Alleszins zijn er niet-elementen van S waar je 3 ipv 2 elementen van S voor kan vinden die ermee verbonden zijn.

Mijn excuses om moeilijk te doen.

PeterPan

eendavid schreef:Peterpan,

ben ik verkeerd met volgend tegenvoorbeeld?

S=(1,2,3,4,12,13,14,15,23,24,25,26,...), dus

S={11k+n|k=0..180,n=1..4} levert 4*181=724 elementen.

Ik vind geen bewijs dat dit het beste is. Alleszins zijn er niet-elementen van S waar je 3 ipv 2 elementen van S voor kan vinden die ermee verbonden zijn.

Mijn excuses om moeilijk te doen.

TD

Dat is een typische "val" die ook met dit voorbeeld geïllustreerd wordt:

Proof Traps by Jim

by example: How big a subset of {1, ... 20} can you make so that no two

elements differ by 3 or 5?

Proof (obviously): choose each number to be in if it can starting at 1

choose 1, 2, and 3

4, 5, 6, 7, and 8 are all different by 3 and/or 5 from 1, 2, 3

choose 9, 10, and 11

12, 13, 14, 15, and 16 are all different by 3 and/or 5 from 9, 10, 11

choose 17, 18, 19

20 differs by 3 from 17

result: 1,2,3,9,10,11,17,18,19 chosen in smart way, so the answer is 9

But wait, what about choosing the odd numbers

result: 1,3,5,7,9,11,13,15,17,19 chosen and fit conditions

Proof (try again):

(1,4)(2,5)(3,6)(7,10)(8,11)(9,12)(13,16)(14,17)(15,18)(19)(20)

maximum can be 11 since only 1 can be taken from each subset

(1,6)(2,7)(3,8)(4,9)(5,10)(11,16)(12,17)(13,18)(14,19)(15,20)

maximum can be 10 since only 1 can be taken from each subset

in fact, the odds are an example that does include one from each

Therefore, 10 is the exact answer.

Moral: proof may be _obvious_ to you, and yet still be _wrong_!

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Verzameling

Verzameling

Re: Verzameling

Re: Verzameling

Re: Verzameling

Re: Verzameling

Re: Verzameling