Un (n,k)-torneo es un concurso con n participantes hecho en k rondas tal que:
i) Cada participante juega en cada ronda y cada 2 participantes jugaron a lo más una vez;
ii) Si el jugador A se enfrenta a B en la ronda i, C se enfrenta a D en la ronda i, y A se enfrenta a C en la ronda j, entonces B se enfrenta a D en la ronda j.
Determinar todos los pares (n,k) tales que existe un (n,k)-torneo.
Sea ABCD un cuadrilátero cíclico. Sean E y F puntos variables en los lados AB y CD, respectivamente, tales que AE/EB=CF/FD. Sea P el punto en el segmento EF tal que PE/PF=AB/CD. Probar que la razón de las áreas de los triángulos APD y BPC no depende de la elección de E y F.
Suscribirse a:
Comentarios de la entrada (Atom)
6 comentarios:
La respuesta es:
Las parejas $(n,k)$ que cumplen que si $2^a \le k$ es la mayor potencia de $2$ menor o igual a $k$, entonces $2^{a+1} | n$.
Demostración: Tenemos una gráfica de $n$ vértices donde las aristas son coloreadas de $k$ colores, y de cada vértice sale una arista de cada color, tal que si $AB$ es de color $i$ y $CD$ es de color $i$ y $AC$ es de color $j$ entonces $AD$ es de color $j$.
Sea $P(n,k)$ la proposición que dice que existe una gráfica así con $n$ vértices y $k$ colores.
Primero, muestro que $P(n,k) \Rightarrow P(n,k-1)$. Ésto es fácil, en mi torneo simplemente elimino las aristas de color $k$.
Ahora muestro que $P(n,2^a) \Rightarrow 2^{a+1} | n$. Para ver ésto, vemos que el color $1$ "empareja" a los vértices. Ahora, si dos vértices están unidos por el color $2$, entonces sus parejas respectivas también están unidas por el color $2$. Entonces el color $2$ empareja a las parejas, creando cuartetas. Similarmente, el color $3$ empareja cuartetas, el color $4$ empareja octetas, etcétera. De aquí es fácil concluir.
Ahora, muestro $P(2^a, 2^a-1)$ para $a \ge 1$. Lo hago inductivamente. Para $a=1$ es obvio. Ahora, supongamos que tengo mi acomodo para $a$ y crearé uno para $a+1$.
Supongamos que, en mi acomodo para $a$, numero los vértices del $1$ al $2^a$. Mis colores son color $1$, color $2$, ..., color $2^a-1$. Sea $f(x,y)=0$ si no hay arista entre los vértices número $x$ y $y$, y de lo contrario sea $f(x,y)$ el valor del color de la arista $xy$. Notemos que $f(x,y)=f(y,x)$.
El siguiente será mi acomodo para $a+1$. Mis vértices serán vértice $1$, ..., vértice $2^a$, vértice $1_p=1+2^a$, ..., vértice $2^a_p=2^a+2^a$.
Defino una función $g : \{1,...,2^{a+1} \} \times \{1,...,2^{a+1} \} \rightarrow \{0,1,...,2^{a+1}-1\}$.
$g$ cumplirá que $g(x,y)=g(y,x)$:
Sea $g(x,y)=f(x,y)$ si $x,y < 2^a+1$.
Sea $g(x,x+2^a) = 2^{a+1}-1$.
Sea $g(x,y)=f(x,y-2^a)+2^a-1$ si $x<2^a+1$ y $y \ge 2^a+1$.
Si dibujo una gráfica con esos vértices y tal que $g(x,y)=0$ si no hay arista entre $x,y$ y que si $g(x,y) \neq 0$ entonces la arista $xy$ será del color $g(x,y)$, es fácil ver que la gráfica funcionará. Entonces he completado mi inducción.
Ahora...
Tengo tres propiedades de $P$:
(1) $P(n,k) \Rightarrow P(n,k-1)$
(2) $P(2^a, 2^a-1)$
(3) $P(n, 2^a) \Rightarrow 2^{a+1} | n$
Con éstas tres propiedades vemos que mi respuesta inicial es la correcta.
Mi demostración es esencialmente igual a la de Juan. Solo hago la observación que para $P(2^a,2^a-1)$, mi ejemplo es diferente (o al menos más claro).
Basicamente, mis colores serán del $1$ al $2^a-1$. Sea x la función XOR binaria, entonces la pareja $(R,RxK)$ estara del color $K$. Esto funciona porque $RxKxK=R$ y $RxAxB=RxBxA$.
De hecho, otra forma de ver el problema, es ver la grafica como un grupo $G$, un elemento por vertice, tal que haya $k$ elementos $a_1,...,a_k$ tal que $a_ia_i=e$ y sea conmutativa. Como caminar de un vertice a otro por un color es aplicar por derecha ese elemento. XOR binario cumple esto, por lo que cumple el problema.
En mi ejemplo, lo que hago es agarrar la gráfica para $a$ y la dibujo en una hoja de papel, y copio esa hoja de papel. Ahora tengo dos hojas idénticas. Pongo una arriba de otra.
Uno los vértices homólogos con el color $2^{a+1}-1$, y si dos vértices $V$ y $W$ están unidos con el color $C$ en las hojas, entonces uno a $V$ con el complemento de $W$ con el color $C_p$ y uno a $W$ con el complemento de $V$ con el color $C_p$.
Quizá así se entienda mejor
Luis, tienes excelente gusto :) Aquí va mi solución del 2
Sea $BC \cap CD = Q$, y sea $l$ la bisectriz de $\angle BQA$. Sea $EF \cap l = P_1$.
Como, por potencia desde $Q$ y porque $BE/EA=DF/FC$,
$\frac{sen CQF}{sen FQD} = \frac{CF * QD}{CQ*FD} =$$ \frac{AE*BQ}{EB*AQ} = \frac{sen AQE}{sen EQB}$
entonces $l$ biseca a $\angle FQE$. Nótese que $QF/QE=AB/CD$ porque en los triángulos semejantes $BQA$ y $CDQ$, las cevianas $QE$ y $QF$ son homólogas. Entonces por Teo. Bisectriz
$\frac{EP_1}{P_1F} = \frac{QE}{QF} = \frac{AB}{CD}=\frac{EP}{PF}$
entonces $P = P_1$ y así $P \in l$.
Entonces si $h_{AD}$ es la distancia de $P$ a la línea $AD$ y defino $h_{BC}$ análogamente, veo que
$\frac{h_{AD}}{h_{BC}}$
es constante. Como
$\frac{(ADP)}{(BPC)} = \frac{h_{AD}}{h_{BC}} \times \frac{AD}{BC}$
vemos que esa fracción es constante, entonces he acabado.
Publicar un comentario