EL ARTE DE CONTAR
[Link] principios básicos
i) El principio de multiplicación (o de los pastores)
Si una operación se puede realizar de r formas distintas, y una segunda
operación se puede realizar de s formas distintas, entonces las dos operaciones
en sucesión se pueden realizar de r s formas distintas.
ii)El principio del palomar (Dirichlet)
Dados n agujeros y mn + 1 palomas metidas en ellos, existe un agujero que
contiene por lo menos m + 1 palomas.
Generalización : S upongamos que N objetos han de distribuirse en k cajas
(k < N ). Entonces, al menos una caja contiene un número de objetos mayor o
igual que [N=k] + 1; si k no divide a N. Si k divide a N, ese número de objetos
es mayor o igual que N=k:
Demostración
Si las k cajas contuvieran menos de [N=k]+1 objetos, entre todas contendrían
un número de objetos menor o igual que k [N=k] < N; lo cual es absurdo.
Ejemplos :
1)Hay 5 puntos en el interior de un cuadrado deplado 2. Probar que hay 2
de esos puntos cuya distancia es menor o igual que 2:
2)Demostrar que, dados 7 números reales cualesquiera, siempre es posible
elegir dos de ellos, x; y tales que
x y 1
0< <p
1 + xy 3
(25 OME, Fase nacional)
iii)La fórmula de inclusión y exclusión.
Representaremos con #(A) el número de elementos del conjunto …nito A.
Sean A1 ; A2 ; ; Am conjuntos …nitos. Entonces:
m
! m
[ X X
# Ai = # (Ai ) # (Ai \ Aj ) +
i=1 i=1 i<j
m
!
X n 1
\
# (Ai \ Aj \ Ak ) + ( 1) # Ai
i<j<k i=1
El número total de términos que intervienen en la fórmula es
m m m
m+ + + + = 2m 1
2 3 m
Vamos a comprobar que en el segundo miembro de la fórmula cada elemento
S
de i Ai se cuenta exactamente una vez. En primer lugar, es claro que los
1
elementos que no están en ninguno de los Ai no se cuentan ninguna vez en ese
segundo miembro.
Supongamos que un elemento x pertenece exactamente a h 1 de los con-
juntos Ai . No hay inconveniente en suponer que se trata de los h primeros :
x 2 A1 \ A2 \ \ Ah , pero x no está en ninguno de los demás.
Entonces, x se contará una vez en cada uno de los h sumandos #(A1 ) ; ; # (Ah ) ;será
descontado (contado negativamente) en cada uno de los h2 términos # (Ai \ Aj )
que se obtienen al poner 1 i j h ; hay ese número de términos porque hay
ese número de maneras de elegir los enteros i,j de entre los números 1; 2; ; h:
Análogamente, x se contará positivamente en h3 de los términos #(Ai \ Aj \ Ak ) ; etc:
Por lo tanto el número de veces que x es contado positiva o negativamente
es
h h h h 1 h
+ + ( 1)
1 2 3 h
y debemos probar que esto es igual a 1.
En efecto, del binomio de Newton
h h h h h 1 h h
(a + b) = a + a b+ + b
0 1 h
en el caso particular a = 1; b = 1 da
h h h h
0= + + ( 1)
0 1 h
es decir
h h h h 1 h
1= = + ( 1) ( 1)
0 1 2 h
como queríamos demostrar.
[Link]ón combinatoria
Permutaciones sin repetición de n elementos :
Pn = n! = n(n 1)(n 2) 3 2 1
Variaciones con repetición de n elementos tomados de k en k :
0
Vn;k = nk
Variaciones sin repetición de n objetos tomados de k en k :
Vn;k = n(n 1)(n 2) (n k + 1)
Combinaciones sin repetición de n objetos tomados de k en k :
2
n n (n 1) (n k + 1) n! Vn;k
Cn;k = = = =
k k! k! (n k)! Pk
Permutaciones con repetición de n objetos, de los que son iguales entre sí,
son iguales entre sí; iguales entre sí, con + + + =n
n!
P n; ; ; =
! ! !
Combinaciones con repetición de n objetos tomados de k en k :
0 n+k 1
Cn;k = = Cn+k 1;k
k
Propiedades de los números combinatorios
n n
=
k n k
n n 1 n 1
= +
k k 1 k
n n
es el coe…ciente de xk y n k
en (x + y)
k
n
X m k k+1 n n+1
= + + + =
k k k k k+1
m=k
n
X1 n+1
r (n r) =
r=1
3
1 n 1 n 1
=
n k k k 1
4.3.Fórmula de Leibniz para la potencia de un polinomio
n
X n!
(a + b + c + + k) = a b k
! ! !
donde ; ; ; toman todos los valores posibles de tal manera que +
+ + = n:
[Link] (Permutaciones sin puntos …jos)
Una permutación de los números f1; 2; ; ng se llama una desordenación
cuando ningún número está en su lugar primitivo. Por ejemplo, 2143 y 3142 son
desordenaciones, pero 1342 no. Para calcular el número Dn de desordenaciones,
se de…ne
3
Ai = Conjunto de permutaciones de f1; 2; ; ng
tales que el elemento i ocupa el i ésimo lugar,
i 2 f1; 2; ; ng :
Queremos calcular el número de elementos del conjunto de todas las per-
mutaciones de f1; 2; ; ng que pertenecen a exactamente cero de los conjuntos
A1 ; A2 ; ; An : Usaremos la fórmula de inclusión y exclusión. Tenemos
S0 = # ( ) = n!
Xn n
X
S1 = # (Ai ) = (n 1)! = n (n 1)! = n!
i=1 i=1
X X n!
S2 = # (Ai \ Aj ) = (n 2)! = Cn;2 (n 2)! =
2!
1 i<j n 1 i<j n
X X n!
S3 = # (Ai \ Aj \ Ak ) = (n 3)! = Cn;3 (n 3)! =
3!
1 i<j<k n 1 i<j<k n
..
.
n!
Sn = Cn;n (n n)! =
n!
El número de elementos de que pertenecen a exactamente cero de los
conjuntos A1 ; A2 ; ; An es
n
X0 k
a0 = ( 1) C0+k;k S0+k
k=0
n
X k
= ( 1) Sk
k=0
n
= S0 S1 + S2 S3 + + ( 1) Sn
n! n! n n!
= n! n! + + + ( 1)
2! 3! n!
n
1 1 1 1 ( 1)
= n! + + +
0! 1! 2! 3! n!
n!
Se puede demostrar que Dn es el entero más próximo a e :
Otras propiedades de Dn :
i) Si n 3; Dn = (n 1) (Dn 1 + Dn 2 )
ii) Poniendo D0 = 1;
n n n n
n! = Dn + Dn 1 + Dn 2 + + D0
0 1 2 n
4
n
iii)Si n 2; Dn = nDn 1 + ( 1) :
4.5. Los lemas de Kaplansky
¿De cuántas maneras es posible formar un subconjunto de tamaño p (es
decir, con p elementos) del conjunto f1; 2; ; ng, en el cual no haya números
consecutivos? Por ejemplo, para n = 6 y p = 3; podemos obtener a partir de
f1; 2; 3; 4; 5; 6g los siguientes subconjuntos de cardinal 3 sin elementos consecu-
tivos:
f1; 3; 5g ; f1; 3; 6g ; f1; 4; 6g ; f2; 4; 6g
Vamos a buscar un procedimiento que nos permita contar estos subconjuntos
sin enumerarlos exhaustivamente. Al formar un subconjunto, marcamos con +
los elementos que formarán parte del subconjunto y con signo - lo que no. Así
f1; 3; 5g ! + + +
f2; 3; 6g ! ++ + (éste no es válido)
Ahora bien, para formar un subconjunto de cardinal 3 sin elementos consec-
utivos, debemos colocar tres signos + y tres signos - en …la, sin que haya dos
signos + consecutivos. Para eso, colocamos los signos menos (de 1 sola manera),
y colocamos los signos + en los cuatro espacios de la …gura (de 43 maneras)
^ ^ ^ ^
La respuesta es, entonces, 1 C4;3 = 4 maneras.
En el caso general tenemos p signos + y n p signos , para colocar de
manera que no haya dos signos + consecutivos. Hay una única manera de
colocar los signos y Cn p+1;p maneras de colocar los signos más. Hemos
obtenido así el
Primer Lema de Kaplansky: El número de p-subconjuntos de f1; 2; ; ng
en los cuales no hay números consecutivos es
n+p 1
f (n; p) = :
p
Supongamos ahora que los elementos de f1; 2; ; ng están dispuestos en
círculo, como en la …gura :
Ahora los elementos 1 y n son consecutivos. ¿De cuántas maneras es posible
formar un p subconjunto de f1; 2; ; ng en el que no haya números consecu-
tivos?
El número total de subconjuntos en cuestión será la suma del número de
subconjuntos en los que esté el 1 con el número de subconjuntos en los que no
esté el 1.
5
a)Subconjuntos en los que …gura el 1. Para formarlos debemos escoger p 1
elementos en f3; 4; ; n 1g (Pues si …gura el 1 no pueden estar 2 ni n) para
ser los compañeros del 1, no pudiendo elegirse elementos consecutivos. Eso
puede hacerse (por el primer lema) de
n 3 (p 1) + 1 n p 1
f (n 3; p 1) = = maneras.
p 1 p 1
b) Subconjuntos en los que no esté el 1. Para formarlos debemos elegir p
elementos de f2; 3; ; ng sin elementos consecutivos. Eso puede hacerse de
n 1 p+1 n p
f (n 1; p) = = maneras.
p p
Por lo tanto la respuesta es
n p 1 n p (n p 1)! (n p)!
+ = +
p 1 p (p 1)! (n 2p)! p! (n 2p)!
(n p 1)!p + (n p)!
=
p! (n 2p)!
p + (n p)
= (n p 1)!
p! (n 2p)!
(n p 1)!
= n
p! (n 2p)!
n (n p)!
=
n p p! (n 2p)!
n n p
=
n p p
Así hemos obtenido el
6
Segundo Lema de Kaplansky
El número de p subconjuntos de f1; 2; ; ng en los cuales no hay números
consecutivos, considerando a 1 y n como consecutivos, es
n n p
g(n; p) = :
n p p
Generalización del Primer Lema de Kaplansky
¿De cuántas maneras es posible formar un p subconjunto de f1; 2; ; ng
de modo que entre cada dos elementos escogidos para el subconjunto haya, en
el conjunto, al menos r elementos no escogidos para el subconjunto?
La respuesta es n (pp 1)r :
Generalización del segundo Lema de Kaplansky
Rehacer el problema anterior en el caso circular. En ese caso, por ejemplo,
tomando n = 6, el conjunto f1; 2; 3; 4; 5; 6g es tal que entre 1 y 4 hay 2 elementos,
entre 5 y 1 hay 1 elemento, entre 6 y 4 hay 3 elementos. Sugerencia: dividir los
subconjuntos en dos grupos: los que contienen alguno de los elementos 1; 2; ;r
y los que no contienen ninguno de los elementos 1; 2; ; r:
La respuesta es n npr n ppr :
Problemas olímpicos de Combinatoria
Problema 1
Demostrar que el producto
2 2 2 2
4 4 4 4
1 2 3 n
es un entero, cualquiera que sea el número natural n:
(Olimpiada de Chequia)
Solución
Escribimos el factor 4 k2 , con 1 k n;en la forma
2 4k 2 2 (2k 1) 2k (2k 1)
4 = = =
k k k k2
así que el producto en cuestión es de la siguiente forma:
2:1 4:3 6:5 2n (2n 1) (2n)! 2n
= =
1:1 2:2 3:3 n:n n!n! n
que es evidentemente un entero.
Problema 2
Un condenado queda en libertad cuando alcance el …nal de una escalera de
100 escalones, estando obligado a subir un sólo escalón cada día de los meses
impares, y a bajar un escalón cada día de los meses pares. Comienza el 1 de
enero de 2001. ¿Qué día quedará en libertad?
¿Qué día quedaría en libertad si la escalera tuviera 99 escalones?
(O.M.E.2001, Fase local)
Solución
Solución o…cial
7
El avance en un año no bisiesto es 3+1+1+0-1-1 = 3 escalones, y en un año
bisiesto es 2 escalones, de manera que si un 31 de diciembre está en el escalón n,
el siguiente año termina en el escalón n + 3, y en el n + 2 si ese año es bisiesto.
El punto más alto lo alcanza el 31 de julio, donde ha avanzado n + 5+31
escalones en un año no bisiesto, y n + 4 + 31 en año bisiesto.
El 31 de julio de 2024 llega al escalón 99 (lo que contesta a la segunda
pregunta del problema), el 31 de diciembre de 2024 llega al 66; y en 2025, el 31
de enero termina en el 97; el 28 de febrero en el 69, y el 31 de marzo, en el 100.
Con 100 escalones, el 31 de marzo de 2025
Con 99 escalones, el 31 de julio de 2024
Problema 3
Sea n un número natural cualquiera. Demostrar que, para todo k 2 N con
k n, el número
P = (n + 1) (n + 2) (2n 1) (2n)
k
es divisible por 2 :
(Olimpiada de la URSS)
Solución
Completemos el producto hasta que aparezcan factoriales :
1 2 3 n (n + 1) (n + 2) (2n 1) (2n)
P =
n!
(2n)! 1 (2 1) 3 (2 2) 5 (2 3) (2n)
= =
n! n!
2n 1 2 n [1 3 5 (2n 1)]
=
n!
= 2n [1 3 5 (2n 1)]
que es más que lo que pide el problema.
Problema 4
Un subconjunto A M = f1; 2; 3; ; 11g es majo si tiene la siguiente
propiedad :
Si 2k 2 A; entonces 2k 1 2 A y 2k + 1 2 A:
(Se supone que ; y M son majos).
¿cuántos subconjuntos majos tiene M?
(Concurso Abel de Noruega, 1989)
Solución
Consideremos los subconjuntos de M formados por los números pares e im-
pares:
P = f2; 4; 6; 8; 10g ; I = f1; 3; 5; 7; 9; 11g :
8
Un subconjunto majo de M puede contener :
a) Exclusivamente números impares. Como card(I) = 6, subconjuntos de
esta clase hay 26 , entre los que se cuenta el conjunto vacío (que es majo por
hipótesis).
b) Un único número par (por ejemplo, f1; 2; 3g) : hay 51 maneras de elegir
en P un número par ; obligatoriamente hay que incluir a los impares inmediata-
mente anterior y posterior a ese número par; luego hay 4 números impares que
pueden formar parte del subconjunto; con ellos se pueden formar 24 subconjun-
tos.
Luego de este tipo habrá
5
24
1
subconjuntos majos.
c) Dos números pares consecutivos (ej. f1; 2; 3; 4; 5g).
Hay que incluir en A tres números impares, y quedan libres otros tres
impares. Hay 4 subconjuntos con dos números pares consecutivos (que son
f2; 4g ; f4; 6g ; f6; 8g ; f8; 10g); y 23 subconjuntos que se pueden formar con los
otros tres : de este tipo hay
23 4:
d) Con dos números pares no consecutivos hay 6 subconjuntos de P, y hay
que incluir cuatro números impares necesariamente (ej. f1; 2; 3; 5; 6; 7g), así que
quedan 2 impares libres , con los que se forman 22 subconjuntos para combinar
con aquellos : luego son
6 22 subconjuntos.
e)Con tres números pares consecutivos hay 3 subconjuntos de P :
f2; 4; 6g ; f4; 6; 8g y f6; 8; 10g, en los que habrá que incluir cuatro números
impares, quedando 2 libres : el número de subconjuntos majos de este tipo es
3 22 :
f) Con tres números pares, dos de ellos consecutivos, hay 6 subconjuntos de
P:
f2; 4; 8g ; f2; 4; 10g ; f4; 6; 10g ; f2; 6; 8g ; f2; 8; 10g y f4; 8; 10g :
para los que hacen falta 5 números impares, quedando sólo 1 libre; de esta
clase habrá entonces
6 21
subconjuntos majos.
g) Con tres números pares, ninguno de ellos consecutivos, hay 1 subconjunto
de P : f2; 6; 10g ; que ya utiliza todos los impares, luego en este caso sólo tenemos
9
subconjunto majo.
h) Con cuatro números pares, puede ocurrir :
h1 ) que no esté el 4, el 6 ó el 8. En este caso hacen falta todos los impares,
y hay
3 1
subconjuntos majos.
h2 ) que no esté el 2 ó el 10. En este caso hay un número impar que no hay
que usar, y tenemos
2 21
subconjuntos majos.
i) Con 5 números pares, hay que poner todos los impares y se tiene el conjunto
M:
1
subconjunto majo.
Por lo tanto se tiene en total
26 + 24 5 + 23 4 + 22 6 + 3 22 + 6 21 + 1 + 3 1+2 2+1
= 64 + 80 + 32 + 24 + 12 + 12 + 1 + 3 + 4 + 1 = 233
subconjuntos majos.
Problema 5
Sea A un conjunto con 8 elementos. Hallar el máximo números de subconjun-
tos de A, de 3 elementos cada uno, tales que la intersección de dos cualesquiera
de ellos no es un conjunto de 2 elementos.
(Olimp. de Bulgaria)
Solución
Sean B1 ; B2 ; ; Bn subconjuntos de A; con jBi j = 3; jBi \ Bj j 6= 2; para
i; j = 1; 2; ; n:
Supongamos que exista un elemento a 2 A que pertenezca a cuatro de los
subconjuntos Bi (no hay inconveniente en suponer que son B1 ; B2 ; B3 y B4 ).
Entonces jBi \ Bj j 1; i; j = 1; 2; 3; 4:
Pero Bi 6= Bj si i 6= j, es decir jBi \ Bj j 6= 3: Entonces jBi \ Bj j = 1 ,
i; j = 1; 2; 3; 4: De aquí se deduce que jAj 1 + 4 2 = 9; lo cual es una
contradicción. Por lo tanto, todo elemento de A pertenece a lo sumo a tres de
los conjuntos Bi . Entonces 3n 8 3 =) n 8:
Demos un ejemplo que prueba que el máximo es 8 :
A = f1; 2; 3; 4; 5; 6; 7; 8g
B1 = f1; 2; 3g ; B2 = f1; 4; 5g ; B3 = f1; 6; 7g ; B4 = f3; 4; 8g
B5 = f2; 6; 8g ; B6 = f5; 7; 8g ; B7 = f3; 5; 6g ; B8 = f2; 4; 7g :
10
Problema 6
Seis músicos participan en un festival de música. En cada concierto, algunos
de esos músicos tocan y los demás escuchan. ¿Cuál es el mínimo número de
conciertos necesario para que cada músico escuche a todos los demás?
(Torneo de las Ciudades)
Solución
Sean A,B,C,D,E y F los músicos. Examinemos la situación con 3 conciertos.
Como cada uno de los 6 toca al menos una vez, por lo menos hay un concierto
en el que tocan 2 ó más músicos. Supongamos que A y B tocan en el primer
concierto. Como cada uno de ellos debe escuchar al otro, supongamos que A
toca en el 2o concierto (B no) y B en el 3o (A no). En el 2o concierto, C,D,E y
F tienen que tocar, ya que es la única vez que B escucha. Por la misma razón
(referida a A), tienen que tocar en el tercero. El primer concierto sólo no es
bastante para permitir que C,D,E y F toquen cada uno para los demás. Por lo
tanto, hacen falta más de 3 conciertos.
Es su…ciente con 4 conciertos:
ABC; ADE; BDF; CEF:
Problema 7
¿De cuántas maneras se pueden sentar p caballeros y q damas a una mesa
redonda si cada dama tiene la posibilidad de escoger entre sentarse en una silla
o en las rodillas de un caballero (mientras haya caballeros libres)?
(American Mathematical Monthly 1942, prop. por [Link])
Solución (de [Link] Voorhis)
Sea m el número de damas que eligen sentarse en las rodillas de algún ca-
ballero. Entonces, los p caballeros y las q m damas desdeñosas pueden sentarse
q
de (p + q m 1)! formas. Las damas complacientes pueden ser elegidas de m
formas. Para la primera de ellas hay p caballeros disponibles; para la segunda,
p 1; etc: Luego pueden sentarse de
q
(p + q m 1)! p (p 1) ::: (p m + 1) f ormas:
m
Sumando para los posibles valores de m se obtiene el número total de formas
como
min(p;q)
X p q
m! (p + q m 1)!
m=0
m m
Nota editorial del Monthly:
Si los caballeros son …jos, hay que dividir el resultado por (p 1)!; resultando
min(p;q)
X p p+q m 1
q! ;
m=0
m p 1
p
1+x
que es q! veces el coe…ciente de xq en el desarrollo de 1 x :
11
Problema 8
Sea X un conjunto de n elementos y F una familia de subconjuntos de X,
todos con tres elementos cada uno, de tal manera que dos subconjuntos cua-
lesquiera de F tienen, a lo sumo, un elemento
p en común. Demostrar que existe
un subconjunto de X, con, al menos, 2n elementos, y que no contiene ningún
subconjunto de F.
(Olimpiada de Brasil, 1996)
Solución o…cial.
Sea M un subconjunto de X que no contiene ningún subconjunto de la familia
F y sea maximal con respecto a esta propiedad, es decir,
para todo x 2 X M hay un subconjunto B 2 F tal que B M [ fxg ;
esto es, para todo x 2 X M existe un subconjunto que llamaremos Ax M;
con 2 elementos (n (Ax ) = 2 ), tal que fxg [ Ax 2 F.
De esta forma se puede de…nir una función
f :X M ! P2 (M ) ;
donde P2 (M ) representa el conjunto cuyos elementos son todos los subcon-
juntos de M que tienen 2 elementos.
Vamos a ver que f es inyectiva:
Ax = Ay ) n [(fxg [ Ax ) \ (fyg [ Ay )] 2
n [(fxg [ Ax ) \ (fyg [ Ay )] = 3 ) x = y
Ya que f es inyectiva,
n (X M) n (P2 (M )) ;
luego si n (M ) = r; entonces
2
r r (r 1) 1 1
n r () n r () r+ 2n +
2 2 2 4
y de aquí se deduce
r $r %
1 1 1 jp k
r+ 2n + 2n + 2n :
2 4 4
p
Ya que r 2 N, r 2n :
Problema 9
Problema 3 de la I.M.O. 1973, propuesto por Inglaterra
Sean k y n enteros no negativos. Demostrar que
(2k)! (2n)!
k!n! (k + n)!
es un entero.
12
Solución 1
Aunque hay procedimientos ”casi standard” para probarlo, daremos una
solución ”de idea feliz”.
Sea
(2k)! (2n)!
P (k; n) = ;
k!n! (k + n)!
y observemos que P (k; 0) = (2k)!k!k! =
2k
k es un entero. Busquemos una
relación de recurrencia, del estilo de la que veri…can los coe…cientes binomiales,
que sea cumplida por P (k; n): Para ello pongamos
P (k; n) = A:P (k; n 1) + B:P (k + 1; n 1)
y busquemos los valores de A y B. Si son enteros, habremos dado el primer
paso. El segundo miembro de la expresión anterior se puede poner como
(2k)! (2n 2)! (2k + 2)! (2n 2)!
A: + B:
k! (n 1)! (k + n 1)! (k + 1)! (n 1)! (k + n)!
y como el denominador interesa que sea k!n!(k + n)! tendremos que escribir
el numerador como
Bn (2k + 2)! (2n 2)!
An(k + n) [(2k)! (2n 2)!] +
k+1
así que la relación que buscamos se convierte en
Bn(2k + 2)(2k + 1)
(2k)! (2n)! = (2k)! (2n 2)! An(k + n) +
k+1
Simpli…cando resulta
Bn(2k + 2)(2k + 1)
2n(2n 1) = An(k + n) +
k+1
Quitando denominadores e identi…cando coe…cientes resulta
4n2 k + 4n2 2nk 2n = An2 k + (A + 4B) k 2 n + An2 + (A + 6B) kn + 2Bn
es decir
A = 4; A + 4B = 0; A + 6B = 2; 2B = 2
A = 4; B = 1
Por lo tanto, se veri…ca
P (k; n) = 4:P (k; n 1) P (k + 1; n 1) (1)
13
Aplicando la igualdad (1) por segunda vez, obtenemos
P (k; n) = 16P (k; n 2) 8P (k + 1; n 2) + P (k + 2; n 2)
y aplicándola n veces llegaremos a
n
X
P (k; n) = ar :P (k + r; 0)
r=0
donde los ar son enteros. Pero ya vimos que P (k + r; 0) es entero, así que
la proposición queda demostrada por recurrencia.
Generalizaciones y extensiones
1) Si k; n1 ; :::; nk 2 N , entonces
(kn1 )! (kn2 )!:::(knk )!
k 1 k 1
(n1 !) (n2 !) :::(nk !)k 1 (n1 + n2 + ::: + nk )!
es entero.
2)Si k; n 2 N , probar que k+n k divide al producto 2k
k :
2n
n :
(5k)!(5n)!
3) Si k; n 2 N , probar que n!k!(3k+n)!(3n+k)! es entero.
4) Si n1 ; :::; nk ; k 2 N , entonces
(n1 + ::: + nk )!
es entero.
n1 !:::nk !
h i
(n 1)!
5) Si n 2 N; n 6; demostrar que n(n+1) es par.
6) Si k; n 2 N demostrar que
n2 ! (kn + 1)!
n y k
(n!) (n!)
son enteros.
Problema 10
Para cada entero positivo n, sea f(n) el máximo común divisor de n! + 1 y
(n + 1)!:
Encontrar, razonadamente, una fórmula que dé f(n) para cada n.
([Link] Irlanda 1996)
Solución o…cial.
Supongamos que n + 1 no es primo. Entonces todo primo p que divida a
(n + 1)! divide a uno de los números 1; 2; 3; :::; n; y por lo tanto divide a n! ,
pero no a n! + 1: De aquí que
f (n) = 1 si n + 1 no es primo.
Supongamos ahora que n + 1 = p es primo. Sea q un primo distinto de p
que divida a (n + 1)!. Entonces q n, luego q divide a n! y en consecuencia no
divide a n! + 1; así que tampoco divide a f (n) : De aquí que f (n) = p para
14
algún entero 0: Ahora bien, p2 no divide a (n + 1)!; luego 1. Por otra
parte, el teorema de Wilson dice que
(p 1)! 1 modp si p es primo.
Luego p divide a n! + 1 ya que p 1 = n: Entonces p divide a f (n) y = 1:
Por lo tanto, la fórmula buscada es
1 si n + 1 no es primo
f (n) =
n + 1 si n + 1 es primo
Problema 11
Un poliedro convexo dado no tiene ningún vértice en el que concurran exac-
tamente 3 aristas. Probar que el número de caras triangulares del poliedro es
mayor o igual que 8.
(Competición Israel-Hungría 1996)
Solución o…cial.
Sean v; e; f el número de vértices, aristas y caras,respectivamente, del poliedro;
vi el número de vértices de grado i; fi el número de caras con i aristas. Se tiene:
v = v4 + v5 + v6 + :::
f = f3 + f4 + f5 + :::
2e = (3v3 = 0) + 4v4 + 5v5 + :::
2e = 3f3 + 4f4 + 5f5 + :::
Según la fórmula de Euler, 4v + 4f = 4e + 8 = 2e + 2e + 8
es decir
4 (v4 + v5 + :::) + 4 (f3 + f4 + :::) = (4v4 + 5v5 + :::) + (3f3 + 4f4 + :::) + 8;
o lo que es lo mismo,
f3 = 8 + (v5 + 2v6 + :::) + (f5 + 2f6 + :::) 8; c.q.d.
15
