[shkola] Otnosno zadachata na Dancho
- From: Rangel Dokov <rangel_dokov@xxxxxx>
- To: shkola@xxxxxxxxxxxxx
- Date: Sun, 30 Nov 2003 01:55:00 +0200
Pyrvo uslovieto kakto az go razbrah:
Razpolagame s N nomerirani tochki. Mezhdu tochkite sa prekarani otsechki taka
che ot vsqka tochka izlizat tochno po 2 otsechki. Celta e da se nameri kolko
razlichni nachina za prekarvane na otsechkite ima. Dve svyrzvaniq se chitat za
ednakvi ako spisycite na svyrzanite tochki sa ednakvi. Primer:
1 --- 2
| |
| |
4 --- 3
e _ednakyv_ sys:
1 --- 4
| |
| |
2 --- 3
Ponezhe i dvete imat spisyci na sysedstvo:
(1,2), (1,4), (2,3), (3,4).
A sega i reshenieto:
1-va chast: broq na svyrzvaniq, kogato otsechkite obrazuvat cikyl.
Bez nikakvi ogranicheniq moga da schitam che tochkite sa podredeni v pravilen
N-ygylnik. Vseki takyv N-ygylnik se opredelq ednoznachno ot permutaciqta na
chislata ot 1 do N, kato obikalqme vyrhovete na N-ygylnika po chasovnikovata
strelka, zapochvajki ot nqkoj fiksiran vryh. (ako za gorniq primer zapochvame
da broim ot goren-lqv ygyl, to permutaciite sa syotvetno (1,2,3,4) i
(1,4,3,2))
Sega ostava da nemerim koi ot vsichki N! permutacii sa razlichni. Za celta
trqbva da razdelim tozi broj na broq na elementite v grupata ot simetrii
(avtomorfizmi) na N-ygylnika. Kakvo imam v predvid s tova: vseki N-ygylnik
mozhe da se preobrazuva vyv samiq sebi si chrez nqkakvo preobrazuvanie
(rotaciq, simetriq, etc.). V sluchaq za 4-ygylnik, imame 4 osi na simetriq
(2-ta diagonala i 2-te simetrali), osven tova imame i 4 razlichni zavyrtaniq
okolo centyra sys ygyl 360/4 = 90 gradusa. Tova pravi obshto 8 permutacii,
koito sa ekvivalentni. Sledovatelno resheniqta za edin 4-ygylnik sa:
4! / 8 = 3
Vyobshte v sluchaq s pravilen N-ygylnik razpolagame s 2*N razlichni simetrii.
Taka che broq na razlichni svyrzvaniq za N-ygylnik e raven na:
(N-1)! / 2
2-ra chast.
Pri N >= 6 mozhe da se napravi svyrzvane v koeto se poluchavat 2 (ili poveche
svyrzani komponenti). V tozi sluchaj trqbva da se nami po kolko nachina mogat
da se obrazuvat tezi komponenti. Primer za 6-ygylnik. Toj mozhe da se
predstavi kato 2 triygylnika. Mozhem da izberem 3 ot 6 tochki po tochno
C(6,3) nachina (kydeto C(M,N) oznachava kombinaciite na M elementa ot
N-ti klas) ili C(6,3) = 20. Samo che tova sa vsichki vyzmozhni 3-ygylnici,
t.e. na nas ni trqbvat polovinata zashtoto vseki 3-ygylnik opredelq i negovoto
dopylnenie do 6-te tochki. T.e. imame 10 razlichni razbivaniq na triygylnici.
I ako priemem G(X) dava reshenieto na zadachata za X na broj tochki.
Trqbva da pribavim 10*G(3)*G(6-3) = 10. (ponezhe pri 3 vyha, zadachata
ima edinstveno reshenie, t.e. G(3) = 1).
V obobshteniq sluchaj za N-ygylnik trqbva da se pribavi:
[ C(N,1)*G(1)*G(N-1) + C(N,2)*G(2)*G(N-2) + ... + C(N,N)*G(N)*G(N-N) ] / 2
ili za po kratko: suma C(N,i)*G(i)*G(N-i), za vsqko 0 <= i <= N
kato priemem che G(0) = G(1) = G(2) = 0, zashtoto pri po-malko ot 3
vyrha, zadachata nqma reshenie.
Eto i malko otgovori:
za 4 vyha:
3!/2 = 3
za 5 vyha:
4!/2 = 12
za 6 vyha:
5!/2 + 10*G(3)*G(3) = 60 + 10 = 70.
za 7 vyrha:
6!/2 + 35*G(4)*G(3) = 360 + 35*3 = 360 + 105 = 465
za poveche maj shte e po-lesno da si napisha koda :-)
P.S. Dancho, q kazhi otkyde e tazi zadacha da si namerq testove i da vidq
dali sym uspql da q resha bez da znam tochnoto uslovie :-)
P.P.S. ako nqkoj e ostanal s vpechatlenie che totalno sym omazal
kombinatorikata da se obadi :-)
Happy coding,
Rangel
--
"If people are good only because they fear punishment, and hope for reward,
then we are a sorry lot indeed." -- Albert Einstein
Other related posts:
- » [shkola] Otnosno zadachata na Dancho
