Springen naar inhoud

Verzameling


  • Log in om te kunnen reageren

#1

angel78

    angel78


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 23 september 2006 - 21:17

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

*_gast_PeterPan_*

  • Gast

Geplaatst op 24 september 2006 - 10:47

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 ...

#3

angel78

    angel78


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 24 september 2006 - 11:47

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

#4

eendavid

    eendavid


  • >1k berichten
  • 3751 berichten
  • VIP

Geplaatst op 24 september 2006 - 13:52

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.

#5

*_gast_PeterPan_*

  • Gast

Geplaatst op 24 september 2006 - 15:34

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.

:)

#6

TD

    TD


  • >5k berichten
  • 24049 berichten
  • VIP

Geplaatst op 24 september 2006 - 15:39

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_!

"Malgré moi, l'infini me tourmente." (Alfred de Musset)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures