L´ ogica y Conteo

Elaborado por: Jeff Maynard Guill´en

Eliminatoria III Mayo, 2011

L´ ogica-Conteo Principio de Conteo: Si tenemos n opciones, y cada una de estas tiene a su vez m opciones, entonces la cantidad total de opciones es n · m.

Ejemplo: Hay cinco sobres sin estampillas y cuatro tipos de estampillas de un mismo valor. ¿De c´ uantas maneras se puede seleccionar un sobre con estampilla para enviar una carta?

En este caso f´ acilmente podemos ver que la soluci´on es 5 · 4 = 20. 

Ejemplo: ¿C´ uantas placas distintas hay con dos letras a la izquierda y tres n´ umeros a la derecha? (Asumiendo que hay 27 letras)

En este caso tenemos que para la primera y segunda posici´on hay 27 opciones, mientr´as que para la tercera, cuarta y quinta 10 opciones. Entonces la soluci´ on ser´ıa 27 × 27 × 10 × 10 × 10 = 729000. 

Proposici´ on: El n´ umero de formas de tomar n objetos distintos, sin permitir repeticiones, eligiendo todos a la vez es n!

Esto dado que tendriamos n opciones para el primer elemento, n − 1 para el segundo y recursivamente s´ olo una para el u ´ltimo objeto. De esa forma tenemos n · (n − 1) · (n − 2) · · · 1 = n!

Ejemplo: ¿De c´ uantas formas se pueden sentar 5 personas en 5 sillas numeradas del 1 al 5?

La primera persona se puede sentar en cualquier silla, la segunda persona tiene 4 opciones para sentarse, la tercera 3 y la u ´ltima s´ olo tendr´ a un asiento disponible. Entonces la soluci´on es 5 · 4 · 3 · 2 · 1 = 5! = 120. 

Ejemplo: Cuantas palabras de tres letras podemos formar con las letras a, b, c, d, e si est´a permitido usar la misma letra dos veces.

Para las tres posiciones tendremos cinco opciones. Entonces 5 · 5 · 5 = 53 . 

Ejemplo: Cuantas palabras de tres letras podemos formar con las letras a, b, c, d, e si no podemos usar la misma letra dos veces.

Para la primera posici´ on tenemos 5 opciones, para la segunda 4 y para la tercera 3. Entonces tenemos 5·4·3 = 60. 

Notese que en estos dos casos el orden si importa, es decir aba 6= aab 6= baa

2

En general tendremos que cuando el orden si importa:

Proposici´ on: El n´ umero de formas, sin repeticiones, de elegir n objetos distintos, tomando m objetos a la vez es n! n · (n − 1) · · · (n − m + 1) = (n − m)! Proposici´ on: El n´ umero de formas, aceptando repeticiones, de elegir n objetos distintos, tomando m objetos a la vez es nm

Ejercicio:1 Se colocan palitos en una mesa de manera que se forme un rect´angulo de 2 x 3 como lo muestra la figura:

Debemos pintar cada palito de azul, rojo o negro de modo que cada uno de los cuadros de la figura quede limitado por exactamente dos palitos de un color y dos palitos de otro color. ¿De cu´antas formas podemos hacer esto?

Soluci´ on:

Hay 33 formas de pintar el rengl´ on horizontal superior de palitos. El palito vertical m´as a la izquierda de la primera fila tambi´en se puede pintar de tres formas. Una vez definidos los colores de los palitos superiores y el palito izquierdo de un cuadrito, hay dos maneras de completar el segundo: si ambos palitos pintados tienen el mismo color, tenemos dos colores para pintar los dos palitos restantes; y si los dos tienen distinto color hay dos formas de pintar los do palitos restantes con esos colores. Luego, para completar la primera l´ınea de cuadros hay un total de 33 · 3 · 23 formas. De la misma manera, el color del palito vertical a la izquierda de la segunda fila puede escogerse de tres maneras y hay 23 formas de pintar los dem´ as palitos de la segunda fila.

As´ı, en total, habr´ a 33 · 3 · 23 · 3 · 23 = 35 · 26 formas de pintar los palitos del tablero. 

Ejemplo ¿C´ uantos n´ umeros distintos de cuatro cifras y divisibles por 4 pueden formarse a partir de las cifras 1, 2, 3, 4, 5, si cada cifra puede emplearse en la escritura de un n´ umero varias veces? Soluci´ on Usando s´ olo esas cifras, tendremos que los u ´nicos n´ umeros divisibles por 4 ser´ıan aquellos que terminen 1 Ejercicio

tomado del banco de ejercicios III Eliminatoria 2008

3

en 12, 24, 32, 44 y 52. Luego, la cantidad total buscada es: |{z}  |{z}  = 125 n´ umeros.  5×5

5

Luego cuando el orden no importa:

Ejemplo: Cuantas palabras de tres letras podemos formar con las letras a, b, c, d, e si no podemos usar la misma letra dos veces.

En este caso tenemos en total, como ya vimos en un ejemplo anterior, es 60. Sin embargo estamos contando algunos casos varias veces, ¿pero cuantas veces? La respuesta es 3! ya que es el n´ umero de formas de elegir tres letras. Entonces 60 60 la respuesta ser´ıa = = 10.  3! 6 Proposici´ on: El n´ umero de formas, sin repeticiones, de elegir n objetos  distintos tomando m objetos a la vez es n! n a esto se le llama coeficiente binomial y se denota por . Esto se puede ver tambi´en como (n − m)! · m! m Ejemplo: De un grupo de 10 ni˜ nos y 15 ni˜ nas se quiere formar una colecci´on de 5 j´ovenes que tenga exactamente 2 ni˜ nas. ¿C´ uantas colecciones distintas se pueden formar?

Soluci´ nas se puede hacer   on Veamos que en este caso el orden no va a importar, entonces la elecci´on de las 2 ni˜ 15 × 14 15 15! = = 105 formas. Como deben ser 5 en total y debe haber 2 ni˜ nas exactamente, de = (15 − 2)!2! 2 2   10 10 entonces los ni˜ nos ser´ an 3; ´estos se pueden escoger de = = 120 formas. Por tanto el resultado es 3 (10 − 7)!3! 105 × 120 = 12600.  Ejercicio:2 De cu´ antas maneras se pueden colocar un rey blanco y uno negro en un tablero de ajedr´ez de manera que se ataquen mutuamente.

Soluci´ on

Se colocar´ a el rey blanco primero. Si se coloca en alguna de las esquinas hay 12 maneras de colocar al rey negro. Si se coloca en una orilla que no sea la esquina hay 24 · 5 = 120 maneras de colocar al rey negro. Finalmente, si al rey blanco se coloca en una casilla interior hay 49 · 8 = 392 maneras de colocar la rey negro. En total, si se considera que las posiciones de cada rey se pueden intercambiar hay (12 + 120 + 392) · 2 = 1048 maneras.  Ejercicio:3 Una ficha es colocada en cada extremo de una cuadr´ıcula 1 × 2009. Dos jugadores, por turno, mueven su ficha 1 o 2 campos en direcci´ on del otro jugador. No se puede brincar fichas y pierde el primer jugador que no pueda mover su ficha. ¿Qu´e jugador tiene una manera de jugar que le garantice que siempre puede ganar? 2 Ejercicio 3 Ejercicio

tomado del banco de ejercicios III Eliminatoria 2009 tomado del banco de ejercicios III Eliminatoria 2009

4

Soluci´ on

Si el jugador uno mueve un cuadro, el jugador dos mueve dos cuadros, y si el jugador uno mueve dos cuadros el jugador dos mueve un cuadro, en ese caso en cada turno completo el n´ umero de cuadros decrece en 3. Como inicialmente hay 2007 = 3 × 609 cuadros y en cada jugada se disminuye en 3 despu´es de 669 jugadas no quedan espacios y el jugador 1 pierde.  Ejercicio:4 Con 29 palitos de f´ osforo, se forma la siguiente f´ıgura

Soluci´ on

Es claro que si se moviera un u ´nico palito, ´este no podr´ıa ser el lado de ning´ un cuadrado, pues para serlo, deber´ıa unir los extremos de otros dos palitos y esto no es posible en la figura anterior. Ahora bien, es f´acil ver que al mover convenientemente dos palitos se pueden obtener las siguientes figuras

Observe que en la primera de ellas hay exactamente 10 cuadrados (1 × 1) y dos cuadrados (2 × 2), por lo que en total hay 12 cuadrados. Adem´ as, cada palito de f´osforo, es el lado de al menos uno de los cuadrados (1 × 1). Por otro lado, en la segunda figura hay exactamente 10 cuadrados (1 × 1) y tres cuadrados (2 × 2), por lo que en total 4 Ejercicio

tomado del exanen D´ıa 2 III Eliminatoria 2009

5

hay 13 cuadrados. Nuevamente, cada palito de f´ osforo, es el lado de al menos uno de los cuadrados (1 × 1). Es claro entonces que n = m = 2 Para la segunda parte, basta ver que la condici´ on de que cada palito sea el lado de uno de los cuadrados, implica que el menor n´ umero de ´estos que se forman con 29 f´ osforos, debe ser mayor que 7. Lo anterior por cuanto se debe buscar que la mayor cantidad de f´ osforos sea el lado de un u ´nico cuadrado. Al observar la siguiente figura podemos concluir que 8 es la menor cantidad de cuadrados que podr´ıan ser formados usando los 29 f´osforos, de forma que cada uno de los palitos sea el lado de al menos un cuadrado.

 Ejercicio:5 Dentro de unos d´ıas se celebra el festival de Eurovisi´on, concurso al que una cadena de televisi´ on por cada pa´ıs europeo presenta una canci´ on. La primera parte del concurso es la interpretaci´on de las canciones: en la segunda, los pa´ıses participantes votan por turno, distribuyendo puntos seg´ un (en teor´ıa) la calidad de las distintas canciones interpretadas. En cada turno, se calcula una clasificaci´on provisional.

Supongamos que est´ an participando u ´nicamente Espa˜ na, Inglaterra, Francia, Alemania e Italia. Cada pa´ıs debe votar por los restantes, no a s´ı mismo, repartiendo sus puntos en la forma 5, 3, 2, 1. As´ı Espa˜ na que empieza la ronda de votaciones, asigna 5 votos a Alemania, 3 a Italia, 2 a Inglaterra y 1 a Francia. Despu´es votan los dem´ as pa´ıses, en el orden Francia, Inglaterra, Italia, Alemania. En los dos primeros turnos de votaci´ on (votos de Espa˜ na y Francia), Alemania va a la cabeza. Pero en cada uno de los tres siguientes hay cambio de l´ıder de la clasificaci´ on provisional, pasando a la cabeza de la tabla un pa´ıs que antes no hab´ıa ocupado este lugar.

Por cierto, en ninguno de los turnos se da en la clasificaci´on un empate a puntos entre pa´ıses. Se pide determinar el reparto de puntos en cada ronda.

Soluci´ on

Podemos construir la siguiente tabla: 5 Ejercicio

tomado del exanen D´ıa 1 III Eliminatoria 2008

6

´ DE VOTOS ASIGNACION PA´IS VOTANTE Espa˜ na

Inglaterra

Francia

Alemania

Italia

Espa˜ na

-

2

1

5

3

Francia

5

1

-

2

3

Inglaterra

2

-

5

1

3

Italia

1

3

5

2

-

Alemania

5

3

1

-

2

TOTAL

13

9

12

10

11

As´ı, por ejemplo, las posiciones en la segunda ronda son: Alemania con 7, Italia con 6, Espa˜ na con 5, Inglaterra con 3 y Francia con 1.  Ejercicio:6 Se seleccionan al azar tres d´ıgitos diferentes de cero. Se pega uno de esos tres d´ıgitos en la frente de Ana, otro de los d´ıgitos en la frente de Bety y el u ´ltimo d´ıgito en la frente de Carolina, de tal modo que ninguna de las ni˜ nas puede ver el d´ıgito que ella misma tiene en su frente. Adem´as las ni˜ nas est´an en cub´ıculos con vidrios especiales de tal modo que Ana puede ver a Bety y a Carolina, mientras que Bety s´olo puede ver a Carolina y Carolina s´ olo a Bety. El objetivo para cada ni˜ na es deducir cu´ al es el d´ıgito que lleva en su frente. El juez les informa que el n´ umero formado por los d´ıgitos que tienen Ana, Bety y Carolina en ese orden, es un cuadrado perfecto.

Despu´es de esto, Ana dice: ”No puedo saber cu´al es mi d´ıgito”. En seguida Bety dice: ”No puedo saber cu´ al es mi d´ıgito”. Finalmente, Carolina dice: ”Yo si s´e cu´ al es mi d´ıgito”. ¿Cu´al es el d´ıgito que Carolina tiene en la frente?. Explicar. Soluci´ on

Sean A, B y C los n´ umeros que Ana, Bety y Carolina tienen en sus respectivas frentes. Como Ana inicialmente no puede saber cu´ al es su d´ıgito y Ana puede ver a B y a C entonces el cuadrado ABC no se puede determinar de manera u ´nica conociendo B y C. Esto significa que debe existir por lo menos dos cuadrados perfectos cuyas u ´ltimas cifras sean B y C. Ahora, la u ´ltima cifra de cualquier cuadrado perfecto debe ser 0,1,4,5,6 o 9. Como C 0 entonces tenemos cinco casos que consideramos a continuaci´ on: C = 1. Todos los cuadrados perfectos de tres cifras terminados en 1 son 121, 361, 441, 841 y 961. Notemos que 361 y 961 tienen sus dos u ´ltimas cifras iguales al igual que los n´ umeros 441 y 841. Si Ana observa que B = 6 y C = 1 o b = 4 y C = 1 entonces no puede determinar cu´al es el valor de A. Si Bety observa que C = 1 tampoco puede determinar cu´ al es el valor de B. Para terminar este caso necesitamos considerar otros casos por lo tanto volveremos m´ as adelante a este caso. 6 Ejercicio

tomado del exanen D´ıa 1 III Eliminatoria 2006

7

C = 4. Todos los cuadrados perfectos de tres cifras terminados en 4 son 144, 324, 484 y 784. Entre estos n´ umeros tan s´ olo 484 y 784 tienen sus dos u ´ltimas cifras iguales. En este caso Ana no puede determinar cu´al es el valor de A, sin embargo si Bety observa que C = 4 puede determinar que B = 8 lo cual implica que este caso no es posible. C = 5. Entonces ABC = 225 o 625. Pero al igual que en el caso anterior si Bety observa que C = 5 despu´es de escuchar que Ana no puede saber cu´ anto es A entonces Bety puede deducir que B = 2. Entonces este caso tampoco es posible. C = 6. Tenemos que ABC puede ser 196, 256, 576 o 676. Los n´ umeros que tienen sus dos u ´ltimas cifras iguales en este caso son 576 y 676, pero razonando igual que en los casos anteriores se deduce que Bety puede encontrar B; por lo tanto tampoco es posible este caso. C = 9. Entonces ABC puede ser 169, 289, 529 o 729. Los cuadrados con sus dos u ´ltimas cifras iguales son 529 y 729. Igual que los casos anteriores, este caso tampoco es posible. Finalmente, volviendo al primer caso, despu´es de considerar todos los casos anteriores, concluimos que Carolina escucha que ni Ana ni Bety saben cu´ ales son sus respectivos d´ıgitos y observa que B = 4 o B = 6, Carolina puede concluir que C = 1.  ´ Ejercicio:7 Las familias Alvarez, Barboza, Carrillo y G´omez, viven en Atenas, Bagaces, Cahuita y Golfito (no necesariamente en ese orden). Las cuatro familias poseen un u ´nico autom´ovil. El color de esos autos es amarillo, blanco, celeste y gris (no necesariamente en ese orden. Indique cu´ al es el lugar de residencia de cada familia y el color de su respectivo auto, sabiendo que:

a) En cada caso, las iniciales del apellido de la familia, de su lugar de residencia y del color de su auto, son todas diferentes. ´ b) El auto de la familia Alvarez no es de color blanco. c) El auto de color gris no pertenece a la familia que vive en Cahuita. d) La familia G´ omez no vive en Bagaces. e) El auto celeste no es de la familia Barboza. f) El auto de la familia que vive en Golfito no es de color amarillo g) La familia Carrillo no vive en Atenas. h) El auto blanco no es de la familia G´ omez. i) El auto celeste pertenece a la familia que vive en Atenas. 7 Ejercicio

tomado del examen d´ıa 1 III Eliminatoria 2009

8

Soluci´ on Resolveremos este problema utilizando la siguiente tabla, en la que se ha considerado como punto de partida la condici´ on 1 que se da en el enunciado. Familia

Lugar de Residencia

Color de Auto

Condici´on

´ Alvarez

Bagaces

Celeste

FALSO (Condici´on i)

Gris Cahuita

Golfito

Barboza

Atenas

Blanco

FALSO (Condici´on b)

Gris

FALSO(Condici´on c)

Blanco

FALSO (Condici´on b)

Celeste

FALSO (Condici´on i)

Celeste

FALSO (Condici´on e)

Gris Cahuita

Amarillo

FALSO (Condici´on c)

Gris Golfito

Carrillo

Atenas

Bagaces

Amarillo

FALSO (Condici´on f)

Celeste

FALSO(condici´on e)

Blanco

FALSO (Condici´on g)

Gris

FALSO (Condici´on g)

Amarillo Gris

Golfito

Amarillo

FALSO (Condici´on f)

Blanco G´ omez

Atenas

Blanco

FALSO (Condici´on h)

Celeste Bagaces

Cahuita

Amarillo

FALSO (Condici´on d)

Celeste

FALSO(condici´on d)

Amarillo

FALSO (Condici´on h)

Blanco Ahora bien, como el auto celeste pertenece a la familia que vive en Atenas (condici´on i), la u ´nica posibilidad que se tiene es que pertenezca a la familia G´ omez. Con esto, nuestra tabla se ha reducido a la siguiente. Familia

Lugar de Residencia

Color de Auto

´ Alvarez

Bagaces

Gris

Barboza

Cahuita

Amarillo

Carrillo

Bagaces

Amarillo Gris

Golfito

Blanco 9

´ De donde es claro que la familia Alvarez vive en Bagaces y su auto es de color gris, mientras que la familia Barboza vive en Cahuita y su auto es de color amarillo. Luego la familia Carrillo debe vivir en Golfito y su auto debe ser de color blanco.

10