Matematické Fórum

Ahoj ↑ BakyX:,

Skrytý text:
Co si myslis o tejto postupnosti
1; 3; 5;  ...;2999; 4; 12; ... ; 2996
su v nej vsetki neparne cisla z (mame 1500 takych cisiel)
a tiez vsetky cisla formy z formy 4a, kde a je neparne ( mame 375 takych cisiel)?

↑ BakyX:

↑ vanok:
Ahoj, z čeho prosím plyne, že je Tebou uvedná množina maximální taková?
Děkuji

Ahoj,
↑ vanok:

Skrytý text:
nsd 2 asi ne, třeba 8 v tvé množině není... Pokud jsi chtěl napsat, že každý prvek je buď dvojnásobkem, nebo polovinou něčeho z , pak si nemyslím, že to je dostatečný argument. Pokud jsi chtěl napsat, že každý prvek je dvojnásobkem něčeho z , pak bych asi souhlasil, ale úplně samozřejmé mi to odůvodnění nepřijde.
Promiň, že tak hnidopíchám, taky už totiž chvilku přemýšlím, jak toto "jasné" tvrzení nějak elegantně zdůvodnit a nic extra snadného mě nenapadá.

Skrytý text:
Než někdo dojde k hezčímu zdůvodnění, tak já bych argumentoval takovými "minisouboji" dvojic adeptů do naší množiny, která splňuje to o dvonásobcích:
- Mějme libovolné liché . V naší množině může být nanejvýš jedno z čísel . Zvolením do množiny vyřadíme ze hry , ale na zbytek čísel už žádné podmínky nenakládáme, takže ho do můžeme bez obav přidat. Volba nemůže být výhodnější.

Z toho důvodu do nahážeme všechna lichá čísla. Tím jsme probrali kandidáty tvaru a , kde je liché. Další souboj proběhne mezi čísly ve tvaru a , pak a , a dál, dokud neprobereme všechna čísla do 3000.

Skrytý text:

Našich 3000 čísel nasekáme zhruba na čtvrtinky.
Vezměme čísla 1501-3000. Polovina z nich jsou dvojnásobky čísel 751-1500. Protože z každé dvojice, která se liší jen o násobek 2, může být v nanejvýš 1 člen, usoudíme, že může z čísel obsahovat nanejvýš 2/3. Podobně pokračujeme se zbytkem.

751-1500   1501-3000         V M je max. 2/3 z čísel  751-3000
188- 375     376- 750          V M je max. 2/3 z čísel  188- 750   (dokonce ostře méně)
  47-  93       94- 187          V M je max. 2/3 z čísel    47- 187
  12-  23       24-   46          V M je max. 2/3 z čísel    12-  46   (dokonce ostře méně)
    3-   5         6-   11          V M je max. 2/3 z čísel      3- 11
        1               2              V M je méně než 2/3 z čísel 1,2.
A protože 2/3 z 3000 jsou 2000, je jasné, že v množině A, která má splňovat ty podmínky o dvojnásobcích musí být méně než 2000 prvků.

↑ vanok:
Pak je ovšem otázka, zda všechny takové maximální množiny mají stejný počet prvků...

Ahoj,
napadlo mě toto (většina toho co napíšu ale už bylo řečeno výše, spíš to řeknu trošku jinak). Rozdělme M na třídy ekvivalence. Každá třída je maximální taková množina prvků {xi}, že .
Je zřejmé, že:
- nejmenším prvkem každé třídy je liché číslo
- k "porušení" podmínky (říkejme této podmínce P), že daná množina B, , neobsahuje prvky x a 2x dojde pro nějaké dva prvky jedné třídy ekvivalence

Tedy pro nalezení maximální množiny B, která neporušuje P, stačí hledat maximální množinu neporušující P v každé třídě ekvivalence. To je však jednoduché. Každá taková tříde je totiž tvaru {y,2y,4y,..,} pro y liché. Tj. stačí do B vložit např. každý 1.,3.,5.,... prvek (pokud je počet prvků dané třídy sudý, pak by bylo možné do B vložit i každý 2.,4.,6.,... prvek).

Teď jde jen o to vhodně spočítat počet těchto prvků. Rozdělíme třídy ekvivalence na podtřídy obsahující stejný počet prvků - tedy lze z každé takové třídy vložit do B stejný počet prvků (n) a je-li tříd v dané podtřídě k, pak tato podtřída přispěje do B celkem n.k prvky. Totéž provedeme pro všechny podtřídy a výsledek sečteme.

Např. třídy obsahující jen jeden prvek jsou třídy, jejichž první prvek je mezi 1501 a 3000 (a je to liché číslo), podobně třídy obsahující právě dva prvky jsou třídy, jejichž první prvek je mezi 751 a 1500, atd.

Tj. celkem máme třídy tyto třídy (v závorce je vždy počet tříd, počet znamená počet prvků každé třídy a tot je celkový počet prvků, kterým třídy o těchto prvcích souhrnně přispívají do B):

1501-3000 (750), počet 1, tot 750
751-1500 (375), počet 2, tot 375
376-750 (187), počet 3, tot 374
188-375 (94), počet 4, tot 188
94-187 (47), počet 5, tot 141
47-93 (24), počet 6, tot 72
24-46 (11), počet 7, tot 44
12-23 (6), počet 8, tot 24
6-11 (3), počet 9, tot 15
3-5 (2), počet 10, tot 10
2-2 (0), počet 11, tot 0
1-1 (1), počet 12, tot 6
celkem: 1999

Tedy množina obsahující 2000 prvků již poruší podmínku P.

Pokoušel jsem se uvedený počet vyjádřit nějak elegantněji, ale problém zde nastává s tím, že počet tříd v každé podtřídě závisí na tom, zda je první číslo uvedeného intervalu liché nebo sudé: Např. v případě tříd, které obsahují 10 prvků, začínají tyto třídy (resp. jsou to jejich nejmenší prvky) číslem 3 až 5. jelikož číslo 3 je liché, máme dvě třídy s 10 prvky (obsahující 3 a 5). Pokud by však např. tyto třídy začínaly čísly 2 až 4, pak bychom měli jen jednu třídu (začínající 3).

Obecně tedy pro třídu obsahující i prvků máme dolní a horní hranici pro nejmenší prvek každé takové třídy jako: až , tedy počet lichých čísel v tomto intervalu je , kde c=1 pro liché, jinak je c=0.
Počet prvků z každé této třídy, které mohou přispět do B je , tedy celkem je počet prvků přispívajících do B dán jako , kde sčítáme dokud hranice některé ze tříd není číslo 1.
Velice zhruba řečeno jde tedy o sumu tvaru .

Dobrý deň. Ďakujem za zaujímavú diskusiu. Konečne som späť a preto načrtnem moje riešenie:

Všetky čísla z množiny rozdeľme do tried tak, že v každej z nich budú čísla tvaru pre konkrétne nepárne . Ak si vezmeme čísla z dvoch rôznych tried, tak zrejme ich podiel nie je celočíselný, alebo je deliteľný nepárnym číslom a teda je rôzny od 2. Preto stačí určiť, koľko najviac čísel možno zobrať z každej triedy, čo je už len počítanie.

Skrátka prakticky to isté, ako má ↑ check_drummer:.

Odvádzal som aj všeobecný vzorec pre maximálny počet prvkov tejto podmnožiny ak má ako prvky prvých čísel a je celkom hrozivý:



Pre to však po troške počítania hádže .