La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
domingo, 28 de octubre de 2012
Problema del día. Combinatoria (28 de octubre)
Se tienen 2009 puntos en el plano. Dos jugadores A y B juegan a trazar líneas entre los puntos por turnos. Empieza A. Gana el primero que completa un ciclo. ¿Cuál de los dos jugadores tiene estrategia ganadora?
Lo vemos como grafos. Si un vertice tiene orden 2, entonces podremos hacer un triangulo. Haciendo un triangulo completamos un ciclo. Entonces para no perder, debes de intentar que todos los vertices tengan orden 0 o 1. Si tu oponente hace que el vertice tenga orden 2, entonces tu completas un triangulo y ya ganas. Entonces suponemos que A y B conocen esta estrategia. Si los 2 la aplican veremos quien es el que pone el primer vertice con orden 2.
2009≡x(mod4) Si x≡0,1(mod4) Entonces A hara que exista el primer vertice con orden 2. 2009≡1(mod4). Entonces A hace el primer vertice con orden 2 y B solo completa el triangulo. Si A hace que algun punto tenga orden 2 antes de que se agoten todos los puntos con orden 0, entonces acelera el proceso de victoria para B siempre y cuando B siga la estrategia ganadora.
Perdon, es x≡1,2(mod4) Esto es porque cada turno le agregas 1 al orden de 2 vertices. Entonces primero A modifica el del 1er y 2do punto. Despues B modifica el del 3er y 4to. En su turno A modifica el del 5to y 6to y asi sucesivamente.
que A va a modificar a los puntos que tengan esa congruencia modulo 4. Cuando hace que un vertice tenga orden 2, podremos hacer un ciclo uniendo los vertices con los que esta conectado haciendo asi un triangulo. Si ambos se apegan a la estrategia, A pondra conectara el punto 2009 con algun otro que ya estaba conectado con otro y ese tendra orden 2. Entonces en su turno, B podra completar un ciclo.
Sabemos que un ciclo es que termina donde empezó sin repetir aristas, entonces la mínima cantidad de vértices para formar un ciclo son 3. Vemos las estrategias para n=0,1,2...9 0∙→GanaB 1∙→GanaB 2∙→GanaA 3∙→GanaA 4∙→GanaB 5∙→GanaB 6∙→GanaA 7∙→GanaA 8∙→GanaB 9∙→GanaB
Para dejar a un jugador en una posición perdedora tenemos que 0 puntos que no se hayan unido antes o 1 punto que no tenga pareja que no se haya unido.
Quien gana n≡0,1mod4⇒GanaB n≡2,3mod4⇒GanaA
Intente demostrar esto por inducción(No estoy segura de que la inducción este bien hecha)
Tenemos i≥0
Base i=0 4(0)<4(0)+1<4(0)+2<4(0)+3 0<1<2<3← sabemos que esto es cierto B,B,A,A
Hipotesis:Cumple para 4k k=i 4(i)<4(i)+1<2(i)+2<2(i)+3 4(i)<4(i)+1<4(i)+2<4(i)+3
P.D Cumple para 4k+4 k=i+1 4(i+1)<4(i+1)+1<4(i+1)+2<4(i+1)+3 4(i)<4(i)+1<4(i)+2<4(i)+3
Al inicio ¿qué es n? ¿la cantidad de vértices?. Si es eso, para n=0,1,2, ¿cómo haces un ciclo? (tu misma pones que lo mínimo son 3). Para n=3,4,...,9 ¿cómo sabes quién tiene estrategia ganadora? No entendí la inducción. ¿Tratas de demostrar que el que gana depende de la congruencia de n módulo 4? ¿Cómo usas las desigualdades para decir quién gana?
Se deben de trazar todas las lineas para poder ganar?
ResponderBorrarNo. Para ganar sólo se tiene que trazar la línea que termine el ciclo, independientemente de quién hace los demás trazos.
BorrarLo vemos como grafos. Si un vertice tiene orden 2, entonces podremos hacer un triangulo. Haciendo un triangulo completamos un ciclo. Entonces para no perder, debes de intentar que todos los vertices tengan orden 0 o 1. Si tu oponente hace que el vertice tenga orden 2, entonces tu completas un triangulo y ya ganas. Entonces suponemos que A y B conocen esta estrategia. Si los 2 la aplican veremos quien es el que pone el primer vertice con orden 2.
ResponderBorrar2009≡x(mod4)
Si x≡0,1(mod4) Entonces A hara que exista el primer vertice con orden 2.
2009≡1(mod4). Entonces A hace el primer vertice con orden 2 y B solo completa el triangulo. Si A hace que algun punto tenga orden 2 antes de que se agoten todos los puntos con orden 0, entonces acelera el proceso de victoria para B siempre y cuando B siga la estrategia ganadora.
¿Por qué si x≡0,1(mod4) A hace que exista el primer vértice con orden 2?
BorrarPerdon, es x≡1,2(mod4) Esto es porque cada turno le agregas 1 al orden de 2 vertices. Entonces primero A modifica el del 1er y 2do punto. Despues B modifica el del 3er y 4to. En su turno A modifica el del 5to y 6to y asi sucesivamente.
Borrar¿Seguro que es x≡1,2(mod4)? ¿Qué tiene que ver que A modifique 1°,2°, 5°,6°,... con que haga que exista el primer vértice de orden 2?
Borrarque A va a modificar a los puntos que tengan esa congruencia modulo 4. Cuando hace que un vertice tenga orden 2, podremos hacer un ciclo uniendo los vertices con los que esta conectado haciendo asi un triangulo. Si ambos se apegan a la estrategia, A pondra conectara el punto 2009 con algun otro que ya estaba conectado con otro y ese tendra orden 2. Entonces en su turno, B podra completar un ciclo.
BorrarSabemos que un ciclo es que termina donde empezó sin repetir aristas, entonces la mínima cantidad de vértices para formar un ciclo son 3. Vemos las estrategias para n=0,1,2...9
ResponderBorrar0∙→GanaB
1∙→GanaB
2∙→GanaA
3∙→GanaA
4∙→GanaB
5∙→GanaB
6∙→GanaA
7∙→GanaA
8∙→GanaB
9∙→GanaB
Para dejar a un jugador en una posición perdedora tenemos que 0 puntos que no se hayan unido antes o 1 punto que no tenga pareja que no se haya unido.
Quien gana
n≡0,1mod4⇒GanaB
n≡2,3mod4⇒GanaA
Intente demostrar esto por inducción(No estoy segura de que la inducción este bien hecha)
Tenemos i≥0
Base i=0
4(0)<4(0)+1<4(0)+2<4(0)+3
0<1<2<3 ← sabemos que esto es cierto
B,B,A,A
Hipotesis:Cumple para 4k
k=i
4(i)<4(i)+1<2(i)+2<2(i)+3
4(i)<4(i)+1<4(i)+2<4(i)+3
P.D Cumple para 4k+4
k=i+1
4(i+1)<4(i+1)+1<4(i+1)+2<4(i+1)+3
4(i)<4(i)+1<4(i)+2<4(i)+3
4k+4≡0mod4⇒GanaB
4k+3≡1mod4⇒GanaB
4k+2≡2mod4⇒GanaA
4k+1≡3mod4⇒GanaA
4k+0≡0mod4⇒GanaB
⇒ 2009≡1mod4∴Btieneestrategiaganadora
Al inicio ¿qué es n? ¿la cantidad de vértices?. Si es eso, para n=0,1,2, ¿cómo haces un ciclo? (tu misma pones que lo mínimo son 3). Para n=3,4,...,9 ¿cómo sabes quién tiene estrategia ganadora?
BorrarNo entendí la inducción. ¿Tratas de demostrar que el que gana depende de la congruencia de n módulo 4? ¿Cómo usas las desigualdades para decir quién gana?