Autor Tema: Colocar números en un tablero

0 Usuarios y 1 Visitante están viendo este tema.

24 Febrero, 2014, 03:11 am
Leído 2699 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas, buenas!

Tengo el siguiente problema:

Ponga los enteros \( 1, 2, 3,..., n^2 \) (sin repetición) en cualquier orden sobre una tablero de ajedrez de \( n\times n \), con uno en cada cuadrado. Demuestre que existen dos entradas adyacentes cuya diferencias es al menos \( n+1 \).

este problema lo he atacado para los casos \( n=2, 3, 4 \) en el adjunto problema cuatro. Sin embargo no logro ver una generalización inteligente que me lleve a muchas subcasos y el caso general así como propongo en esos casos tiene una hipótesis fuerte que se explica ahí.

También en el problema dos del mismo adjunto se soluciona con cálculo vectorial el problema que mencioné en

http://rinconmatematico.com/foros/index.php?topic=73029.0

sin embargo, creo que no es la manera más lista o efectiva. Esa era la razón de mi pregunta.

Agradecería cualquier consejo.

¡Gracias!
 
PD: El trabajo no está terminado, pero sí organizadito. :P
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

24 Febrero, 2014, 11:51 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Entiendo que por adyacente se incluye también en diagonal.

 En ese caso ten en cuenta que en un tablero \( n\times n \) se puede ir de una casilla cualquiera a otra en a lo sumo \( n-1 \) movimientos entre casillas ayacentes.

 Analiza que ocurre si tratamos de ir desde la casilla donde está el \( 1 \) hasta \( n^2 \).

Saludos.

26 Febrero, 2014, 06:18 am
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Digamos que me siento cerca, pero sin saber a dónde ir:

Denotemos \( 1\equiv{(i,j)} \) y \( n^2\equiv{(i',j')} \) las posiciones de \( 1 \) y \( n^2 \)

Primer caso: \( i=i' \), \( j<j' \)
Iremos hacia \( n^2 \) del modo siguiente

\( 1, n+1, 2n+1, ..., (j-j'-1)n+1 \)

sobre la fila en que ambos están. Esto es ir de modo que la diferencia entre cada par de consecutivos es \( n \) que es la máxima diferencia posible. El elemento \( (j'-j-1)n+1 \) cumple que

\( n(j'-j+n)\geq 2 \)

\( n^2- [(j'-j-1)n+1] \geq n+1 \)

que es la diferencia buscada.

Segundo caso: \( i'=j, j'=i, i<j \)
 
Existe \( r \) tal que \( (i+r, j-r)=(i',j') \) haciendo lo  mismo que en el primer caso pero en diagonal encontramos que el elemento
\( (r-1)n+1 \) cumple que

\( n(n-r)\geq 2 \)
\( n^2-((r-1)n+1)\geq n+1 \)

que de nuevo es la diferencia buscado.

Tercer caso \( i>i', i-i> j'-j \)

es analogo a los otros dos, pero este teclado ya no me obedece... Parece que estos razonamientos pueden convertirse en una demostracion legitima, porque estoy escogiendo en la secuencia el maximo numero para el que no se cumple el teorema.

Que pena la falta de tildes y no subir bien mas. Misero teclado


Muchas gracias por la paciencia  ;D

Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

26 Febrero, 2014, 12:46 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Te estás complicando o queriendo ser más papista que el papa.

 1) En primer lugar yo considero como una afirmación obvia que se puede llegar de una casilla a otra con a lo sumo \( n-1  \) movimientos entre casillas adyacentes.

 2) Teniendo en cuenta (1) basta razonar por reducción al absurdo. Supongamos que no hay ningún par de entradas adyacentes cuya diferencia es al menos \( n+1 \). Es decir supongamos que todas las entradas adyacentes tienen una diferencia menor que \( n+1 \).

 Ahora si consideramos las casillas (que denoto respectivamente como \( c_1 \) y \( c_{s+1} \)) donde se encuentran el \( 1 \) y \( n^2 \) por (1) existe una cadena de \( s\leq n-1 \) movimientos entre casillas adyacentes que los conectan:

\( 1=c_1\to c_2\to c_3\to \ldots \to c_{s+1}=n^2 \)

 Entonces por hipótesis:

\(  |c_i-c_{i+1}|<n+1 \) y en particular \( c_i>c_{i+1}-(n+1) \)

 Por tanto:

\(  1=c_1>c_2-(n+1)>c_3-2(n+1)>\ldots>c_{s+1}-s(n+1)=n^2-s(n+1)\geq n^2-(n-1)(n+1)=1 \)

 ¡Contradicción!.

Saludos.

P.D. Si (1) no te parece obvio tampoco es difícil de probar, si quieres hacerlo y no te sale dilo.

26 Febrero, 2014, 04:17 pm
Respuesta #4

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Yo lo solucioné como aparece en el siguiente adjunto. ¡Gracias por la ayuda!  ;D

¡Cuarto problema!
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

26 Febrero, 2014, 08:18 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Tu demostración me resulta confusa; no me queda claro como en tu cadena de desigualdades no llegas directamente a \( n^2 \), sino a un elemento \( m_{j'-j-1} \) que no sé muy bien con que criterio está elegido.

Saludos.

26 Febrero, 2014, 09:25 pm
Respuesta #6

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Aaah...  :(

Hay un problema entre las desiguldades. Tendré que repensar ese chapotero o quedarme con tu solución.  ;D

¡Gracias!

Sin embargo la solución intuitivamente me parece correcta... pero puede ser complicado escribirla. Le estaré contando.
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

27 Febrero, 2014, 04:38 am
Respuesta #7

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Supongamos que tenemos un tablero de \( n\times n \). Supongamos que en \( (i,j) \) está \( 1 \) y en \( (i',j') \) está \( n^2 \). Además, coloquemos las condiciones \( 0<i'-i\leq j'-j \) los demás casos funcionarán de manera análoga. El número mínimo de casillas entre \( 1 \) y \( n^2 \) es \( j'-j \). Si \( 1 \) es adyacente a algún número tal que la diferencia entre ambos es al menos \( n+1 \) hemos terminado. Si no cada \( x \) adyacente a \( 1 \) cumple la desigualdad \( x\leq n+1 \) llamemos \( m_1 \) al \( x \) cuyo mínimo de casillas entre \( m_1 \) y \( n^2 \) es \( j'-j-1 \). Si \( m_1 \) es adyacente a un número tal que la diferencia entre ambos es al menos \( n+1 \) hemos terminado. Si no cada \( x \) adyacente a \( m_1 \) cumple la desigualdad \( x\leq 2n+1 \)  pero no recíprocamente. Elijamos como \( m_2 \) al \( x \) que cumple la desigualdad anterior y cuyo mínimo número de casillas entre \( m_2 \) y \( n^2 \) es \( j'-j-2 \). Continuamos con este proceso: si \( m_i \) tiene adyacente algún número con el que diste al menos \( n+1 \) hemos terminado sino cada \( x \) adyacente a \( m_r \) cumplirá la desigualdad \( x\leq (r+1)n+1 \) y llamamos \( m_{r+1} \) al elemento que cuyo mínimo número de casillas con \( n^2 \) es \( j'-j-i \). Este proceso sólo puede continuar hasta \( j'-j-1 \) cuyo elemento \( m_{j'-j-1} \) cumple la desigualdad \( m_{j'-j-1}\leq (j'-j-1)n+1 \) y es adyacente a \( n^2 \). Luego con esta desigualdad
\( n+1 \leq n^2-[(j'-j-1)n+1]\leq n^2-m_{j'-j-1} \)
con lo que si todos los casos anteriores no tienen adyacentes con los que disten \( n+1 \) este ha de tenerlo.

Creo que así está bien, aunque cualquier regaño no será mal recibido o un consejo de redacción o hasta pedagógico  ;D

PD:
Te estás complicando o queriendo ser más papista que el papa.
Esto no lo entendí.
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

27 Febrero, 2014, 11:09 pm
Respuesta #8

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Me siento como un desquiciado  :P ¿no me hago entender?
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

27 Febrero, 2014, 11:19 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Me siento como un desquiciado  :P ¿no me hago entender?

Me tengo que ir a dormir y no puedo extenderme ahora.

Lo que quiero decir con que "estás siendo más papista que el papa" es que estás deteniéndote en formalizar con índices y una notación algo farragosa una idea que es muy sencilla y que yo creo que se puede aceptar sin más sin necesidades de pararse en los detalles formales.

 Incluso como la escribí yo, tiene ya un exceso de notación.

 Podría escribirse una solución mucho clara y convincente prácticamente sólo con texto, sin apenas fórmulas, pero ahora...

 .... ¡buenas noches!.

Saludos.