Grafos

Problemes de Grafs i Complexitat
Professorat de Grafs i Complexitat Gener de 2012

Cap´ ıtol 1

Conceptes previs: Funcions i algorismes
1. Una funci´ booleana consisteix en una correspond`ncia en la qual, a partir o e de n inputs binaris, obtenim un unic output binari. ´ Quantes funcions booleanes podem construir? Soluci´ o Com que hi ha 2n seq¨`ncies d’n inputs binaris, ens demanenquantes funcions ue n entre N2n i X = {0, 1} podem fer. Per tant, hem de calcular V R(2, 2n ) = 22 .

2. Troba el nombre de permutacions dels nou d´ ıgits 1, 2, 3, 4, 5, 6, 7, 8, 9 en les quals (a) els blocs 12, 34 i 567 no apareixen (b) els blocs 12, 23 i 415 no apareixen

Soluci´ o (a) Permutacions on els blocs 12, 34 i 567 no apareixen. De permutacions de 9 d´ ıgits n’hi ha P (9), per` li hem dedescomptar o aquelles en les que figura el bloc 12. Podem considerar que el bloc 12 t´ entitat pr`pia i, llavors, junt amb els e o altres d´ ıgits 3, 4, 5, 6, 7, 8, 9 fer totes les possibles permutacions. En total n’hi haur` P (8). a De la mateixa manera, de permutacions en les que figura el bloc 34 n’hi ha P (8) i de permutacions on figura el bloc 567 n’hi ha P (7). Compte que al restar del total P(9) les permutacions on apareix el bloc 12 i llavors aquelles on apareix el bloc 34, hi ha permutacions que les hem 1

Conceptes previs: Funcions i algorismes

2

restat dues vegades. S´n aquelles en les que apareix el bloc 12 i, tamb´, o e 34. An`logament amb els altres blocs. a Per tant el que ens demanen ´s: e P (9) − P (8) − P (8) − P (7) + P (7) + P (6) + P (6) − P (5) = 283560 (b)Permutacions on els blocs 12, 23 i 415 no apareixen. El problema ´s semblant a l’anterior. La difer`ncia ´s que en les pere e e mutacions on apareix el bloc 12 estem segurs que el bloc 415 no apareix, etc. El que ens demanen ´s: e P (9) − P (8) − P (8) − P (7) + P (7) + P (6) = 282960

3. En el conjunt de tots els nombres naturals m´s grans o igual que 0 i m´s e e petits que 1010 , hi ha m´snombres que contenen algun 9, o b´, n’hi ha m´s que e e e no en contenen cap? Soluci´ o Calculem els nombres entre 1 i 1010 que no contenen cap 9: s´n els nombres de o 10 xifres que es poden formar utilitzant, nom´s, les xifres 0, 1, 2, 3, 4, 5, 6, 7 i 8 e (els nombres de, per exemple, 3 xifres es poden escriure com un nombre de 10 xifres amb les primeres 7 xifres iguals a 0). Es tracta de les funcionsentre N10 i {0, 1, 2, 3, 4, 5, 6, 7, 8}. Aix´ es poden escriure V R(9, 10) = 910 = 3486784401 nombres sense cap 9. ı, Per tant, es poden escriure 1010 − 910 = 6513215559 nombres amb algun 9. En definitiva, hi ha m´s nombres amb algun 9 que sense cap 9, pr`cticament el e a doble.

4. Un estat que es troba a les ant´ ıpodes d’Austr`lia ha fet un paper poc llu¨ a ıt a les darreres olimp´ ıades (peraix` no fem p´blic el seu nom). Un diari local, o u de llarga tradici´ i discurs florit, proposa, per apaivagar una mica els `nims, o a la creaci´ de la vicemedalla; la vicemedalla ´s la distinci´ que s’atorga a qui o e o obt´ el quart lloc a qualsevol de les competicions. Aix´ pels redactors d’aquest e ı, insigne diari, els quatre premis importants s´n: el primer (or), el segon (plata), o eltercer (bronze) i el quart (vicemedalla). D’aquesta manera, els resultats dels esportistes d’aquest antic estat milloren substancialment, perqu` a la seva e representaci´ hi ha molts vicemedallistes (pr`cticament tants com a medallistes). o a En una prova atl`tica hi participen 12 competidors, 3 dels quals s´n compae o triotes dels esmentats redactors (els de l’insigne diari). Suposem que tots elsparticipants acaben correctament la carrera (´s a dir, en una de les 12 posicions, e sense abandonar o quedar desqualificats). Contesta: (a) De quantes formes diferents poden arribar aquests 12 corredors?

Conceptes previs: Funcions i algorismes

3

(b) De quantes maneres es poden repartir les tres medalles entre els 12 corredors? (c) I si s’afegeix el gener´s premi de la vicemedalla, de...