Maratón de Problemas

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por Nacho » Jue 22 Mar, 2012 7:57 pm

Spoiler: mostrar
Sea [math] la cantidad de personas en la fiesta. Numeramos las personas del [math] al [math]. Podemos armarnos una matriz de [math], donde el elemento [math] tiene un [math] si las personas [math], [math] son amigas y un [math] si no lo son. Luego, cada fila representa a los amigos que tiene cada persona, es decir, el [math]-ésimo componente del [math]-ésimo vector fila nos dice si son amigos o no lo son. Sean [math] estos vectores filas. La cantidad de amigos en común entre dos personas [math] y [math] es el producto escalar [math] ya que consiste en multiplicar componente a componente, y solo suma un [math] en el caso en que ambos componentes sean [math].

Dicho esto, consideremos todos los productos escalares. Si fijamos a una persona, wlog, a [math] y calculamos todos los productos escalares [math], vemos que de estos [math] productos escalares, [math] valen [math], ya que la condición del enunciado nos dice que si dos personas se conocen no tienen amigos en común. Luego, hay [math] productos que valen [math]. Ahora, fijamos cualquier otro número y hacemos lo mismo, de donde tenemos una suma de [math]. Pero tenemos que dividirla por [math], ya que cuando fijo cada valor, voy considerando [math]. Por lo tanto, la suma es [math].

Contar eso es lo mismo que contar pares de [math]'s en cada fila. Como tenemos [math] unos por fila, tenemos [math] maneras de contar esto.

Luego, [math].

Por lo tanto hay [math] personas en la fiesta.
Problema:

Hallar todos los enteros positivos [math] tales que:
[math]
"Though my eyes could see I still was a blind man"

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 152
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach » Sab 31 Mar, 2012 1:44 am

Spoiler: mostrar
Empiezo diciendo que, wlog, [math].
[math]. Si los tres números son mayores a [math]: [math], y [math] , [math]. Divido en ambos lados por [math] y tengo que [math] y como [math], [math], [math]. Absurdo por suponer que ambos números son mayores a 3.
Entonces por lo menos un número tiene que ser menor a [math].
Veamos qué pasa si [math] :
[math]. Ahora voy a dividir por [math] en ambos lados. Así tengo que [math].
Si [math], [math], pero [math].
Si [math], [math], entonces encontramos un conjunto posible, [math] y sus permutaciones.
Si [math], [math], pero [math], y [math].

Entonces con [math] no hay más posibilidades.

Si [math] :
[math].
Si ambos son impares, lo de la izquierda sería impar y lo de la derecha par.
Y si uno de los fuera par y el otro impar, lo de la izquierda sería par y lo de la derecha impar.
Entonces ambos números son pares.
Si [math] , [math] , [math]. [math] , entonces [math] y sus permutaciones cumplen con lo pedido.
Si [math] , [math] y [math] , [math], entonces [math]. Pero al principio dijimos que [math].
Entonces no hay más tríos posibles y los únicos que cumplen con lo pedido son [math], [math], [math], [math], [math], [math] y [math], [math], [math].
Problema:

En el pizarrón están escritos los cuadrados de los primeros 101 números enteros positivos:

[math], [math], [math], ... [math], [math]

Hay que escribir delante de cada número un signo [math] o un signo [math] de manera que al realizar la suma algebraica de los 101 números se obtenga el menor valor mayor o igual que cero que sea posible. Determinar cuál es ese mínimo e indicar como se distribuyen los signos para lograrlo.

Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Maratón de Problemas

Mensaje sin leer por Vladislao » Jue 05 Abr, 2012 1:59 pm

Spoiler: mostrar
Como la suma inicial de los numeritos del pizarrón es [math], si intercalamos signos de suma o resta entre los mismos, es sencillo ver que la paridad de la suma es invariante, en particular, no podemos lograr que la suma sea 0, dado que 0 es par. De esto deducimos que el menor valor posible es el 1. Aquí hay una distribución de signos que funciona:

Primero notemos que para todo [math] vale que: [math]

Es decir, podemos alternar signos más y menos en la suma de 8 cuadrados consecutivos para obtener un 0.

Hacemos eso con todos los cuadrados desde [math] hasta [math] (son 88).

Con los demás, hacemos:

[math].

Y ganamos.
Problema

Diremos que un entero positivo es anual si tiene un múltiplo tal que sus primeras [math] cifras desde la izquierda sean [math], [math], [math], [math] (en ese orden). Demostrar que todos los enteros positivos son anuales.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 152
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach » Mar 10 Abr, 2012 11:35 pm

Spoiler: mostrar
Si queremos ver que un número [math] de [math] cifras es anual, escribimos el número [math]. Este número puede tener, como resto en la división por [math], los números del [math] al [math]. Si es 0 ya ganamos; si no, vamos a sumar al número que teníamos a lo sumo [math], y como las últimas [math] cifras eran [math] y [math] tiene [math] cifras, el número va a comenzar con [math] y va a ser múltiplo de [math].
[math]
Problema nuevo

Hallar el mínimo número natural [math] con la siguiente propiedad: entre cualesquiera [math] números distintos, pertenecientes al conjunto {[math]} se puede elegir cuatro números diferentes [math], tales que [math].

Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 295
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: Maratón de Problemas

Mensaje sin leer por ésta » Mié 25 Abr, 2012 7:46 pm

Spoiler: mostrar
El problema es equivalente a encontrar el mayor [math] tal que existe un conjunto de [math] elementos tal que no se puedan elegir [math] distintos que cumplan esa cuenta.
Sea [math] un subconjunto de [math] tales que no hay [math] distintos tal que [math], vamos a tratar de acotar la cantidad de elementos de [math], supongamos que hay al menos dos elementos en [math].

sean [math] los dos elementos de [math] más chicos.
Si [math], hay a lo sumo [math] elementos en [math] mayores a [math], entonces [math] tiene a lo sumo [math] elementos.

Supongamos que [math].
Por la condición, no hay dos elementos [math] de [math] que difieran en [math] ya que sino [math].
Entonces si [math] con [math], sabemos que [math] pero [math]. Esto nos dice que por cada elemento de [math] no muy grande, hay un número menor a [math] que no ésta en [math], y además es distinto para cada [math].

Sea [math] la cantidad de elementos de [math] menores o iguales a [math] y mayores a [math], y [math] los mayores a [math].
Como por cada elemento de los [math] hay uno (mayor a [math]) que no ésta en [math], y hay [math] números mayores a [math] y menores a [math], tenemos que [math].
Entonces la cantidad de elementos de [math] mayores a [math] es [math].

Ahora hay a lo sumo [math] mayores a [math] y menores a [math], entonces [math], y como [math], [math].

Volvemos a [math],
[math].
Pero la cantidad de elementos de [math] es a lo sumo [math] ya que hay [math] elementos menores o iguales a [math]. Sigue que [math] tiene a lo sumo [math] elementos.

Finalmente, damos un ejemplo con [math] elementos, tomamos [math], sean [math] tres elementos distintos de [math], entonces [math], entonces no existe [math] tal que [math], y por lo tanto funciona este ejemplo.
Problema número 55:
Definimos la sucesión de Fibonacci como [math], [math] y [math] (con [math]).
Hallar todos los enteros positivos [math] tal que [math] es primo.
Imagen

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 152
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach » Jue 26 Abr, 2012 9:20 pm

Spoiler: mostrar
Bueno, vamos a demostrar que [math].
Primero vemos que [math].
Ahora, por inducción, vemos que si para [math] se cumple [math] para [math] también.
Tenemos que [math] se cumple para algún [math].
Ahora, [math]
Resolvemos los paréntesis: [math]
Pero teníamos que [math]
[math] [math]
También tenemos que [math] [math]
Si llevamos [math] a [math] tenemos que:
[math] que claramente se cumple. Entonces tenemos demostrada nuestra inducción, y como vale para [math], vale también para todo [math].
Entonces [math] va a ser siempre producto de [math] números, y nunca va a ser primo, a menos que [math], que solo se cumple para [math]. [math]

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 152
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach » Jue 26 Abr, 2012 9:28 pm

Problema nuevo:
Hallar todos los pares de enteros [math] con [math], [math], tales que [math] divide a [math] y [math] divide a [math].

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por Nacho » Dom 29 Abr, 2012 11:45 pm

Solución
Spoiler: mostrar
Es un problema relativamente estándar, solo que hay que tener mucho cuidado con todos los casitos:

Como [math] existe un [math] tal que [math], de donde [math]. El enunciado nos dice que [math]. Se sigue entonces que [math]. Es claro que si divide a eso, entonces [math] y entonces [math].

Luego, sabemos que [math] con [math] entero. Organicemos una cuadrática: [math].

El discriminante de eso tiene que ser un cuadrado perfecto para que tenga solución. [math].

Acá es donde tenemos que tener mucho cuidado. Miremos tres casos: [math], [math] y [math].

Si [math], entonces se sigue que [math]. Como [math] nos queda [math]. Luego, tenemos soluciones de la forma [math] que es trivial ver que andan.

Si [math], entonces [math]. Pero además, es claro ver que [math]. Vemos que eso pasa sii [math]. Notemos entonces que si [math] vamos a obtener [math]. Y el caso [math] nos da [math]. Pero como [math] debemos tener [math], que nos da que [math] que no tiene raíces enteras. [math] nos da [math]. Luego, si tenemos [math] nos va a pasar que [math]. Entonces, como no queremos que eso pase (ya que el discriminante es un cuadrado y no puede estar entre dos cuadrados), vamos a ver los casos [math] y [math].

El caso [math] nos da [math], y así [math]. Tenemos entonces las soluciones [math] que es trivial ver que funcionan.

El caso [math] nos da [math] que es una cuadrática en [math]. Miremos su discriminante: [math]. Notemos que como [math], tenemos que [math]. Además, es claro que [math]. Entonces, [math], que nos conduce a un claro absurdo.

Ahora exploremos el caso [math]. Entonces [math]. Pero además, es claro ver que [math]. Estamos en una situación simétrica a la anterior, entonces sólo debemos ver como antes los casos [math] y [math].

Si [math] luego [math] y así [math]. Y así [math] es solución.

Si [math] luego [math] y así [math] que es solución.

Ya analizamos todos los casos, entonces podemos concluir que las soluciones son: [math].
Problema nuevo:

Dado un par ordenado de números naturales [math], las operaciones permitidas son reemplazar el par [math] por el par [math] o reemplazar el par [math] por el par [math]. Determinar todos los naturales [math] tales que, a partir del par [math] y mediante una secuencia de operaciones permitidas se puede obtener el par [math].
"Though my eyes could see I still was a blind man"

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 152
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach » Dom 06 May, 2012 10:16 pm

Che hace un montón está este problema, no querés poner la solución Nacho? O alguien...?
Así seguimos la maratón :P

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por Nacho » Mar 08 May, 2012 12:40 am

Solución del problema pendiente:
Spoiler: mostrar
Voy a tirar el esquema de la solución y me voy a saltear un par de inducciones que salen fácil (capaz mañana edito y lo completo bien bien).

Vamos a proceder al revés, es decir, vamos a definirnos la operación inversa y llegar desde un par [math] hasta [math]. La operación inversa es del tipo A si [math] ó del tipo B si [math].

Vemos que [math] es de la forma [math]. Luego, aplicamos WLOG una operación del tipo A [math]. Luego, [math] tiene que ser de la forma [math] ya que no hay cuadrados entre [math] y [math]. Lo mismo va a pasar con [math].

Nos definimos la sucesión de números [math] de manera tal que [math] para [math] y [math] arbitrario. Notemos que tras [math] operaciones vamos a llegar a [math]. Notemos también que si tenemos iniclamente el par [math], vamos a tener que hacer al menos [math] operaciones para llegar a poder hacer una operación del tipo B. Pero una inducción nos dice que [math], de donde no podemos llegar a hacer una operación del tipo B porque no podríamos hacer la suficiente cantidad de operaciones del tipo A necesarias.

Luego, todas las operaciones son del tipo A.

Ahora, definimos la sucesión [math], de manera tal que [math] (Es decir, sumo siempre uno).

(O sea, básicamente [math] y [math] son las operaciones en orden normal).

Miro dos casos: [math] y [math].

Notemos que [math] ya que la dupla es [math].

Para el primer caso, veamos por inducción que [math] para [math], de donde [math]. Por lo tanto limitamos [math] y explorando los casos hallamos [math] es la única solución.

Para el segundo caso, de nuevo por inducción, vemos más rápido que [math] para todo [math]. De donde no tiene solución.

Entonces, la única dupla de la forma [math] a la que se llega es [math]. (El procedimiento para ver que podemos llegar se logra fácil, así que no lo copio. Es más, usando las operaciones inversas, se alcanza fácil). Y estamos. [math]
Problema Nuevo:

Demostrar que la expresión [math] es un entero para todo par de enteros positivos [math] con [math].
"Though my eyes could see I still was a blind man"

Responder