Autor Tema: Tablero de Ajedrez

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

06 Diciembre, 2019, 04:03 am
Leído 933 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre que si removemos dos esquinas opuestas en un tablero de ajedrez de \( 8\times 8 \) obtenemos un subtablero que no puede ser cubierto por fichas rectangulares de tamaño \( 2\times 1 \) y \( 1\times 2. \) ¿Podria extender el argumento para hacer una afirmacion que aplique a todos los grafos bipartitos?
"Haz de las Matemáticas tu pasión".

06 Diciembre, 2019, 05:38 am
Respuesta #1

Abdulai

  • Moderador Global
  • Mensajes: 2,387
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

Con grafos no se me ocurre nada, pero como ese subtablero tiene 30 cuadros blancos y 32 negros (o al revés) jamás podremos cubrirlo con fichas de 2x1 , pues tapan la misma cantidad de blancos que negros.

09 Diciembre, 2019, 09:44 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Demuestre que si removemos dos esquinas opuestas en un tablero de ajedrez de \( 8\times 8 \) obtenemos un subtablero que no puede ser cubierto por fichas rectangulares de tamaño \( 2\times 1 \) y \( 1\times 2. \) ¿Podria extender el argumento para hacer una afirmacion que aplique a todos los grafos bipartitos?

El problema se puede ver como un grafo bipartito donde los vértices son las casillas repartidas en blancas y negras (esa es la partición del grafo bipartito).

Las aristas son las fichas descritas que unen siempre vértices (casillas) blancos con negros.

El problema de cubrir el tablero con tales fichas es el problema de encontrar un "perfect matching" es decir una colección de aristas disjuntas (sin vértices en común) que cubran todos los vértices.

Pues bien en un grafo bipartito para que pueda existir un "perfect mathcing" los dos subconjuntos de vértices de la partición deben de tener el mismo número de elementos, ya que cada arista une un vértice de cada conjunto.

El argumento de Abdulai: si retiramos las casillas de los extremos, como son del mismo color, el grafo bipartito tiene \( 30 \) vértices en un conjunto de la partición y \( 32 \) en el otro, luego no puede existir un "perfect matching".

Saludos.