Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 14. 06. 2017 14:24
Kombinace z kombinaci
Mam "priklad", ktery uz mi strasne dlouho vrta hlavou a nejsem schopen najit obecne reseni. V podstate jde o ucivo stredni skoly (kombinace bez opakovani).
Mame (k) cisel, z kterych muzeme vytvorit (n)tice cisel a (m)tice, kde m<n. Kolik je minimalni pocet (n)tic tak, tak /unikatni/ (m)tice vytvorene z techto vybranych (n)tic byly zaroven sadou vsech (m)tic ktere jde vytvorit z (k)?
Priklad : k=4, n=3, m=2
z (k) lze vytvorit 6 (m)tic (12;13;14;23;24;34)
z kazde (n)tice (jsou celkove 4 - 123;124;134;234) lze vytvorit 3 (m)tice
prostym delenim (6/3) bychom mohli rict ze staci 2 (n)tice k pokryti vsech (m)tic. Protoze ale nelze vybrat (n)tice tak, aby se v nich zadna (m)tice neopakovala, jsou zapotrebi minimalne 3 (n)tice.
A ted obecne reseni? Ma nekdo tuseni jak to pojmout?
Offline
#4 11. 07. 2017 23:30
- check_drummer
- Příspěvky: 4634
- Reputace: 99
Re: Kombinace z kombinaci
↑ noclaf:
Ahoj, búno nechť ta k-prvková množina je {1,..,k}, zkoumejme n-tici N={1,..,n} - a zkoumejme v ní obsaženou m-tici M={1,..,m} a dále zkoumejme n-tice obsahující prvky {1,..,m-1}, označme tyto n-tice jako Ni - ty musí mít všechny ostatní prvky od sebe různé, protože jinak bychom měli dvě n-tice obsahující m stejných prvků - a tedy bychom vygenerovali jednu m-tici vícekrát, což nechceme. Takže každá Ni vždy obsahuje navíc oproti N a oproti již doposud vybraným n-ticím Nj celkem n-m+1 prvků - a protože chceme aby spolu s 1,..,m-1 byl v nějaké m-tici libovolný prvek, tak musí N a Ni pokrývat celou M, tj. musí platit n+c.(n-m+1)=k (pro nějaké c přirozené), tj. n=k mod (n-m+1). To je tedy nutná podmínka na vygenerování každé m-tice z nějakých n-tic právě jednou. Otázka je, zda je postačující, nejspíš ne.
"Máte úhel beta." "No to nemám."
Offline
#5 02. 08. 2017 07:52
Re: Kombinace z kombinaci
kdyz to nejde po dobrem, tak si vypis nekolik moznosti a treba z vysledku dokazes prijit na vzorecek.
n = 4, a = 2, b = 3
dvojice: 12 13 14 23 24 34 (6)
trojice z dvojic: 123 124 134 234 (4)
n = 4, a = 3, b = 3
trojice: 123 124 134 234 (4)
trojice z trojic: 123 124 134 234 (4)
n = 4, a = 1, b = 3
jednice: 1, 2, 3, 4 (4)
trojice z jednic: 123 124 134 234 (4)
n = 5, a = 2, b = 3
dvojice: 12 13 14 15 23 24 25 34 35 45 (10)
trojice z dvojic: 123 124 125 134 135 145 234 235 245 345 (10)
Odhadl bych to, ze vlastne kombinujes stejne prvky jako v prvnim pripade, jenom pocitas 3 cifry.
n = 5, a = 2, b = 4
dvojice: 12 13 14 15 23 24 25 34 35 45 (10)
ctverice z dvojic: 1213 1214 1215 1223 1224 1225 1312 1313...
Tady si nejsem jist, zda 1213 neni stejne jako 1312...
Offline