22/02/2020, 00:44:16 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Tablero de Ajedrez  (Leído 106 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Julio_fmat
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 2.083



Ver Perfil WWW
« : 06/12/2019, 00:03:24 »

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

"Haz de las Matemáticas tu pasión".
Abdulai
Moderador Global
Pleno*
*

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.297


Ver Perfil
« Respuesta #1 : 06/12/2019, 01:38:01 »


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.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.007


Ver Perfil
« Respuesta #2 : 09/12/2019, 17:44:41 »

Hola

Demuestre que si removemos dos esquinas opuestas en un tablero de ajedrez de [texx]8\times 8[/texx] obtenemos un subtablero que no puede ser cubierto por fichas rectangulares de tamaño [texx]2\times 1[/texx] y [texx]1\times 2.[/texx] ¿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 [texx]30[/texx] vértices en un conjunto de la partición y [texx]32[/texx] en el otro, luego no puede existir un "perfect matching".

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!