http://libreria-universitaria.blogspot.com

MATEMTICAS DISCRETASCuarta edicin

Richard JohnsonbaughDePaul University, Chicago

fRADUCCIN: scar Alfredo Palmas Velasco Doctor en Matemticas Instituto de Matemticas~EVISIN TCNICA:

Vctor Hugo Ibarra Mercado Lic. en Fsica y Matemticas, ESFM-IPN Catedrtico de la Escuela de Actuara Universidad Anhuac

PRENTICEHALLMXICO' NUEVA YORK' BOGOT' LONDRES' MADRID MUNICH' NUEVA DELHI' PARS' RO DE JANEIRO SINGAPUR' SYDNEY' TOKIO' TaRaNTa' ZURICH

m

'wmmE'

E'

http://libreria-universitaria.blogspot.com

o/c..rOAS> (/'vl2,Entonces p es falsa y q es verdadera. Por tanto,

q:4 2, entonces 3 < 6.

'1

n .,

Sip y q son proposiciones, la proposicin compuestap si y slo si q

es una proposicin bicondicional y se denota

pHq.El valor de verdad de la proposicin p H q se define mediante la siguiente tabla de verdad:

(a) Sean

p: l 1 x2 +Ies falsa precisamente cuando

_1_.

46. Escriba la negacin de cada proposicin en los ejercicios 2245.~

47. La siguiente proposicin apareci en la columna Querida Abby: Todos los hombres no engaan a sus esposas. Cules el significado exacto de esta afirmacin? Piensa que la proposicin es verdadera o falsa? 48. El economista Robert J. Samuelson fue citado diciendo "Cada problema ambiental no es una tragedia". Cul es el significado exacto de esta afirmacin? Aclare la afirmacin reformulndola. 49. (a) Utilice una tabla de verdad para demostrar que si p y q son proposiciones, alguna de las afirmaciones p -+ q o q -+ p es verdadera. (b) Sea P(x) la funcin proposicional "x es un nmero racional" y sea Q(x) iafuncin proposicional "x es un nmero positivo". El dominio de discurso es el conjunto de todos los nmeros reales. Comente el siguiente argumento, que supuestamente demuestra que todos los nmeros racionales son positivos o que todos los nmeros reales positivos son racionales. Por el inciso (a),' 1, entonces :cI(x'

+ 1) 1, enronces e'(x'

t. '

La geometra euclidiana proporciona un ejemplo de sistema matemtico. Entre los axiomas estn Dados dos puntos distintos. existe exactamente una recta que los contiene. Dada una recta y un punto que no est sobre la recta. existe exactamente una recta paralela a la primera recta y que pasa por el punto. Los trminos punto y recta son trminos no definidos que quedan definidos de manera implcita mediante los axiomas que describen sus propiedades. Entre las definiciones estn Dos tringulos son congruentes si sus vrtices pueden ponerse en correspondencia de modo que los lados correspondientes y los ngulos correspondientes sean iguales. Dos ngulos son suplementarios si la suma de sus medidas es 180. OE..JEMPL.O 1.4..2

EJEMPl..O I AA

Un ejemplo de corolario en geometra euclidiana es

,~~

-Siun tringulo es equiltero. entonces es equiangular.Este corolario se sigue de manera inmediata a partir del primer teorema del ejemplo 1.4.3.O

~

---.',-

EJEMPLO 1 A.5

,

Algunos ejemplos de teoremas relativos a los nmeros reales son

x . O = Opara cada nmero real x.Para todos los nmeros reales x, y y z, si x :s y y y :s z, entonces x :s z.

Los nmeros reales proporcionan otro ejemplo de sistema matemtico. Entre los axiomas estn Para todos los nmeros reales x y y. xy = yx. Existe un subconjunto P de nmeros reales que satisface (a) Si x y y estn en p. entonces x + y y xy estn en P. (b) Si x es un nmero real. entonces exactamente una de las siguientes afirmaciones es verdadera:x eSG\ en P

o

.,". "1 ;.-.er.. .1

'i0C'--1

EJEMPl..O 1 A.6

.:

/f!rt.

(tr,ty-

Un ejemplo de lema relativo a los nmeros reales es Si n es un entero positivo. entonces n - l es un entero positivo o n - = O. Seguramente este resultado no es interesante en s mismo, pero puede utilizarse para demostrar otros resultados. O

x=O

-x est en P.

1'-

La multiplicacin se define de manera implcita mediante el primer axioma y otros axiomas que describen las propiedades que se supone tiene la multiplicacin.

__,_.b

.-' I'! e: ..e-

__________ _ _ _ _ _ _ _ _ _ --- qP :. q22. p I\p

21. p--'>q

Oy x"'" O;

'L:.p23. p --'>( q '~-H )q--'>p--'>r) :. (p./ q) --'> r

9. Muestre, mediante una demostracin por contradiccin, que si se colocan 100 bolas en nueve cajas, alguna caja contiene 12 o ms bolas. Formule los argumentos de los ejercicios 10-14 en forma simblica y determine si cada uno es vlido. Seanp: Estudio mucho. q: Obtengo un 10.r: Me vuelvo rico.

:. q24. (p --'>q ) 1\ ( r --'>s)pVr :.qV s

25. Muestre que si

10. Si estudio mucho. entonces obtengo un 10. Estudio mucho. :. Obtengo un 10. l I. Si estudio mucho, entonces obtengo un 10. Si no me vuelvo rico, entonces no obtengo un 10. :. Me vuelvo rico. 12. Estudio mucho si y slo si me vuelvo rico. Me vuelvo rico. :. Estudio mucho. 13. Si estudio mucho o me vuelvo rico, entonces obtengo un 10. Obtengo un 10. :. Si no estudio mucho, entonces me vuelvo rico.

son argumentos vlidos, el argumento

tambin es vlido. 26. Comente acerca del siguiente argumento:

El espacio de almacenamiento en disco flexible es mejor que nada. Nada es mejor que una unidad de disco duro. :. El espacio de almacenamiento en disco flexible es mejor que una unidad de disc duro.

. . . . .42C .... PITULO 1 I LOGlCA y DEMOSTRACIONES

i\,.;:;~

1 .5 J DEMOSTR....C IONES

POR RESOL.UCtON

43

. ~~"

t

1.5 DEMOSTRACIONES POR RESOLUCIN

EJEMPLO 1.5A

:,-. :t'"-''l'~t~!

En esta seccin escribiremos a 1\ b como abo La resolucin es una tcnica de demostracin propuesta por J. A. Robinson en 1965 (vase [RobinsonJ) que depende de una nica regla: Si P V q Y PV r son verdaderas, entonces q V r es verdadera.(1.5.1)

Demostraremos lo siguiente mediante resolucin 1. 2. 3.

s VecVd :.bvd

avb

i..... :'-;..- O-".,~_

--..

,'-

Podemos verificar (1.5.1) mediante la tabla de verdad (vase elejercicio 1). Como la resolucin depende slo de esta sencilla regla, es la base de muchos programas de computadora que realizan razonamientos y demostraciones de teoremas. En una demostracin por resolucin, las hiptesis y la conclusin se escriben como clusulas. Una clusula consta de trminos separados por o, donde cada trmino es una variable o la negacin de una variable.EJEMPLO 1.5.1 ,

.,~~

.

Al aplicar (1.5.1) a las expresiones 1 y 2, deducimos

.~ :~-

4.

bvc

.~.'~r.

Al aplicar (1.5.1) a las expresiones 3 y 4, deducimos 5. bv d

~.

La expresin

la conclusin deseada Dadas las hiptesis 1, 2 Y3, hemos demostrado la conclusin b vd. O Algunos casos particulares de (1.5.1) son

aVbVcvdes una clusula, pues los trminos a, b, variable o la negacin de una variable.EJEMPLO 1 .5.2

e y d estn separadas por o, y cada trmino es unaO

Si p V q YPson verdaderas, entonces q es verdadera. (1.5.2) Si p yEJEMPLO 1.5.5

PV r son verdaderas, entonces r es verdadera.

....~~-'''~u

,--

~_.

!

La expresin

Demostraremos lo siguiente mediante.sesolucin

xyVwVzno es una clusula, pues aunque los trminos estn separados por o, el trmino xy consta de dos variables, y no de una sola. OEJEMPLO 1.5.3

1.2.

a

ii

Ve

'fB!r" r:

3.

cVd

::dAl aplicar (1.5.2) a las expresiones 1 y 2, deducimos

f

4.La expresinp~q

e

Al aplicar (1.5.2) a las expresiones 3 y 4, deducimos

5.

d

no es una clusula, pues los trminos estn separados por~. Sin'embargo, cada trmino es una variable. O Una demostracin directa por resolucin se realiza aplicando varias veces (1.5.1) a pares de afirmaciones, para deducir nuevas afirmaciones, hasta que se obtenga la conclusin. Al aplicar (1.5.1), p debe ser una sola variable, pero q y r pueden ser expresiones. Observe que al aplicar (1.5.1) a las clusulas, el resultado q V r es una clusula. (Como q y r constan de trminos separados por o, donde cada trmino es una variable o la negacin de una variable, q V r tambin consta de trminos separados por o.donde cada trmino es una variable o la negacin de una variable.)r Esta seccin puede omitirse sin prdida de continuidad.

O laconclusin deseada. Dadas las hiptesis 1,2 Y3, hemos demostrado la conclusin d. Si una hiptesis no es una clusula, debe reemplazarse por una expresin equivalente que sea una clusula o la conjuncin de varias clusulas. Por ejemplo, supongamos que una de las hiptesis es a V b . Como la barra est sobre ms de una variable, utilizamos la primera ley de De Margan (vase el ejemplo 1.2.11) (1.5.3) para obtener una expresin equivalente con una barra sobre las variables individuales

~

a v b ss a b,

:.~L

~-

:te.~

L

---~

t

IIfIr

C~,~~,,~,:,:,,:5~.!, !i~;:.:.'(;' .';~;t:_, ;:

J_ii:;;;'!~r;~-~~,.~:~',:;~~i~~'1':J1,{~~'".i(~!i :;:'":".,,~

t' ,l. ,d ' j 11

z..:'

';,J'

.~:i

i~l

,;"r!;~I~2',~';~,

'!,meros ann6nicos crecen sn'Imte.Enjaterminologadel clculo; la srie.armnca': 1'".' .,; ~"., ! i ':'j_~,~'.~':'-~(,:,,:NOTAS

La bibliografa general relativa a las matemticas discretas es [Dossey; Graham, 1988; '... Solucinfo~ ",:1 1.., a :~

Podemos esCribir

la:Souci6nformal '.'" ; __

'.. :.. ; ";; , r

:;\,~.

,,-

...

Liu, 1985; Ross; Tucker]. [Knuth, 1973, volmenes l y 3; 1981) es la referencia clsica para una gran parte del material. [Barker; Copi; Edgar] son libros de texto de introduccin a la lgica. Un anlisis ms avanzado aparece en [Davis], El primer captulo del libro de geometra de [Jacobs] est dedicado a la lgica bsica. [Solow] estudia el problema de la construccin de demostraciones. Para una historia de la lgica, vase [Kline]. El papel del razonamiento lgico en los programas de cmputo se analiza en [Gries], La formacin de mosaicos con polirnins es el tema del libro de [Martn].

,~

.~

,~~'

/:::::9 CONCEPTOS BSICOS DEL CAPTULO

Seccin1.1Lgica Proposicin COnjuncin: p y q, P f\ q Disyuncin, p o q, p V q

Negacin: nop,p Proposicin compuesta Tabla de verdad O exclusivo de proposiciones p, q: p o q, pero no ambos

e--

rtr,~-

.t-

J..__----~---~--------_._--~--_ ..

:~

_---

!~

10-~'-

60

CAPiTULO 1

I

LGICA y DEMOSTRACIONES

CAPITULO 1

I

LOGICA y DEMOSTRACIONES

61

Seccin 1.2Proposicin condicional: si p, entoncesq;p~q

Para demostrar que la afirmacin cuantificada universalmente para alguna x, P(x) es falsa, muestre que para cada x en el dominio de discurso, la proposicinP(x) . es falsa.

~ AUTOEVALUACIN DEL CAPTULO

Seccin 1.11. Si p, q y r son verdaderas, determine el valor de verdad de la proposicin (p V q ) /1.

Hiptesis Conclusin Condicin necesaria Condicin suficiente Recproca dep ~ q: q ~ p Proposicin bicondicional: p si y slo si q,p H q Equivalencia lgica: P == Q Leyes de De Morgan para la lgica: p V q es jil\q,pl\q'" jivq Contrapositiva de p -o q: q -o ji

p 1\ r) V q).2. Escriba la tabla de verdad de la proposicin (p tI. q ) V (p V

r ).

r: 44.~' i l31BUOTE:C.:\ F;.CULT.\r.I

3. Formule la proposicin p 1\ ( q V r) con palabras, utilizando'p: Mi rea es la administracin hotelera. q: Mi rea es la supervisin de diversiones.

Seccin 1.3Funcin proposicional Dominio de discurso Cuantificador universal Afirmacin cuantificada universalmente Contraejemplo Cuantificador existencial Afirmacin cuantificada existencialmente Leyes de De Morgan generalizadas para la lgica: ';;Ix, P(x) y 3x, P(x) tienen los mismos valores de verdad. 3x, P(x) y ';;Ix, P(x) tienen los mismos valores de verdad. Para demostrar que la afirmacin cuantificada universalmente para cada x, P (x)

Seccin lA Sistema matemtico Axioma Definicin Trmino no definido Teorema Demostracin Lema Demostracin directa Demostracin por contradiccin Demostracin indirecta Demostracin por contrapositiva Razonamiento deductivo Hiptesis Premisas Conclusin Argumento Argumento vlido Argumento no vlido Seccin 1.5 Demostracin por resolucin; utiliza: Si p V q Y ji V r son verdaderas, entonces q V r es verdadera. Clusula: consta de trminos separados por o, donde cada trmino es una variable o la negacin de una variable. Seccin 1.6 Principio de induccin matemtica Paso base: demostrar la verdad de la afirma. cin para la primera instancia Paso inductivo: suponer ciertas todas las instancias menores que n y demostrar que es cierta para n Frmula para la suma de. los primeros n enteros positivos:

,~

. y

I . ~ (. ~ ['".,,, .'.'-"~", 1""'''';','' ",J .. ~ ..... ;~ '

"~'d~trar~una'propiedad-s.vlida,~_rel8cJ;;~ieS~oJCoitSiderar-uoelenentoarbitrariodia'.rehiciliydemostrar11l'nOpidadpara'0'

(t..~

~

~\j,~ '.'... :J.:' '. .~.'.''Po~'L-'>:',1~~_.-,

,~;,::;.'

-

.,

;,

_'~~ ~=-::

' ':.'..-; o;:;?_,1'i'.:1-'~;_?

j,:,: ';"' ",;:':'.'1',C:), ~:,;t't'X,,~..t:

oc';,:. "'.,~...

I

~~~ii$~r~~?t~!("'1i~~~~~t~t",

; '(X~,,) represente unpar ordenado arbitranoenR:y;seproporciona IUI. argumen-

~,i';or,ejemp~,:par~dem~\q~~~laci~ll'~~;~lm~c;yerhace~,ue;

O(t'~.~~.

_____ Jnz-~ - - - - - - - - - - - - - - - - - - - - - - -.......

1

C-

http://libreria-universitaria.blogspot.com1 04

e A plTULO 2

I

EL LENGUAJE DE LAS MATEMTICAS

2.51 RELA'

2.5

REIACIONES DE EQUIVALENCIA

.'

EJEMPJ..02.5.4.

FIGURA 2.5.1 Un conjunto de bola,s con color.

Suponga que tenemos un conjunto X de 10 bolas rojas (R), azules (B) y verdes (G) (vase la figura 2.5.1). Si dividimos las bolas en los conjuntos R, 'By G de acuerdo con su color, la . familia {R, B, G} es una particin de X. (Recuerde que en la seccin 2.1 definimos una particin de un conjunto X como una coleccin S de subconjuntos no vacos de X tal que todo elemento en X pertenece exactamente a un miembro de S.) Una particin puede utilizarse para definir una relacin. Si S es una particin de X, podemos decir que x R y si para algn conjunto S E S, x y y pertenecen a S. Para el ejemplo de la figura 2.5,1, la relacin obtenida podra describirse como "tiene el mismo color que". El siguiente teorema muestra que.esta relacin siempre es reflexiva, simtrica y transitiva.TEOREMA 2.!5.1 .

,

Larelaci6n R del ejemplo 2::.2 es una relacin de equivalencia sobre [1,2,3,4,5, 6} de. bido al teorema 2.5.1. Tambin podemos verificar directamente q R ex ',. ca y transitiva. ue es re exiva, simetnLa digrfica de la relacin R del ejemplo 2.5.2 aparece en la fzura 2 5" De R ftex . '" . .-. nuevo ve rnos que ~~ re ~X1va (eX1~te un.l~o en cada vrticeJ, simtrica (para cada arista dirigid~ de u a w, tambien existe una ansta dirigida de w a v) y transitiva (si existe una arista diriad d . diri e- a e, ayy unaansta gida dey a z, entonces existe una arista dirigidadex a z), O

Sea S una particin de un conjunto X. Decimos que x R y si para algn conjunto S en S; x y y pertenecen a S. Entonces R es reflexiva, simtrica y transitiva.

"

J Demostracn, Sea r E X. Porta definicin de particin; x pertenece a algn miembro S de 11 s. As, x R x y R es reflexiva. U Supongamos que x Ry. Entoncesxy y pertenecen a algn conjuntoS E S. Como y y ,1 x pertenecen a S, y R x y R es simtrica. Por ltimo, supongamos que x R y YY R z. Entonces x y y pertenecen a algn conjun- _ ~ to S E S YYYz pertenecen a algn conjunto TEs. Como y pertenece exactamente aun ~ miembro de S, se debe cumplir que S = T. Por lo tanto, x y z pertenecen a S y x.R z. Hemos _ mostrado que R es transitiva.EJEMPLO 2.5.2

4

o

FIG URA 2.5.2

La digrfica de la relacin del ejemplo 2.5.2.

EJEMPLO 2.5.5

Consideremos la relacin Consideremos la particin

1'1t,,',)~.

el".~~1

r."').I\'!'~

5= {[1,3,S,}, [2,6}, [4}}

R = {(1, 1), (1,3); (1,5), (2, 2), (2, 4), (3, 1), (3, 3), (3, 5), (4, 2),(4,4), (5,1), (5, 3), (5, 5)}

deX = [1,2,3,4, S, 6}. Larelaci6n R sobre X dada por elteorema 2.5.1 contiene los pares ordenados (1, 1), (1, 3) Y (1, 5), pues [1,3,S} est en s. La relacin completa es R = {(l,l), (1, 3), (1, 5), (3,1), (3, 3), (3, 5), (5,1), (5, 3), (5, 5),~n~~~n~~~~}.

,

O

t.-..,

.~~

.:"~)

..

IL."

:,

Sean S YR como en el teorema 2.5.1. Si S E S, podemos considerar a los miembros de S como equivalentes, en el sentido de la relacin R. Por esta razn, las relaciones que son reflexivas, simtricas y transitivas se llaman relaciones de equivalencia. En el ejemplo de la figura 2.5.1, la relacin es "tiene el mismo color que"; por lo tanto, equivalente quiere decir "tiene el mismo color que". Cada conjunto en la particin.consta de todas las bolas de un color particular.DEFINICION 2.5.3

sobre [1,2,3,4, S}. R es reflexiva pues (1, l), (2, 2), (3, 3), (4, 4), (5,5) E R. R es simtrica, pues SIempre que (x, y) est en R, (y, x) tambin est en R. Por ltimo, R es transitiva pu:sslempre que (r, y) y (y, z) estn en R, (x, z) tambin est en R. Como R es reflexiva, sirnetnca y transitiva, R es una relacin de equivalencia sobre [ 1, 2, 3, 4, 5). OEJEMPLO 2.l:i.6

La relacin R del ejemplo 2.4.4 no es una relacin de equivalencia, pues R 00 es simtrica.OEJEMPL.O 2.5.7

~"'\ ~ 11.

., ....,-" ....~

","

Una relacin que sea reflexiva, simtrica y transitiva sobre un conjunto X es una relacin de equivalencia sobre X.

Larelacin R del ejemplo 2.4.5 no es una relacin de equivalencia, pues R no es reflexiva ni transltlva.O

''':)

106

CAPITULO

21

EL LENGUAJE DE lJ.S MATEMTICAS

2.5 I

RELACK>NE5 DE EQUIVALENCIA

107

EJEMPLO .2.5.8

EJEMPLO 2.5.12

'

La relacin R del ejemplo 2.4.15 es una relacin de equivalencia, pues R es reflexiva, simtrica y transitiva. O Dada una relacin de equivalencia sobre un conjunto X, podemos separar a Xagrupando los miembros de X relacionados entre ellos. Los elementos relacionados pueden pensarse como equivalentes unos con otros. El siguiente teorema proporciona los detalles.

Lasclases de equivalencia aparecen con claridad en la digrfica de una relacin de equivalencia.Las tres clases de equivalencia de la relacin R del ejemplo 2.5.2 aparecen en la digrficade R (que aparece en la figura 2.5.2) como las tres subgrficas cuyos vrtices son (1,3,5), {2, 6} Y{4}. Una subgrfica G que representa a una clase de equivalencia es una subgrfica ms grande de la digrfica original, con la propiedad de que para cualesquiera vrtices v Y w en G, existe una arista dirigida de v a w. Por ejemplo, si v, w E {I, 3, 5}, existe una arista dirigida de v a w. Adems, no pueden agregarse vrtices al, 3, 5 de modo que elconjunto de vrtices resultanle tenga una arista dirigida entre cada par de vrtices. O

Sea R una relacin de equivalencia sobre un conjunto X. Para cada a E X. sea [a] = {xEX Entonces

I xRa}.

EJEMPLO 2.5.13

5=es una particin d/X.

{[a]

I a E X}

Existen dos clases de equivalencia para la relacin de equivalencia del ejemplo 2.5.5, a

saber,[1] = [3]

= [5] = {I,3,5},

[2]

= [4] = {2,4}.

o

Demostracin. Debemos mostrar que cada elemento de X pertenece a exactamente un miembro de 5. Sea a E X. Como a R a, a E [a]. As, cada elemento en X pertenece almenas a un elemento de 5. Ahora debemos mostrar que cada elemento deX pertenece a exactamente un miembro de 5; es decir, six.E Xy x E [a]n[b], entonces [a] = [b). (2.5.1)

EJEMPLO .2.5. 14

Lasclases de equivalencia para la relacin de equivalencia del ejemplo 2.4.15 son[a]

= {a},

[b]

= lb},

[c]

= {c}.

o

Primero mostramos que sia R b,entonces [a] = lb]. Supongamos queaR b. Sea x E [a]. Entonces x R a. Como a R by R'es transitiva, x R b. Por lo tanto, x E [b] Y{a] ~ lb]. El argumento para mostrar que [b] ~ [a] es igual al ltimo argumento, pero cambiando los pa- 1 peles de a y b. As, [a] = lb]. Ahora demostraremos (2.5.1). Supongamos quex E Xy x E [a]n[b]. EntoncesxRa y x R b. Nuestro resultado anterior muestra que [x] = [a] y [x] = lb]. As, [a] = lb]. iDEF!:-.l!ClON 2-S.l0

EJEMPLO 2.5..1 S

SeaX = (1,2, ... , lO). Decimos quex R y si 3 divide ax - y. Podemos verificar rpidamenteque la relacin R es reflexiva, simtrica y transitiva. As, R es una relacin de equivalenciasobre X. Ahora determinaremos Jos miembros de las cl~ses de equivalencia. La clase de equivalencia[1] consta de todas las x talesque x R l. As, . [1] = (x E X

Sea R una relacin de equivalencia sobre un conjunto X. Los conjuntos [a] definidos en el teorema 2.5.9 son las clases de equivalencia de X dadas por la relacin R.EJEMPLO 2.5. 1 1 _

I 3 divide ax -

l) = {l, 4, 7, lO}.

.ar-fIIt"~

"[1]= {1.3.5}.

Ele manera anloga,[2] = (2,5,8)[3]= {3,6,9}.

Consideremos la relacin de equivalenciaR del ejemplo 2.5.2. La clase de equivalencia [1] que contiene a 1 consta de todas las x tales que (x. 1) E R. Por lo tanto,

E-'los tres conjuntos separan a X. Observe que [1](J

Las dems clases de equivalencia se determinan de manera similar: [3]

= [4] = [7] = [10],

{2] = [5]

= [8],

[3]

= [6] = {9].o

= [5] = {l, 3, 5},

[2]

= [6] = {2.6},

[4]

= (4).

c--fIt"'. e~ ~

Para esta relacin, equivalencia es "tiene el mismo residuo al dividir entre 3".

...~----_._--

e-

--------------------------

.~--------.-

108

CAPITULO'2lEL LENGUAJE DE LAS MAT'EMTICAS

2.51

RELACIONES DE EQUIVALENCIA

109

Concluimos esta seccin demostrando un resultado especial que necesitaremos posteriormente (vanse las secciones 4.2 y 4.4). La demostracin se ilustra en la figura 2.5.3.X~-----r-----.------r------.

En los ejercicios 15-17, sean X = [1,2,3, 4, 51, Y = (3. 4) Y e = (1, 3). Defina la relacin R sobre P(X), el conjunto de todps los subconjuntos de X, como

AR Bsi Y slo siA U Y= B U Y.

x,

(r elementos)

15. Muestre que R es una relacin de equivalencia.

16. Enumere los elementos de [C],laclase de equivalencia que contiene a C.

Ixl= rkFIGURA 2.5.3

17. Cuntas clases de equivalencia distintas existen?18. Sea

La demostracin del teorema 2.5.16.

X = (San Francisco, Pittsburgh, Chicago, San Diego, Filadelfia, Los ngeles}. Defina una relacin R sobre X como x R y si .r y )' estn en el mismo estado. (a) Muestre que R es una relacin de equivalencia. (b) Enumere las clases de equivalencia de X. 19. Muestre que si R esuna relacin de equivalencia sobre X, entonces dominio R

I

TEOREMA Z.S..I6 .

Sea R una relacin de equivalencia sobre un conjuntofinito X. Sicada clase de equivalencia tiene r elementos, entonces existen 1X \ / r clases de equivalencia. Demostracin. Sean X I / X2 , j untos separan a X,

,XlaS distintas clases de equivalencia. Como stos con-

= rango R = X.

de donde se sigue la conclusin.~~~

20. Si una relacin de equivalencia tiene slo una clase de equivalencia, cmo debe verse dicha relacin?

~

Si R es una relacin de equivalencia sobre un conjunto X = k.cmo debe verse dicha relacin? L~ ;e~J'" kQ::,e.. ~ _'i91J>---~...('_ 'C1\.L""'~

yIxl IR

EjerciciosEn los ejercicios 1-8, determine si la relacin dada es una relacin de equivalencia sobre (1, 2, 3, 4, 51.Si la relacin es una relacin de equivalencia, enumere las clases de equivalen- cia. (En los ejercicios 5-8, x, y E(1, 2, 3,4,51)

22. Proporcione un ejemplo de una relacin de equivalencia sobre (1, 2, 3, 4, S, 6) con exactamente cuatro clases de equivalencia, enumerando sus pares ordenados.

Cuntas relaciones de equivalencia existen sobre el conjunto {1, 2, 31? ;. b+c.

24. SeaX = (1,2, ... , IO]. Defina una relacin R sobre X x Xcomo (a, b)R(c,d) sia + d =(a) Muestre que R es una relacin de equivalencia sobre

1. ((1, l), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1)12. ((1,1), (2, 2), (3, 3), (4, 4), (S, 5), (1, 3), (3, l), (3, 4), (4, 3) 1 3. ((l,l), (2, 2), (3, 3), (4, 4))

X x X.

(b) Enumere un miembro de cada clase de equivalencia de X x X.

(g;seax = (1,2, ... , ID}.Defina una relacin R sobre X x X como (a, b) R (e, d) siad = be.

4. ((1,1),(2,2),(3,3),(4,4),(5,5),(1,5),(5,1),(3,5),(5,3),(1,3),(3,1) 5. ((x,y)11:S;x:S;5,I:S;y:S;5)6. ((x,y) 14divideax - y}

y; Enumere un miembro de cada clase de equivalencia de X x X.t) Describa la relacin R en trminos familiares.26. SeaR una relacin reflexiva y transitiva sobreX. Muestre que R n R- I es una relacin.de equivalencia sobre X.

y6

Muestre que R es una relacin de equivalencia sobre X x X.

7. ((x,y) 13divideax+ yJ8. ((x,y)lxdividea2-ylEn los ejercicios 9-14, enumere los miembros de la relacin de equivalencia sobre (1, 2, 3, 4) definida mediante la particin dada (como en el teorema 2.5.1). Adems, determine las clases de equivalencia [1], [2J, (3] Y [4].

@

Sean R 1 YR 2 relaciones de equivalencia sobre X.

JI'!

,!.A

Muestre que R1 n R2 es una relacin de equivalencia sobre X. Describa las clases de equi valencia de R I n R~ en trminos de las clases d~ eQ~i valencia de R1 Y las clases de equivalencia de Rr [-de> J't:.IY 11 x

9. ((I,2},(3,4})11. ((I), (2). (31. (4))

10. (( 1 1, (2). (3, 4J)12. [(I,2,3), (4lJ 14. ((11, (2,4), (3})

J"j

\';":13

13. ((I,2,3,4}1

28. Suponga que 5 es una coleccin de subconjuntos de un conjunto X y X = U 5. (No suponemos que la familia 5 es ajena por pares.) Definimos: x R y si para algn conjunto S E S, x y y estn en S. Es R necesariamente reflexiva, simtrica o transitiva?

.l

110

CAPITULO

21 EL LENGUAJE DE LAS MATEMATICAS

y

!(0,1) . - - - -..... (1,1)

29. Sea S un cuadrado unitario. incluyendo el interior. como muestra la figura anexa. De. fina una relacin R sobre S como (x.y)R (x',y').si (x = x'y y = y] o (y = y'y x = Oy x'= I)o(y=y'yx= lyx'=O). (a) Muestre que R es una relacin de equivalencia sobre S. (b) Si los puntos en la misma clase de equivalencia se pegan, cmo describira la fi. gura formada? 30. Sea S un cuadrado unitario. incluyendo el interior (como en el ejercicio 29). Defina u?a relacin 'R' sobre S como (x, y) R' (x', y] si (x = x'y y = y] o (Y = y'y x = OYx = I)o(y= y'yx= I yx'= O)o(x=x'yy = Oyy'= I)o(x =x'yy= I Yv'=CuaI i~~~~~es~~:. :;;~'~S:!., ""o;;:;;.;:;ri'i"';}:;",;;f

"'cO1ciden'.:)EStoo;tambin es. cierto! Hemos. detnostrado:que Res" una'elacin..ae,t

~i!:en:~~~1;~1;b.~~~:~~i~f;;t:,i';~,' ';~~mentos~ycuntelosen forma ' . '-:;,. ,;, '/::~,: ' ,,"

)~,,~~~~~.~\~~:-;que ~~~~},~~;,;,i\(j::;Jth;'t,W~)~

,., .

t:i

;'i.!,\ti:';Co~deremos;eIFblemde.emimeraJiw.~de,~ c~~eq ..1 JellClll. Las,I6.cadenasde.euatro bItS!ytenumeradaS determinan !a&,l6clases,de ;,.; I

:':'OOOldeterminaiaclased~~uivalenciaqueconsta.detcidaslas.cdenasdeochobits":::.; \q~ooDi_!~OOOr~Yiassucesivaniente"Asf;~un!~bm~;1

:ltadetoclas'~cildenas,de.Oc1lo' bits que,: comienzan eonoooo;, la segundaCatfenj;\~

La.;'primeiacadena 0000 determina Iac!aSe.(Ieiequivalenclaiquecons-:;. i

;~cIase,de,equvalencia..~Iollel:eSitamosgregaralgunacadenade~bits~unai~

En Ios}enguajesdeprogramacin.lousuaI:esq~s6lociertlj ,,,~ ,los nombres deI~~luiablsy'loSirini~~(deSdeerput~ae:~,ti~\j . co.se,llaman identijic~s)sonsignifiCatiVos.: .Porejemp~.e1l;ellenguaje depro'-':'-~ gramacinC,: slo lbs primeros 31 caracteres de losidentificadOreSsoosignifiCativos.i. " el sistema puede considerarlos idnticos.,>"~._>'"

~~l~:~r~E';'::i~:lj;~!~'kf,'';",,; '. '. ."."" , ,.. .'.".; E.: 'c;., '.,:.'

"i~laScadenasea~rm~~:)t:.'.'~l;;t{~::~~.~:::~r~:~';~,,~;,\j:t

EstoquieredCcir:~$idosidentificadores.~enzanoon losmsmcs-Sl.caracteres, ' , ";,~;,~ .c:' ;,")onga que ges una funcin de A en un conjunto X con la propiedad de que si x R Y. entonces g(x) = g(y). Muestre que . .h([x])

53.f(x.y)=x+y. X={1.2 } 54.f(x.y)=x-y. X={1,2, } '.. 55. fes, r) = sr,Xesel conjunto de cadenas sobre {a. 56.f(x,y)=xfy. X=\{0.1.2 .... } 57. f(x.y)=i1+y2-xy, X= {1.2... }

bl'

=g(x)

* 37.o(:

define una funcin del conjunto de clases de equivalencia de A en X. [Lo que hay que mostrar es que h asigna un valor de manera nica a [x]: es decir, que si [x] = [y], en. tonces g(x) = g(y).}

En los ejercicios 58 y 59, proporcione un ejemplo de un operador unario (diferente de f (x) = x, para toda x) sobre el conjunto dado.

....~

Seafuna funcin deX en Y. Muestre quefes uno a uno si. y slo si. siempre que g sea una funcin uno a uno de cualquier conjunto A en X,f o g es uno a uno. 38. Seafuna funcin de X en Y. Muestre que f es sobre Y si, y slo si. siempre que g sea una funcin de Y sobre cualquierconjunto Z. g of es sobre Z. Sea U un conjunto universal y sea X ;;; U. Defina

58. {.... -2. -1, O.I,2.... } 59. El conjunto de cadenas sobre {a. b} 60. Muestre que sif es una funcin uno a uno y sobre de X en Y. entonces{(y, x) I (r, y) Ej}

~~-

C {lOx(x)=

si xE X

si x e X.

Cx es la funcin caracterstica de X (en U). 39. MuestrequeCxny(x) = CxCx)Cy(x) para toda x E U. 40. Muestre que Cx u y(x) = CxCx) + Cy(x) - CxCx)Cy(x) para toda x E U. 41. Muestre que Cs Ir) = l. - Cx(x) para toda x E u. 42. MuestrequeCX_y(x) = CxCx) [1 - Cy(x)] para toda x E U. 43. Muestre que si X ~ Y. entonces Cxlx) :5 Clx) para toda x E U. 44. Muestre que CXUy(x) = Cxlx) + Cy(x) para toda x E tr siy slo si X n y = 0. 45. Determine una frmula paraCX~y' (X Yes la diferencia simtrica de X y Y. Ladefinicin aparece antes del ejercicio 61. seccin 2.1,) ,

es un funcin uno a uno y sobre de Yen X. 61. Cmo podemos determinar con rapidez si una relacin R es una funcin. examinando la matriz de R (con respecto de algn orden)? 62. Sea A la matriz de una funcinj'de Xen Y (con respecto al orden dado de Xy Y). Qu condiciones debe satisfacer A para que f sea sobre Y? 63. SeaA la matriz de una funcinfdeX en Y (con respecto del orden dado deXy Y). Qu condiciones debe satisfacer A para quefsea uno a uno? En los ejercicios 64-66, escriba "verdadero' si la afirmacin es verdadera para todos los nmeros reales. Si es falsa, proporcione un contraejemplo.

,(I)r..~.

-~

eae'r.

64. fx+31=fxl+365. 66.

fx + y1= rx1+ fy1 Lx + yJ = Ld+ ry1

le-

S

~_

1

..

-

136

CAPITULO

21

EL LENGUAJE DE LAS MATEMTICAS

CAPfTULO

21

EL LENGUAJE DE LAS MATEMTICAS

137

67. Muestre que si n es un entero impar.

i:::'A

CONCEPTOS BSICOS

DEL CAPTULO Seccin 2.1 68. Muestre que si n es un entero impar,Producto cartesiano de X y Y:Xx Y= (x,y)

rn2l =-4-' n +3 14Z

Conjunto: cualquier coleccin de objetos Notacin para conjuntos: (x x tiene la propiedad P] Ix! : el nmero de elementos en el conjun-

I xEX,yE YIXn

I

Producto cartesiano de XI' X Z' - ,X.:

X, xX2 xSeccin 2.2

X

El 1 de enero del ao x se presenta en el da de la semana mostrado en la s~m na del rengln

ioxx E X: x es un elemento del conjunto X x rt: X: x no es un elemento del conjunto X Conjunto vaco: 0 o ( } X = Y, donde X y Y son conjuntos: Xy y tienen los mismos elementos Y, X es un subconjunto de Y: todo X elemento de X es tambin elemento de Y X es un subconjunto propio de Y: X Yy X,., Y P(X), el conjunto potencia de X: conjunto de todos los subconjuntos de X

= {(a" a z" .. ,a.)

! Q; E X;T-

y=

(x + l~ 1-1 ~J + I~ !I mod 7 4 " lOO L 400 J)e

en la "siguiente labia (vase [RitterJ).

e

yO

1 de enero

Ao no bisiesto

Ao bisiesto

Domingo Lunes Martes Mircoles Jueves Viernes Sbado

enero, octubre abril, julio septiembre, diciembre junio febrero, marzo, noviembre agosto mayo

enero, abril, julio septiembre, diciembre . junio marzo, noviembre febrero, agosto mayo octubre

1

2

-~t

I

1

e

Sucesin: lista donde se toma en cuenta el orden ndice: en la sucesin [s.}, n es el ndice Sucesin creciente: s. :$ S." para toda n Sucesin decreciente: sn ~ s para toda n Subsucesin S.k de la sucesin (snl Notacin de suma o sigma:

!P(X) I =2 1x lenXoY

.

"

La,- =a m +a m + l + +ani=m

.

X U Y, X unin Y: conjunto de elementos Unin de una familia sde conjuntos: us= (x xEXparaalgnXEsI X n Y, X interseccin Y: conjunto de _ elementos en X y Y Interseccin de una familia S de conjuntos: ns = {x 1,x E X para toda X E SI Conjuntos ajenos X y Y: X n Y = 0 Familia de conjuntos ajenos por pares' X - Y, diferencia de X Y Y. complemento relativo: conjunto de elementos en X pero no en Y f:onjunto universal. universo X, complemento de X: U - X, donde U es un conjunto universal Propiedades de conjuntos (vase el teorema 2.1.8) Leyes de De Morgan para conjuntos:

34

Notacin producto:

56

I

rrni=m

a =

Gm

'a"'+1 an

Los mesescon viemes 13 en el ao x se determinan en el rengln y de la columna adecuada. 69. Determine los meses con viernes 13 en 1945. 70. Determine los meses con viernes 13 en este ao. 71. Determine los meses con viernes 13 en el ao 2000. 72. Sea X el conjunto de sucesiones con dominio finito. Defina una relacin R sobre X cornos R tsi dominio s \ = dominio t\ y, si el dominio de s es (m, m+ 1, ... m+kl y el dominio de t es {n, n + 1, ... ,n + kl. entonces sm+; = t.+; para i = O,... .k:

I

i

(a) Muestre que R es una relacin de equivalencia. (b) Explique con palabras lo que significa que dos sucesiones en X sean equivalentes bajo la relacin R. (e) Una sucesin es una funcin y porlo tanto es un conjunto de pares ordenados. Dos sucesiones son iguales si los dos conjuntos de pares ordenados son iguales. Compare la diferencia entre dos sucesiones equi valentes en X y dos sucesiones iguales en X./::::A

Cadena: sucesin finita Cadena nula, 1..: cadena sin elementos X*: conjunto de todas las cadenas sobre X incluyendo la cadena nula ' X': conjunto de todas las cadenas no nulas sobre X Longitud de la cadena a, nmero de elementos en a Concatenacin de cadenas a y {J, a{J: a seguida de {J.

Ial:

Seccin 2.3Sistema numrico decimal Sistema numrico binario Sistema numrico hexadecimal Base de un sistema numrico Conversin de binario a decimal Conversin de hexadecimal a decimal Conversin de decimal a hexadecimal Suma de nmeros binarios Suma de nmeros hexadecimales

(A UB)

=A nE,

NOTAS

(AnB)=AUE

La mayor parte de la bibliografa general en matemticas discretas se refieren a los temas de este captulo. [Halmos; Lipschutz; y Stoll] son recomendables para el lector que desee estudiar teora de conjuntos, relaciones y funciones con mayor detalle. {Codd; Date; Kroenke; y Ullman] son referencias recomendables acerca de las bases de datos en general y el modelo relacional en particular.

Particin de X: una coleccin S de subconjuntos no vacos de X tales que todo elemento en X pertenece exactamente a un miembro de S Par ordenado: (x, y)

138

CAPiTULO 2

I EL. L.ENGUAJE DE Lo'5 MATEMATICAS

CAPITULO

21 EL. LENGUAJE

DE LAS MATEMATICAS

139

Seccin 2.4 Relacin binaria de X en Y: conjunto de pares ordenados (x, y), con x E X,)' E Y Dominio de una relacin binaria R:{x

I (x,y)ER)

Si A I es la matriz de la relacin R I Y A 2 es la matriz de la relacin A 2, la matriz de la relacin R2 o R, se obtiene reemplazando cada trmino distinto de cero en la matriz producto A ,A2 por l. Seccin 2.7 Relacin n-aria: Conjunto de n-adas Sistema de administracin de bases de datos Base de datos relacional Clave Consulta_Selec~n

~

AUTOEVALUACIN DEL CAPTULO

Rango de una relacin binaria R: {y (x, y) E R}

I

Digrfica de una relacin binaria Relacin reflexiva R sobre X: (r, x) E Rpara toda x E X Relacin simtrica R sobre X: para toda x, y E X, si (x, y) E R, entonces(v,x)ER Relacin antisimtricaR sobre X: para toda x, y E X, si (x, y) E R Y x "., y, entonces (y, x) f1. R Relacin transitiva R en X: para toda x, y, z E X, si (x, y) Y (y, z) estn en R, entonces (x.z) E R Orden parcial: relacin que es reflexiva, antisimtrica y transitiva Relacin inversa R-': {(y,x) (x, y) E R}

Seccin 2.1 1. SiA = {1,3,4,5,6,7j,B= {x xesunenteropar),C= {2,3,4,5,6},determine (A nB) - c. 2. Si X es un conjunto y = 8. cuntos miembros tiene P(X)? Cuntos subconjuntos propios tiene X? ' 3. Si A U B = B, qu relacin debe haber entre A y B? 4. Son iguales los conjuntos

I

11. e, _eI~'

t.'.

Ixl

e-

{3, 2. 2), Explique.

Ix Ixes un entero y 1 x (5) 1) es verdadero, por lo que asignamos x a b (5). En la lnea 3, e > x (3 > 5) es falso, por lo que no hacemos nada. En este momento, x es 5, el mximo de a, b y c.

,142

1.

http://libreria-universitaria.blogspot.com3.21NOTACION PARA LOS ALGORITMOS

CAPITULO 3 I ALGORITMOS

145

Supongamos que

a = 6,

b=I,

e=9.

En la lnea 1, a x le asignamos el valor de a (6). En la lnea 2, b > x (1 > 6) es falso, por lo que no hacemos nada. En la lnea 3, e > x (9 > 6) es verdadero, por lo que asignamos 9 a x, En este momento, x es igual a 9, el mximo de a, by e. Observemos que este ejemplo de algoritmo tiene el conjunto de propiedades establecidas al principio de esta seccin. . Los pasos de un algoritmo deben establecerse con precisin. ~os pasos del eJe~plo anterior tienen la precisin como para poder escribirse en un lenguaje de programacion y ejecutarse en una computadora. Dados los valores de entrada, cada paso intermedio de un algoritmo produce un Ee: sultado nico. Por ejemplo. dados los valores

demasiado por los signos de puntuacin, las letras maysculas y minsculas, las palabras especiales, etc., cualquier versin de seudocdigo es aceptable, siempre que sus instrucciones no sean ambiguas y tenga la forma, aunque no la sintaxis exacta, del seudocdigo descrito en esta seccin. Como primer ejemplo de seudocdigo, escribiremos de nuevo el algoritmo de la seccin 3.1, que determina el mximo de tres nmeros.. ALGORITMO 3..2. I

Determinacin del mximo de tres nmeros

Este algoritmo determina el mximo de los nmeros a, by e. Entrada: Salida: Tres nmeros a, b y e

x, el mximo de a, b y e

a

= 1,

b = 5,

e

= 3.

1. procedure" max(a, b, e)

en la lnea 2 del ejemplo, se asigna 5 a x sin importar la persona o mquina que ejecute el algoritmo. Un algoritmo termina despus de un nmero finito de pasos que responden la pregunta solicitada. Por ejemplo, el algoritmo del ejemplo se detiene despus de tres pasos y proporciona el mximo de los tres valores dados. . . . Un algoritmo recibe entradas y produce salidas. El a1gontmo del ejemplo recibe.co-. mo entrada, los valores a, b y e, y produce, corno salida, el valor x. Un algoritmo debe ser general. El algoritmo del ejemplo puede determinar el mximo valor de cualesquiera tres nmeros. Nuestra descripcin de un algoritmo es suficiente para las necesidades en este libro. Sin embargo, es posible dar una definicin matemtica ms precisa de "algoritmo" (vanse las notas del captulo lO). En la seccin 3.2 presentaremos una manera ms formal de especificarlos algorie > mos y daremos ms ejemplos de stos.~~~

2. 3.4.

5.6.

x:=a ir b > x then I! si'b es mayor que x, actualizar x x:=b ir e> x then II si e es mayor que x, actualizar x x:= ereturn(x)

--7.

8. "ndmaxNuestro algoritmo consta de un ttulo, una breve descripcin del algoritmo, la entrada y salida del algoritmo, y los procedimientos con las instrucciones del algoritmo. El algoritmo 3.2.1 tiene un solo procedimiento. Para una fcil referencia a las lneasindividuales dentro de un procedimiento, a veces las numeraremos. El procedimiento del algoritmo 3.2.1 tiene ocho lneas numeradas. La primera lnea de un procedimiento tendr la palabra procedure, despus el nombre del procedimiento y, entre parntesis, los parmetros del procedimiento, los cualesdescriben losdatos, variables,arreglos,etc., que se encuentran disponiblespara el procedimiento. En el algoritmo 3.2.1, los parmetros del procedimiento son los nmeros a, by e. La ltima lnea de un procedimiento tiene la palabra end seguida por el nombre del procedimiento. Entre las lneas procedure y end se encuentran las lneas ejecutables del procedimiento. Las tneas 2-7 son las lneas ejecutables del procedimiento en el algoritmo 3.2.1. Al ejecutar el procedimiento del algoritmo 3.2.1, en la lnea 2, asignarnos x aa. En la lnea 3, comparamos b con x. Si b es mayor que x, ejecutamos la lnea 4

Ejerciciosl. Escriba un algoritmo que determine el menor elemento entre a, b y e. 2. Escriba un algoritmo que determine el segundo elemento ms pequeo entre a, by e. Suponga que los valores de a, b y e son distintos. 3. Escriba el mtodo usual, el que se ensea en matemticas elementales, para la suma de dosenteros positivos como un algoritmo. 4. Consulte en el directorio telefnico las instrucciones para hacer una llamada de larga distancia. Cules propiedades de un algoritmo (precisin, unicidad, carcter finito, entrada, salida, generalidad) tienen estas instrucciones? Cules no?

x:=bpero si b no es mayor que x, pasamos a la lnea 5, en la cual comparamos e con x. Si e es mayor que x, ejecutamos la lnea 6

x :=e

3.1

NOTACIN PARA LOS ALGORITMOS

Aunque a veces el lenguaje comn es adecuado para especificar un algoritmo, muchos investigadores en matemticas y ciencias de la computacin prefieren un seudocdigo, por su precisin, estructura y universalidad. El seudocdigo recibe ese nombre pues se asemeja al cdigo real (programas) de lenguajes como Pascal y C. Existen muchas versiones de seudocdigo. A diferencia de los verdaderos lenguajes de computacin, que se preocupan

pero si e no es mayor que x, pasamos ala lnea 7. As, cuando llegamos ala lnea 7, x contendr correctamente al mximo de a, b y c. En la lnea 7 regresamos el valor de x, que es igual al mximo de los nmeros a, b y e, a quien haya llamado al procedimiento, y concluimos. El algoritmo 3.2.1 ha encontrado en forma correcta el mximo de los tres nmeros. En un seudocdigo.las palabrasprocedure. usoen ingls.

ir. then, etc., puedenescribirse en espaol,aunquese ha hecho el

t46

CAPtT'uLO

3 I

ALGORITMOS

3.21

NOTACIN PA.RA LOS AL.GORfTMOS

En general, en la estructura if-tbenifptben accinsi la condicin p es verdadera, se ejecuta accin y el control pasaa la proposicin posterior a accin. Si la condicin p es falsa, el control pasa. directamente a la proposicin posterior a accin. Una forma alternativa es la estructura if-tben-else

147

whilepdo accin en donde accin se ejecuta varias veces, mientras p sea verdadera. El cuerpo de un ciclo es accin. Como en la proposicin if, si accin consta de varias proposiciones, las delimitamos mediante las palabras begin y end. Ilustrarnos el ciclo while en el algoritmo 3.2.2, el cual determina el valor mximo en una sucesin. Como en el algoritmo 3.2.1, recorremos los nmeros uno por uno y actualizamos la variable que contiene al mximo. Utilizamos el ciclo while para recorrer los nmeros.ALGORI'ThlO 3_2.2

ifptben accin I

else

M~2

I

r

Determinacin del elemento mximo en sucesin finita

UIUl

f si la.condicin p es verdadera; se ejecuta aCCn I (perono'at'l'in 2)y el control pasaala < proposicin posterior a accin 2. Si la condicin pes falsa,.seejecutaaccln 2 (pero no accin 1) Y el control pasa a la proposicin posterior a accin 2. Como se muestra, utilizarnos las sangras para identificar las proposiciones que conforman accin. Adems, si accin consta de varias proposiciones, las delimitamos con las palabras begin y end. Un ejemplo de una accin con varias proposiciones en un enunciado if es

Estealgoritmo determina el nmero mximo en la sucesin s" s2" .. , s. Esta versin utiliza un ciclo while.Entrada: Salida:

La sucesin s" s2' ... .s; y la longitud n de la sucesinlarge, el mximo elemento en esta sucesin

ifx;:"Othen begin

l. procedure find_large(s, n) 2. large := s, 3. 1:= 2 4. whilel$ndo5. 6. begin if Si> large then large := Si // se ha encontrado un valor ms grande

x:=x.-l a:= bend Las dos diagonales // indican el inicio de un comentario, el cual se extiende hasta el final de la lnea. Un ejemplo de comentario en el algoritmo 3.2..1 es // si b es mayor que x, actualizar x Los comentarios ayudan al lector a entender el algoritmo, pero no se ejecutan. La proposicin return(x) concluye un procedimiento y regresa el valor de x a quien lIarn al procedimiento. La proposicin return [sin (x) slo termina un procedimiento. Si no existe una proposicin retum, el proceso termina justo antes de la lnea end. Un procedimiento que contiene una proposicin retum(x) es una funcin. El dorninio consta de todos los valores vlidos para los parmetros y el rango es el conjunto de valores que puede regresar el procedimiento. Al utilizar un seudocdigo. utilizaremos las operaciones aritmticas comunes +. -". * (para la multiplicacin) y /, as como los operadores de relacin =,;of, , $,;:" ylos operadores lgicos and, or y not. Utilizaremos = para denotar el operador de igualdad)" : = para la asignacin. A veces utilizaremos proposiciones menos formales (por ejemplo"Elegir un elemento x en S') si lo contrario pudiese esconder el significado. En general,las soluciones de los ejercicios que requieren algoritmos deben escribirse como en la forrns ilustrada en el algoritmo 3.2.1. ,

+c

7. 8..

1:= 1+ I

end 10. return(large) 11. end findLarge Seguiremos el algoritmo 3.2.2 cuando n = 4 y s es la sucesin

9.

s,=-2,

s2=6,

s3=5,

s,=6.

En la lnea 2 hacemos large igual a s,; es decir,large tiene el valor -2. Despus, en la lnea 3. asignamos 2 a l. En la lnea 4 probamos si I $ n; en este caso, vemos si 2 $ 4. Como esta condicin es verdadera, ejecutamos el cuerpo del ciclo while (lneas 5 a 9). En la lnea 6 probamos si s. > large; en este caso, probarnos si S2 > large (6 > -2). Como la condicin es verdadera, ejecutarnos la lnea 7; y asignamos 6 a large. En la linea 8, hacemos I igual a 3. Entonces regresamos a la lnea 4. De nuevo verificamos si I $ n; en este caso, verificamos si 3 $ 4. Como esta condicin es verdadera, ejecutamos el cuerpo del ciclo while. En la lnea 6, probamos si Si > large: en este caso, probamos si s, > large (5) 6). Como la condicin es falsa, pasamos a la 1.~7. En la lnea 8, hacemos' igual a4. Entonces regresamos a la lnea 4. Denuevo verificamos si I $ n; en este caso, verificamos si 4 -s 4. Como esta condicines verdadera, ejecutamos el cuerpo del ciclo while. En la lnea 6, probamos si Si > larg~; en este caso, probamos si s, > large (6) 6). Como la condicin es falsa, pasamos a la !fnea7. En la lnea 8, hacemos igual a 5. Entonces regresamos a la lnea 4. De nuevo verificamos si i $ n; en este caso, verificamos si 5 -s 4. Como la condicin -es falsa, concluimos el ciclo while y llegamos a la lnea lO, donde regresamos large (6). Hemosencontrado el mximo elemento en la sucesin.

Las lneas de un procedimiento, que se ejecutanen forma secuencial, por lo general son proposiciones de asignacin, condicionales (if), ciclos, return y combinaciones de so taso Una estructura cclica til es el ciclo while.

=-----------------------------------_ _ _ _ _ _ _ _1.. . . . .

J----..

~

C ..... ~ITULO 31

ALGORITMOS

3.21 ALGOR.ITMO 3.2.4

NOTACION PARA LOS ALGORrTMOS

t49

En el algoritmo 3.2.2 recorrimos una sucesin utilizando la variable i, la cual tom los valores enteros de la n. Este tipo de ciclo es tan comn que con frecuencia se utiliza un ciclo especial, el ciclo for, en vez del ciclo while. La forma del ciclo for es for var := init to limit do accion Como en los casos de los enunciados if y while, si accin consta de varios enunciados, los delimitamos con las palabras begin y end. Al ejecutar el ciclo for, la accin se ejecuta para los valores de var desde init hasta limito Ms precisamente, init y limit son expresiones que tienen valores enteros. La variable var empieza con el valor init. Si var :s; limit, ejecu, tamos accin y luego sumamos lavar. Luego se repite el proceso, hasta que var > limu, Observe que si init > limitoaccin no se ejecutar. Podemos escribir el algoritmo 3.2.2 de la siguiente forma con un ciclo foro

Verificar si un entero positivo es primo

Este algoritmo verifica si el entero positivo m es primo. La salida es true (verdadero) si m

es primo y false (falso) si m no es primo.Entrada: Salida:

m, un entero positivotrue, si m es primo; false, si m no es primo

procedure is_prime(m) for i:= 2 to m -1 do ifm mod i = Othen // i divide am return(false) retum(true) end is_prime El algoritmo 3.2.5 .determina el mnimo primo mayor.que.el entero positivo n y utiliza al algoritmo 3.2.4. Para llamar a un procedimiento que regrese un valor, como el algoritmo 3.2.4, basta llamarlo por su nombre. Para llamar un procedimiento, digamos,proc, que no regresa algn valor, escribimos

Al.GORITMO 3.2:.3

Determinacin del elemento mximo en una sucesin finita. ,

Este algoritmo determina el nmero mximo en la sucesin s,, S2' liza un ciclo foro Entrada: Salida: La sucesin s"S2' '

s. Esta versin uti-

s. y la longitud n de la sucesin

call procip; P2' .... Pt),donde PI' P2' ... , Pt son los argumentos transferidos a proc.

large, el mximo elemento en esta sucesin

1.

2.3. 4.

5.6. 7.

procedurefind_large(s, n) large:= SI fori:=2tondo if Si> large then // se ha determinado un valor ms grande large : Si retum(large) endfind_large

ALGORITMO 3.2.5

Determinar un primo mayor que un entero dado

Este algoritmo determina el mnimo primo mayor que el entero positivo n. . Entrada: Salida:

n, un entero positivom, el menor primo mayor que n

Durante el desarrollo de un algoritmo, con frecuencia es recomendable descomponer el problema original en dos o ms subproblemas. Puede desarrollarse un procedimiento para resolver cada subproblema, despus de lo cual estos procedimientos pueden combinarse para proporcionar una solucin del problema original. Nuestros ltimos algoritmos ilustran estas ideas. Supongamos que necesitamos un algoritmo para determinar el mnimo nmero primo mayor que un entero positivo dado. Ms precisamente, el problema es: Dado un entero positivo n, determinar el mnimo primo p tal que p > n. Podemos descomponer este problema al menos en dos subproblemas. Primero podramos desarrollar un algoritmo para determinar si un entero positivo es primo. Luego podramos utilizar este algoritmo para determinar el mnimo primo mayor que un entero positivo dado. El algoritmo 3.2.4 verifica si un entero positivo m es primo. Slo verificamos si algn entero entre 2 y m - l divide a m. Si determinamos un entero entre 2 y m - I que divida a m, entonces m no es primo. Si no podemos determinar un entero entre 2 y m - l que di vida a m, entonces m es primo. (El ejercicio 17 muestra que basta verificar los enteros encomo posibles divisores.) El algoritmo 3.2.4 muestra que los procedimientoS tre 2 y pueden regresar los valores true (verdadero) o false (falso).

procedure large_prime(n) m:=n+ l while not is_prime(m) do m:=m+ l retum(m) end large_prime Como el nmero de primos es infinito (vase el ejercicio IS), el procedimiento del algoritmo 3.2.5 terminar en algn momento. b:'9t::::::::: n /4+n/4 n+ l

Por tanto, el tiempo del algoritmo 3.5.14 en el caso promedio es Ahora,O(n).

n(l-.i.. '\t(n);5;

2' I/2

As, el tiempo d~1 algoritmo 3.5.14 en el caso promedio esG(n).

1--'-

de modo que ten) = O(n). As, una notacin theta para el nmero de veces que ejecutamos

x:=x+les0(n).

O

Para este algoritmo, los tiempos en el peor de los casos y en el caso promedio son O ambos 0(n).

176

CAPiTULO 3 I ALGORITMOS

3.51AL.GORITMO 3.5. 14

COMPLEJIDAD DE LOS ALGORITMOS

177

Bsqueda en una sucesin no ordenada

peor.de los casos es p.roporcional a un polinomio de grado alto, la solucin del problema podra tardar mucho ~empo. Por fortuna, en muchos casos importantes la cota polinomial uene un grado pequeno. ' n problema que: no tiene un algoritmo con tiempo polinomial en el peor de los cade ejecucin ' para el peor de los casos , de cu al quier . al gontmo . sos , . es . mtratable. El tle,mpo SI existe, que resuelva un problema intratable. es muy largo incluso para tam d ' da modestos. . anos e entra-

Dada la sucesin

?

y un valor key, este algoritmo determina la posicin de key.Si key no-se encuentra, el algoritmo produce como salida O. Entrada: Salida: l. 2. 3. 4. 5.

~

sI' S2'

.

,s.' n y key (el valor buscado)

La posicin de key, o bien. Osi key no se encuentra

6.

procedure linear_search(s, n, key) fori:=ltondo if kev = s. then reiurnd) 1I bsqueda exitosa return(O)./1 bsqueda no exitosa end linear_search

Ciertos problemas-son tan difciles que no disponen de algoritmo alguno. Un problema para el que no hay algoritmo se dice que es irresoluble. Se conoce un gran nmero de problemas que son irresolubles, algunos de ellos con una importancia prctica considerable . . Uno de lospnmeros problemas que se demostr ser irresoluble es el problema de t ., . Dado . . enruna cJO~. un programa arbitrario yun conjunto de entradas, se detendr el programa algun momento? en

Un gran n~ro de problemas solubles tienen un estado hasta ahora indeterminado' se supone que-so~ mtratables, pero esto no se ha demostrado. (Estos problemas pertenecen ala clase NP;. vease los detalles en [Hopcroft).) Un ejemplo de problema soluble que se piensa que es intratable, aunque esto no es claro an, es: '" Dada una coleccin e de conjuntos finitos y un entero positivo k < aI menos k conjuntos mutuamente ajenos?

TABLA

3.5.3

Funciones de crecimiento comunes

Fonna thetat190)6(1glgn) e(lgn) 6(n) e(nlgn) 6(n 2) 6(n 3) e(nm ) 19(m"), m 2: 2 19(n!)

NombreConstante Loglog Logartmica Lineal nlogn Cuadrtica CbicaPolinomial

Exponencial Factorial

tl g=logdebase2; m es un entero no negativo fijo.

En la seccin 3.6 consideraremos un ejemplo ms complejo, el tiempo en el peor de los casos para el algoritmo de Euclides (algoritmo 3.3.8). . Las constantes que se suprimen en la notacin theta pueden ser importantes. Aunque, . para cualquier entrada de tamao n, el algoritmo A requiere exactamente C,n 'unidades de tiempo y el algoritmo B requiere exactamente C~2 unidades de tiempo, para ciertos tamaos de entrada el algoritmo B puede ser superior. Por ejemplo, supongamos que para cualquier tamao de entrada n, el algoritmo A requiere 300n unidades de tiempo y el algoritmo B requiere Srr' unidades de tiempo. Para un tamao de entrada de n S, el algoritmo A requiere 1500 unidades de tiempo y el algoritmo B requiere 125 unidades de tiempo, pr lo que el algoritmo B es ms rpido. Por supuesto, para entradas suficientemente grandes, el algoritmo A es mucho ms rpido que el algoritmo B. Ciertas formas aparecen con tanta frecuencia que tienen nombres especiales, como muestra la tabla 3.5.3. Las formas de la tabla 3.5.3, con la excepcin de 6(n m ) , estn ordenadas de modo que si e(f(n est arriba de e(g (n, entoncesf(n) :5g (n) para todo entero positivo n excepto para un nmero finito. As, si los algoritmos A y B tienen tiempos de ejecucin que sean e(f(n y e(g (n, respectivamente, y si e(f(n)) est arriba de 6(g (n en la tabla 3.5.3, entonces. para entradas suficientemente grandes, el algoritmo A es ms eficiente en tiempo que el algoritmo B. Es importante desarrollar una idea intuitiva de los tamaos relativos de las funciones que aparecen en la tabla 3.5.3. En la figura 3.5.1 hemos graficado algunas de estas funciones. Otra forma de desarrollar una idea de los tamaos relativos de las funciones f (n) en la tabla 3.5.3 es determinar cunto tardara en concluir un algoritmo cuyo tiempo de ejecucin sea exactamente f (n). Para esto, supongamos que disponemos de una computadora que pueda ejecutar un paso en un microsegundo (10- 6 segundos). La tabla 3.5.1 muestra . los tiempos de ejecucin para diversos tamaos de entrada, bajo estas hiptesis. Observe que es factible implantar un algoritmo que requiera 2 pasos para una entrada de tamao n slo para tamaos de entrada muy pequeos. Los algoritmos que requieren n2 o n3 pasos tambin dejan de ser factibles. pero slo para tamaos de entrada relativamente grandes. Adems, observe la drstica mejora resultante al pasar de n2 pasos a n lg n pasos. Un problema que tiene un algoritmo con tiempo polinomial en el peor de los casos se considera un algoritmo "bueno"; la interpretacin de esto es que dicho problema tiene una solucin eficiente. Por supuesto, si el tiempo necesario para resolver un problema en el

Iel. . e . ,(,contlene.

bl del Otros problemas solubles de los cuales no se sabe si sean tratables o no son el td'" proema agen e e ventas viajero y el problema del ciclo hamiltoniano (vase la seccin 6.3).

=

~~~

Ejercicios. seleccione una notacin tbeta

dela labia 3.5.3 para cada expresin en los ejercicios 1-12. 2. 2n 2 + l 4 3n2 + _n 1 l gn 6. 6n 6 +n+48. (6n+I)2

1. 6n +1 3 3. 6n + 12n 2 + I5.2Ign+4n+3nlgn 7.2+4+6+"+2n

9. (6n+4)(l+lgn)

10. (n+l)(n+3)n+212.2+4+8+16+"'+2"

11. (n

2+lgn)(n+l)

n+n2Enlos'ejercICIOS

"

1

3-

15, seleccione una notacin !heta paraf(n)

.

+ g(n).

13. f(n)

= 19(1),

g(n)

= e(n2)= e(n 19n)

14. f(n) = 6n 3

+ 2n 2 + 4, gen)

15. f(n) = 6(nJ/Z),

gen) = 6(n5/2)

En los ejercicios 11>-26, seleccione una notacin !hata entre

19(1),

6(lgn),

e(n),

e(nlgn),

6(n2j,

0(n3 ) ,

t)(2")

o 6(n!)

para el nmero de veces que se ejecuta la instruccin x : = x

+ 1.

IA\

178

CAPiTULO 3

I ALGORITMOS

3.5 I

COMPL.E.JIDAD DE L.OS AL.GORfTMOS

179

16. fori:= lto2ndo x:=x+ I

17. i:= I while i S 2n do begin x:= x + I i:=i+ 2_ end 19. fori:= lto2ndo forj:= 1 tondo x:=x+1 21. fori:~ 1 tondo forj:= ltondo for k:= l. tondo x:= x "-.I__ 23. for i = l"tlrn do forj:=l,toido for k :=1 toj do x:=x+ I

18. fori:=ltondo forj:= I tondo x:=x+ I 20. fori:= I tondo for i> I to Li/2Jdo x:=x + I

l. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

procedure large_small (s, n, large, small) ifn = I then begin large i-e s ; small:= s, return end m:= 2 LnI2J i:= l while i S m - 1 do begin ir Si> Si+ I then intercambiarrr., s,+ 1) i:= 1 + 2_

efII'

.fII~

"

22;- fori:= 1 to n doforj:= 1 tondo fork:= I toido x:=x+ 1

15.16. 17. 18. 19. 20. 21. 22.

endifn>mthen begin ifsm _ , >s.then intercambiar(s.. _ l ' s.) if s" > sm then intercambiar(s.. ,s.) end

___l.

ef'

24.

i> nwhilej ~ 1 do begin fori:= 1 tojdo x:=x+ I j:= lil3J end

25. i:=n whilei ~ Ido begin x:=x+1 i:=Li/2J

,end

23. 24. 25.26. 27. . 28. 29. 30. 31.

small ise s, large : = S2 i:= 3whileism-Ido - begin if Si < small then small :: Si if Si+ , > large then large:=si+1

efA.~

26. i:= nwhilei~

Ido

begin forj:= 1 tondo x:=x+ 1 i:= Lil2J end 27. Determine una notacin theta para el nmero de veces que se ejecuta la instruccin x:=x+ 1. i:= 2 whilei l y quef(n) = e(loga n). Muestrequef(n) = e(lg n). 30. Muestre que n! = O(n").31. Muestre que 2" = O(n!). 32. Suponga que g(n) > o para n = 1,2, .... y para todan.f(n) es distinta de cero. Muestre quef(n) = e(g(n)) si y slo si existen constantes positivas c y c tales que

e~~

large (el elemento msgrande en SI' S2" .. , s.) small (el elemento ms pequeo en sI' S2' ... , s.>

cJg(n)Slf(n)lsc~(n) paralodan= 1,2, .... Determinesi cada afirmacin en los ejercicios 33-42 es verdadera o falsa. Si la afirmacin es falsa, proporcione un contraejemplo. Suponga Que las funciones/' g y h slo toman va. lores positivos. 33. Sif(n) = e(g(n)) y gen) =8(h(n)), entoncesf(n) = eChen~. 34. Sif(n) = eChen~ y gen) =eChen)~, entoncesf(n) + gen) = eChen)). 35. Sif(n) = 8(g(n)), entonces cf(n) = e(g(n)) para toda c oF o. ~. Sif(n) = e(g(n)), entonces 2[(") = 13(2'(". 7. Sif(n) = e(g(n)), entonces 19f(n) = e(lg gen)~. Suponga quef(n) ~ 1 Y gen) ~ 1 para toda n = 1,2, .... 38. Sif(n) = O(g(n)), entonces gen) = Olf(n):

l

2

eti~ ~ (1,~

-57--

_ _ _~------------(II\~

~

1 SO

CAPITULO 3

I

ALGORITMOS

3.51

COMPLEJIDAD DE LOS ALGORITMOS'

181

* 43. Determine funciones[y g que satisfaganten) ,p O(g(n

39. Si[(n) = O(g{n, entonces g{n) = ([(n. 40. Si[(n) = 0(g(n, entonces gen) = 8 ([(n. 4>1. 1(n) + gen) = 0(h(n, donde h(n) = mx{f(n), gen)} 42. ten) + gen) = 8(h(n,dondeh(n) = rnn{f(n),g(n)}

n

PASO INDUCTIVO.

Suponga que el tiempo necesario para una entrada de tamao n

es a lo ms C'n y que el tiempo necesario para procesarun elemento adicional es C".Sea C el mximo de C' y C". Entonces el tiempo total necesario para una entrada de tamao n + 1 es a lo ms c: + cr Cn + C = C(n + 1) Se ha verificado el paso inductivo. Por induccin. pata una entrada de tamao n, el tiempo necesario es a lo ms Cn. Por tanto, el tiempo de ejecucin es O(n). 52- [Requiere conocimientos de clculo.] Determine si cada afirmacin es verdadera o falsa. Si la afirmacin es falsa. proporcione un contrajemplo. Se supone que[y g son funciones con valores reales. definidas sobre el conjunto de enteros positivos y que g(n),p Oparan 2: 1. (a) Si lm ten)n-+~

y

g(n),p O([(n. ~

44. Determine funcionesf, g, h Y t que satisfaganten) O': 0(g(n, h(n) O': 0(t(n, ten) - h(n)

'* 0(g(n)- ten~.

45. .Dnde est el error en el siguiente razonamiento? Suponga que el tiempo de un algo~tmo en el peor de los casos es 8(n). Como 2n = 8(n), el tiempod~ ejecucin ~I algoritmo en el peor de loscasos con entrada de tamao 2n ser aproximadamente ~gua1 al tiempo de; ejecucin del algoritmo en el peor de los casos con entrada detamano n. 46. Muestre que si n 2: 4, n n nlgn2Ig2~-4-'

gen)

47. Define la ecuacinten) = O(g(n

existe y es igual aalgn nmero real. entonces [(n) = O(g(n (b) Si[(n) = O(g(n, entonces , ten) 1Im-n-+~

. .

'';' -

una relacin de equivalencia sobre el conjunto de funciones con valores reales definidas sobre (1,2, ... }? 48. Define la ecuacin. ten) = 8(g(n

gen)

- existe y es igual a algn nmero real. (e) Si lm ten)n-+~

una relacin de equivalencia sobre el conjunto de funciones con valores reales definidas sobre (1,2... }? 49. [Requiere conocimientos de clculo integral.] (a) Muestre, consultando la figura, que I 1 I -+-+ ... +- c log, n. 2 3 n(b) Muestre. consultando la figura. quey

g(n)

existe y es igual a algn nmero real, entonces[(n) = 8(g(n. (d) Si. 'l~ ten) 1 Im--O': ,n-+~

gen)

entoncesj'(e) = 8(g(n. (e) Si[(n) = 8(g(n, entonces.

x

log, n a unproble~msgrande.'(Ett!l~pr06Iema;Iexte.Kiii6s'ri 'quetermina.en'elndice.i'- 'au1JltsUni!quetermina:'ed:el(ndicei:}'f~ :i,:.,.,:,"',

186

CAPiTULO 3 I ALGORITMOS

3.6 I ANLISIS DEL ALGORITMO DE EUCLIDES

187

3.6.1 Nmero de divisiones necesarias para el algoritmo de Euclides para diversos valores de la entradaTABLA

X:lO

O

1

2OI I

3OI2

4

5OI2

6

7

8

1

I

OOII I

OI

OI I

OI2

OII

2 34

OO

1 2 1 2 2

2 12

1 2

32

1 22

2

3I4

OO O O O

1I I

3 32

56 7

312

I2

1 2I

1 22

2 2ITABLA

1 1

31

34

1 2

8

3

3.6 ANUSIS'DELALGORITMO DE EUCUDESEn esta seccin analizaremos el desempeo en el peor de los casos del algoritmo de Euclides para determinar el mximo comn divisor de dos enteros no negativos, no ambos cero (algoritmo 3.3.8). Como referencia, resumiremos el algoritmo: Entrada:

La sucesin de Fibonacci comienza as:1, 2, 3, 5, 8, 13,

3.6.2 Menor pareja de entrada que requiere n divisiones en el algoritmo de Euclides1

a y b (enteros no negativos, no ambos cero)

'.'

Salida: Mximo comn divisor de a y bL proceduremcd(a, b) 2. . // hacemos que a sea el mayor 3. ifa < b tben 4. intercambiar(a, b) 5. while b '" Odo 6. begin 7. dividir a entre b para obtener a = bq + r, 0:$ r < b 8. a i-e b 9. b:= r

En la tabla 3.6.2 aparece un patrn sorprendente: La columna a es el principio de la sucesin de Fibonacci y, excepto por el primer valor, la columna b tambin es el principio de la sucesin de Fibonacci! Conjeturamos entonces que si la pareja a, b, a> b, se introduce comoentrada en el algoritmo de Euclides y requiere n =e: I divisiones, entonces a =e: L; J y b =e: fn' Como mayor evidencia de esta conjetura, si calculamos la menor parej.a d~ ~ntrada que requiere cinco divisiones, obtenemos a = 13 Yb = 8. Los valores para seis divisiones son a = 21 y b = B ..Nuestro siguiente teorema confirmaque nuestra conjetura es correcta. La demostracin de este teorema se ilustra en la figura 3.6.1.91 57

n(= nmero

a b

1

U iiJo2 3 5 8 1 2 3 . 5

I

de divisiones)

OI 2 3 4

-----

= 57 . 1 + 34~

(1 divisin)

.y

34, 57 requieren 4 divisiones

(para hacer un total de 5) (por hiptesis de induccin)~/5

10.11.

endreturn(a)

/5 y 34

~

:. 91 = 57 1

/4 + 34

~

57

+ 34

+ /4 = /6

12. endmcdDefinimos el tiempo requerido por el algoritmo de Euclides como el nmero de divisiones ejecutadas en la lnea 7. La tabla 3.6.1 enumera el nmero de divisiones necesarias para ciertos valores pequeos de entrada. El peor de los casos en el algoritmo de Euclides ocurre cuando el nmero de divisiones es tan grande como sea posible. En relacin con la tabla 3.6.1, podemos determinar la pareja de entradas a, b, a> b, con a tan pequeo como sea posible, que requiere n divisiones para n = O,... , 4. Los resultados aparecen en la tabla 3(6.2. Recordemos que la sucesin de Fibonacci u;,} (vase el ejemplo 3.4.6) se define mediante las ecuaciones

F,GURA 3.6. 1 La demostracin del teorema 3.6.1. La pareja 57, 91, querequiere n + 1 = 5 divisiones, es una entrada del algoritmo de Euclides.

['o

TEOREMA3.6.1

.1

Suponga que la pareja a, b, a > b, requiere n =e: 1 divisiones cuando se utiliza como entrada del algoritmo de Euclides. Entonces a =e: 1.+ 1 Y b =e:f donde {J.} denota la sucesin de Fibonacci. ',

Demostracin.PASO BASE

La demostracin es por induccin sobre n.

f,=

1;

; =

2;

In = 1. _I + f n _ 2' n =e: 3.

(n = 1). Ya hemos observado que el teorema es verdadero si n = 1.

Mi

3.71188 CAPiTULO 3 I ALGORITMOS

EL SISTEMA. CRIPTOGRFICO

ce

Suponga que el teorema es cierto para n 2: 1. Debemos mostrar que el teorema es verdadero para n + l. Supongamos que la pareja a, b, a > b, requiere n + 1 divisiones al utilizarse como entrada para el algoritmo de Euclides. En la lnea 7, dividimos a entre b para obtenerPASO INDUCTIVO.

Debido a que la funcin logartmica crece muy lentamente, el teorema 3.6.2 nos dice que el algoritmo de Euclides es ms o menos eficiente, incluso para valores grandes de la entrada. Por ejemplo, como'

a=bq+r,O:!Sr r. Estosvalores requieren n divisiones adicionales. Por la hiptesis de induccin,

b2:f.+!

y

r2:f..

(3.6.2)

el algoritmo de Euclides requiere a lo ms 33 divisiones para calcular el mximo comn divisor de cualquier pareja de enteros. no ambos cero, en el rango de O a 1,000.000.

Al combinar (3.6.1) Y{3.6.2), obtenemos

a

= bq + r 2: b + r 2:1.+1 +1. =f.+2"a2:f.+ 2

(3.6.3)

[La primera desigualdad en (3.6.3) es vlida pues q > O; q no puede ser igual a O, pues b.j Las desigualdades (3.6.2) y (3.6.3) implican

a>

~ b. (El intercambio de los valores de a y b no altera el nmero de divisiones requeridas.) Por el teorema 3.6.1, a 2: f.+,. As,

6.

Muestre que rncd(j.,f.+l) = 1, n 2: l.

f.+ 1 :!Sm.Como n

t

3.7

EL SISTEMA CRIPTOGRFICO CON CLAVE PBUCA RSA

+ 1 2:

5. el ejercicio 20 de la seccin 3.4 implica que

Al combinar estas ltimas desigualdades, se obtiene

(~).+l < m.\.2Al calcular el logaritmo en base 3/2, obtenemos

n + l < log3/2 m.Por tanto,

La criptologa es el estudio de sistemas llamados criptosistemas, para las comunicaciones seguras. En un criptosistema, el emisor transforma el mensaje antes de transmitirlo de modo que, en teora,slo un receptor autorizado pueda reconstruir el mensaje original (es decir. el mensaje antes de ser transformado). Se dice que el emisor cifra el mensaje, y que el receptor descifra el mensaje. Si el criptosistema es seguro, las personas no autorizadas no podrn descubrir la tcnica de cifrado. as que aunque lean el mensaje cifrado, no podrn descifrarlo. Los criptosisternas son importantes para las grandes organizaciones (por ejemplo. el gobierno o el ejrcito) y tambin para los individuos. Por ejemplo, si un nmero de tarjeta de crdito se enva a travs de una red de computadoras, es importante que el nmero sea ledo slo por el receptor indicado. En esta seccin. examinaremos ciertos algoritmos que permiten la comunicacin segura.2m 3'

n < log3l2 m -1 =

IOg312

m -10g 312 3/2 =

log312

t Esta seccin puede omitirse sin prdida de continuidad.

I:;ORITMOS

3.71 EL. SISTEMA

CRIPTOGRFlCO CON CL.AVE pBLICA

RSA

191

En uno de los sistemas ms antiguos y sencillos, el emisor y el receptor tienen cada uno una clave que define un carcter sustituto por cada carcter potencial por ser enviado. Adems, el emisor y el receptor no revelan la clave. Tales claves son privadas.

Para transmitir a = 572 al poseedor de la clave pblica 713, 29, el emisor calcula S69 e = a" mod z= 57229 mod 713 = 113 Yenva 113. El receptor calcula es mod z = 113 mod 713 = 572 para descifrar el mensaje. O Parecerla que hay que calcular nmeros enormes para cifrar y descifr:armensa!.s mediante el sistema RSA. Por ejemplo, el nmero 57229 en el ejemplo 3.7.2 nene 80 dgitos, y si p y q tienen 1000 ms dgitos, los nmeros ~an ~ucho ma~ores. La clave para simplificar los clculos consiste en observar que la aritmtica se realiza mdulo z, Puede mostrarse que

EJEMPLO 3.7.1

Si se define una clave comocarcter:

se reemplaza por:

ABCOEFGHIJKLMNOPORSTUVWXYZ EIJFUAXVHWP GSRKOBTOYDMLZNC

ah mod z = [(a modz)(b mod zj] mod z

(3.7.1)

el mensaje SENO MONEY se cifrara como OARUESKRAN. El mensaje cifrado SKRANEKRELIN se descifrara como MONEY ON WAY. O Los sistemas sencillos, como el del ejemplo 3.7.1, se descubren con facilidad, pues ciertas letras (por ejemplo, en el ingls la letra E) o combinaciones de letras (por ejemplo, .. ER en el ingls) aparecen con ms frecuencia que otras. AdemS,un problema general con las claves privadas es que las claves se tienen que enviar de-manera segura al emisor y al receptor antes de poder enviar los mensajes. Dedicaremos el resto de esta seccin al sistema criptogrfico con clave pblica RSA, que recibe el nombre de sus inventores, Ronald L. Rivest, Adi Sharnir y Leonard M. Adleman, el cual se cree que es seguro. En el sistema RSA, cada participante hacepblica una clave de cifrado y oculta una clave de descifrado. Para enviar un mensaje, todo lo que debe hacer es buscar la clave de cifrado del receptor en una tabla distribuida pblicamente. El receptor descifra entonces el mensaje con la clave oculta de descifrado. En el sistema RSA,los mensajes se representanmediante nmeros. Por ejemplo; cada carcter se podra representar como un nmero. Si el espacio en blanco se representa como 1, A como 2, B como 3, y as sucesivamente, el mensaje SEND MONEY se representara como 20, 6,15,5,1,14,16,15,6,26. Si se desea, los enteros se podran combinaren un nicoentero 20061505011416150626. A continuacin describimos el funcionamiento del sistema RSA, presentaremos un ejemplo concreto, y luego analizaremos su funcionamiento. Cada posible receptor elige dos primos p y q y calcula z = pq. Como la seguridad del sistema RSA.se basa principalmente en la incapacidadde que alguien que conozcael valor de zdescubra los nmeros p y q, por lo general p y q se eligen de modo que cada uno tenga 100 o ms dgitos. A continuacin, el posible receptor calcula I/J = (p - l)(q - 1) Yelige un entero n tal que mcd(n,l/J) = l. En la prctica, con frecuencia se elige n como un primo. Entonces se hace pblica la pareja z, n. Por ltimo, el posible receptor calcula el nico nmeros, O :...'.. : .. >:s'eiS;foi';';~~ mas.por elprncpio demul~plicacin,el.nn~ de tefu~:\~"d.~~~~"~~':Jl'~i'~

>. ;:~:Xl:\I"\'X2",ri'XJ' r"~;

. '>::~:t'~\chl"

o::' ""

;:,~~\.~"

seelige.:Sj~6,Y5e;~I~en ~';;'seeligel~,1;S'j~6.ys~.colocaZenlj;',:::; e,J" . elig~j~1. . S 6;y:se cofoea8;en.~~Po~ejmpIo, para C9~trUir;la.tema~ ~;'1r .;\~-.

'ad:ik~~~~i~tgiil~I:~tO"&~~P~O~~';~,l': .::: .~. '~:~~ n. (b) Muestre que S = l para toda n 2: 1. (e) Muestre que = 1 para toda n 2: 1. (d) Muestre que S3.2 = 3. (e) Muestre queSo = 7. (t) Muestre que S. 3 = 6. (g) Muestre que Sn.2 = 2n - 1-1 para toda n 2: 2. (h) Muestre que Sn n-l = C(n, 2) para toda n 2: 2. (i) Determine una'frmula para Sn.n-2' n 2: 3, Ydemustre1a. 76. Muestre que existen

En el ejemplo 4.21.22 se cont elnnIero de tryectoas desde la esquina inferior iz-;,:: quierda hasta la esquina superiorderechade,uoa retcula It X1. la cual slo sepOdf~. ': recorrer hacia la derecha o hacia. arriba,La solucin a ese problema podificaba..cada'~.: ruta como una.cadena de' nletras D (derecha) y nletnis A (ambaj.Entonces. el pro-:;, ::: ", bemase.convirti en 'el,problemade contar el'nmeroae talesCadenas. Una de es-~\"i -. :tas'cacteU'as;p~i:deob~neise eligie'Dcto,n Posiciones~ las letras. D. sin importar el \'1 orden de seleccin..entre:Jas)i1;posiciones,disponibles enla~caelena,.. para despus:;;]" llenar las dems posiciones con.letras.A As, el nmero.de cadenasyel nmerode', "" . -rutsSooiguali:s:aC(2n.n)., ""'IJ"';'~;';~,:~,;.,;;;.,,;:," j ' , : ' ; ' : ' ' , : " : , , , , .'l.. ;'\'Eneste nuevoproblma:pOctriiiseOdifi~;~ rilt mo 'umi' cad~nlde n ,~; .1etras.D (derecha) ym letras A (arriba). Como en eheore~ anterior"debemoscon-: '~: -taretiiinerOde:tal~cadenas. U JiaJe. Cadenaspuede bterme eli~endoitpo:-": . siciones para: las .lettaS B " sin jimportar-el;orden;'de seleCcin,: ertlre las' ri,'-+ lit:;,: posiciones. disponibles enIa cadena y ,llenando desJus las posiciones restantescon:': 1etrasA.:Asl':elllnIerode cadenasyel;oInerode.rutas,son iguales a C(n:;+in,.i}:,t~, Con esto hemosresponddo a la parte (a) ..,~. : \ ' : , 1 ' c.. '. jhj' ",

p~~;;;r~~taI-;~.p:ble~a~.;~~,',,~i,::"i~~~; ., e>.:' ,,;~,. \~)'\:i~:)i;~:,j,.'l.

x " : V ':-,

,;1''eguida por 12357. La ltima cadena ser 34567. O

I I I I

4. 5. 6.

procedure combination(r, n) for i:= I to rdo s.:= i print s)' ... , s, 11 se imprime la primera r-combinacin for i:= 2 to CCn, r) do begin

7. 8.9. 10. 11. 12. 13. 14. 15. 16.

m:= r max.val:= n whiles = max valdo

_i-.-

t!"f":

I

EJEMf>LO 4.3.7

Determine la cadena posterior a 13467 al enumerar las S-combinaciones de X = {1,2,3,4, 5,6,7}. Ninguna cadena que comience con 134 y represente una 5-combinacin de X excede a 13467. As, la cadena posterior a 13467 debe comenzar con 135. Como 13567 es la menor cadena que comienza con 135 y que representa una 5-combinacin de X, la respuestaes 13567. O

II1J

17.18. 19. 20. 21. 22.,

11 se d~termin;el elemento ms a la derecha, que no tenga su mximo valor begin m:=m-I max val : max jval>: 1 end 11 se incrementa el elemento ms a la derecha s := s + I lel resto de los elementos son los sucesores de s.. forj:=m+ltordoSj:=

~~'! ,.j

~-'-I

1

.lb"'~'

~~i

II

Sj~J

+111 se imprime la i-sima combinacin

EJEMPl..O 4.3.8

print s)' ... , s, end end combination.JEMf>L04.:;1.10

~

e---

Determine la cadena posterior a 2367 al enumerar las 4-combinaciones de X = {l. 2, 3, 4, 5,6,7}. . Ninguna cadena que comience con 23 y represente una 4-combinacin de X excede a 2367. As, la cadena posterior a 2367 debe comenzar con24. Como 2456 es la menor caO dena que comienza con 24 y representa una 4-combinacin de,X,.larespuesta es 2456.

I II II

C-- i~'

Mostramos la forma en que el algoritmo 4.3.9 genera la 5-combinacin de {I, 2, 3, 4, 5, 6, 7) posterior a 23467. Estamos suponiendo que sJ = 2,s2

fr-'~~

= 3,

S3

= 4,

s,

= 6,

Ss

= 7.

,e-'

.._-----------------'---~----.:....-_-

.-L

I I

~

----------------.~

e-

~--

~

}'

232

CAPiTULO

41 MltTooos

OECONTEO

y

EL. PRINCIPIO DE LA PICHQNERA

4.31'. EJEMPl..0I4.313;

ALGORITMOS PARA GENERAR PERMUTACIONES Y COMBINACIONES

233

En la lnea 15, vemos que S3 es el elemento ms a la derecha que no alcanza su mximo valor. En la lnea 16, S3 se iguala a 5. En las lneas 18 y 19, s. se iguala a 6 y S5 se iguala a 7. En este momento.

,1324, 2413, 4123, 1342, 2431, 4132, 1423, 3124, 4213. 1432, 3142, 4231, 2134, 3214. 4312, 2143, 3241, 4321.O

El mtoo.0 del ejemplo 4.3.12 permite enumerar las permutaciones de {l. 2, 3, 4} en orden lexlcografico como . Hemos generado la 5-combinacin 23567 posterior a 23467.EJEMPLO 4.3. 11

o

1234, 2314, 3412,

1243, 2341, 3421,

Las 4-combinaciones de {1, 2, 3, 4, 5, 6 l enumeradas segn el algoritmo 4.3.9 son 1234, 1356, 1235, 1456, 1236, 2345, 1245, 2346, 1246, 2356. 1256, 2456, 1345, 3456. 1346,

A continuacin damos el algoritmo.ALGORlTM04.3.14

o

Generacin de permutaciones

Al igual que el algoritmo para generacin de las r-combinaciones. el algoritmo para generar permutaciones enumerar las permutaciones de {l. 2, ... , nI en orden lexicogr. fico. (En el ejercicio 16 se pide un algoritmo que genere todas las r-permutaciones de un conjunto con n elementos.)E..lEMPLO 4.3.12

Este.algoritmo enumera todas las permutaciones de ( l. 2, ... , nJ en orden lexicogrfico creciente. Entrada: Salida:

nTodas las permutaciones de ( 1, 2, ... , n) en orden lexicogrfico creciente.

Para construir la permutacin de {1, 2. 3, 4, 5, 6 l posterior a 163542. debemos mantener idnticos el mayor nmero posible de dgitos de la izquierda. Podra la permutacin posterior a la permutacin dada tener la forma 1635__? Co"mo la nica permutacin de la forma 1635__ distinta de la permutacin dada es 163524 y 163524 es menor que 163542, la permutacin posterior a la permutacin dada no es de ta forma 1635__. ? Los" Podra la permutacin posterior a la permutacin dada tener la forma 163 ltimos tres dgitos deben ser una permutacin de {2, 4, 5 l. Como 542 es la permutacin ms grande de {2, 4. S}, cualquier permutacin que comience con 163 es menor que la permutacin dada. As, la permutacin posterior a la permutacin dada no es de la forma 163 . La razn por la cual la permutacin posterior a la permutacin dada no puede comenzar con 1635 o 163 es que en cualquier caso, los dgitos restantes en la permutacin dada "(42 y 542, respectivamente) decrecen. Por tanto, trabajando desde el lado derecho, debemos determinar el primer dgito d cuyo vecino derecho satisfaga d < r. En nuestro caso, el tercer dgito, 3, tiene esta propiedad. As. la permutacin posterior a la permutacin dada comenzar con 16. El dgito posterior a 16 debe ser mayor que 3. Como queremos determinar la permutacin siguiente ms pequea, el siguiente dgito es 4, el menor dgito disponible. As, la permutacin deseada comienza con 164. Los dems dgitos 235 deben aparecer en orden creciente para obtener el valor mnimo. Por tanto, la permutacin posterior a la permutacindadaes 164235. O Vemos que para generar todas las permutaciones de ( 1, 2, ... , n}, podemos comenzar con la permutacin 12 ... n y luego utilizar varias veces el mtodo del ejemplo 4.3.12 para generar la siguiente permutacin. El proceso concluye cuando se genera la permutacin n(n - 1) .. 21.

l. procedure permutationin 2. for:= I tondo 3. s:= i4. 5.

6. 7. 8.9.

print s" ... ,sn // se imprime la primera permutacin for:=2ton!do begin

m:=n-lwhiles.. >sm+t do 11 se determina la primera disminucin trabajando desde la derecha

10.11. 12. 13.

m:=m-"I k:=n while s.. > Sk do// se determina elelemento ms a la derechas, con s..

< Sk

14.15.

k:=k-lswap(sm' Sk)

16. 17. 18.19.

p:=m+l q:=n whilep0,.10 3=1 16.0';;x l,;;6,x z;;';O,x3;;,;0 Q: 17.0,;;x 1 k, tenemos una contradiccin.

PRINCIPIO DE LAi PlCHONERA

(Segunda forma)

sil es una funcin de un conjunto finito X a un conjunto finito Y y 1 xl>'1 Y!, entonces /Ix,) = f(x 2) para xl' x 2 E X. x, "" x 2 La segunda forma del principio de la pichonera puede reducirse a la primera, si X es el conjunto de palomas y Y el conjunto de pichoneras. Asignamos la paloma x a la pichoneraf(x). :or la primera forma del principio de la pichonera, al menos dos palomas, XI' x 2 E X, se aSlgnanal~ rnisma pichonera; es decir,f(x l ) = f(x 2) paraxl'x2 E X,x "" x l r Nuestro siguiente ejemplo Ilustra el uso de la segunda forma del principio de la pichonera.E..lEMPL04.6.2;,

Si se conectan unos con otros 20 procesadores, muestre que al menos dos procesadores se conectan directamente al mismo nmero de procesadores. Designemos los procesadores como 1,2, ... , 20. Sea a, el nmero de procesadores Si n palomas vuelan hacia k pichoneras y k < n, alguna pichonera contiene al menos dos a los cuales est directamente conectado el procesador i, Debemos mostrar que a. = a. papalomas. ra algn i "" j. El dominio de la funcin a es X = { 1, 2 , 20} yel rango Yes algn ~ubObservemos que el principio de la pichonera no nos dice cmo localizar la pichone= 1, , 19} y no podemos utilizar ra que contiene dos o ms palomas. Slo afirma la existencia de una pichonera con-ass-e- _ .. ~,cQnjuntQ de {O, 1, ... , 19 j. Por desgracia, de manera inmediata la segunda forma del principio de la pichonera. ms palomas. Examinemos la situacin con ms detalle. Observe que no podemos tener a. = O, Para aplicar el principio de la pichonera, debemos decidir cules objetos juegan el para algn i, y aj = 19, para algnj, ya que entonces tendramos un procesador (el' i-si. papel de las palomas y cules objetos juegan el papel de los palomares. Nuestro primer mo) no conectado a los dems, mientras que, al mismo tiempo, algn otro procesador (el ejemplo ilustra una posibilidad. j-simo) estara conectado a todos los dems procesadores (incluyendo al i-simo). As, el rango Yes un subconjunto de {O, l, ... , 18} o [ l , 2, ... , 19}. En cualquier caso, < 20 = X Por la segunda forma del principio de la pichonera, a, = aj para algn i "" i. como se deseaba demostrar: OPRINCIPIO DE. LA PlCHONERA

(Primera forma)

Ixl

!{o.

I

I l

Irl

EJEMPLO 4.6.3

F'GURA

4.6. 1

n =

6 palomasen k = 4 pichoneras.Alguna pichoneracontiene al menosdos

Muestre que si se eligen 151 cursos distintos entre 300 cursos de computacin numerados del I al 300 inclusive, al menos dos estn numerados en forma consecutiva. Digamos que los nmeros de los cursos elegidos son

palomas.

(4.6.1)Los 302 nmeros que constan de (4.6.1) junto conE..lEMPL04.6.1

c..... el

Los nombres de diez personas son Alice, Bemard y Charles, mientras que sus apellidos son Lee, McDuff y Ng. Muestre que al menos dos personas tienen los mismos nombres y apellidos. Existen nueve nombres posibles para las 10 personas. Si pensamos que las personas son las palomas y los nombres son los palomares, podemos considerar la asignacin de nombres a las personas como la asignacin de palomares a las palomas. Por el principio de la pichonera, algn nombre (pichonera) se asigna por lo menos a dos personas (palomas). O A continuacin enunciamos el principio de la pichonera de forma a1temati va.

+ 1, c2 + 1,

(4.6.2)

varan entre I y 301. Por la segunda forma del principio de la pichonera, al menos dos de estos valores coinciden. Los nmeros (4.6.1) son todos distintos y por tanto los nmeros (4.6.2) tambin son distintos. Entonces, debe ocurrrque uno de los nmeros (4.6.1) y uno de los nmeros (4.6.2) sean iguales. As, tenemos

y por supuesto, c es el sucesor de cj

.

O

250

CAPiTULO 4

I

METODOS CE CONTEO Y EL PRINCIPIO DE I-A PICHONERA

4.6 I

EL PRINCIPIO DE LA PICHONERA

251

EJEMPLO 4.6.4

Denotemos las fotos por PI' P2'

... ,

P6' Cada uno de los cinco pares

Un inventario consta de una lista de 80 artculos, cada uno marcado como "disponible" o "no disponible". Existen 45 artculos disponibles. Muestre que existen al menos dos artculos disponibles en la lista a exactamente nueve artculos de distancia. (Por ejernplo,los artculos disponibles en las posiciones 13 y 22 o en las posiciones 69 y 78 satisfacen la condicin.) Sea a la posicin del -sirno artculo disponible. Debemos mostrar que a - al = 9 para algunos i y j. Consideremos los nmeros (4.6.3)y

tiene el valor "similar" o "no similar". Por la tercera forma del principio de la pichonera, existen al menos 15/21 = 3 pares con el mismo valor; es decir, existen tres pares de fotos

todas similares o todas no similares. Supongamos que cada par es similar. (El caso en que cada par no es similar est en el ejercicio 8.) Si cualquier par (4.6.5) es similar, entonces estas dos fotos, junto con PI' son mutuamente similares, con lo que hemos encontrado tres fotos mutuamente similares-, En caso contrario, cada uno de los pares (4.6.5) no es similar y.hemos determinado tres fotos que no son mutuamente similares.

a. 5 + 9.. _

(4.6.4)

LOS 90 nmeros en (4.6.3) Y(4.6.4) slo pueden variar entre

ry"'g9 inclusive. Por la segunda forma del principio de la pichonera, dos de los nmeros deben coincidir. No podemos tener dos nmeros de (4.6.3) o de (4.6.4) idnticos; as, algn nmero en (4.6.3) es igual a algn nmero de (4.6.4). Por tanto, a, - al = 9 para algunos iyj, como se deseaba. O A continuacin enunciamos otra forma ms del principio de la pichonera.PRINCIPIO DE U\, P1CHONERA

o~t::::::::=r~

Ejercicios1. Trece personas /tienenpor nombres Dennis, Evita y Ferdinand, y por apellidos Oh, PieI

(Tercera forma}

Sea f una funcin de un conjunto finito X en un conjuruofinito YsSuponga que [x = n y Y! = m. Sea k = 1nJm1. Entonces existen al menoS k valoresul , ; :,a k E X tales que

I

I

2. 3.

Para demostrar la tercera forma del principio de la pichonera, argumentamos por contradiccin. Sea Y = (y l' . . . , Ym l. Supongamos que la conclusin es falsa. Entonces existen a lo ms k - I valores x E X con f (x) = ."1; existen a lo ms k - I valores x E X conf(x) = ."2;"'; existen aloms k - I valores x E X conf(x) = Ym As, existen aloms m(k - J.) miembros en el dominio de! Perom(k-I)~.2

28.

11. 12. 13. 14.

Cuntos elementos tiene el dominio de a? Muestre que el rango de a est contenido en {l. 2.... n }. Explique por qu los ejercicios II Y 12 implican que a, = aj para algunos i "'" j. Explique por qu el ejercicio 13 implica que existen i y j distintos en X tales que m

'; 19.

=.": 30.

i+j.15. Proporcione un ejemplo de un subconjunto de {l. 2... 2n + I} con (n tos con la siguiente propiedad: No existen i.] E X tales que i + j E X.

+

1) elemen-

en torno del centro de una cancha en un orden arbitrario. Muestre que existen tres jugadores consecutivos tales'que la suma de sus nmeros es al menos 20. Para la situacin del ejercicio 25. determine y demuestre una estimacin de la magnitud de la suma de los nmeros de cuatro jugadores consecutivos. Seafuna funcin uno a uno de X = {I, 2.... n} sobre X. See f" = fa fa .. . afIa k-sima composicin de f con s misma. Muestre que existen enteros positivos distintos i yj tales quef'(x) = P(x) para todo x E X. Muestre que para algn entero positivo k. t(x) = x para todo x E X. Un rectngulo 3 x 7 se divide en 21 cuadrados, cada uno de los cuales se colorea rojo o negro. Demuestre que el tablero contiene un rectngulo no trivial (que no sea I x k ni k x I) cuyas cuatro esquinas cuadradas sean todas negras o todas rojas. Demuestre que si p unos y q ceros se colocan en tomo de un crculo de manera arbitraria. donde p. q y k son enteros positivos tales que p ~ kq, el arreglo debe contener al menos k unos consecutivos. Escriba un algoritmo