Combinações perfeitas em um tabuleiro de xadrez?

14

Considere o problema de encontrar o número máximo de cavaleiros que podem ser colocados em um tabuleiro de xadrez sem que dois deles se atacem. A resposta é 32: não é muito difícil encontrar uma combinação perfeita (o gráfico induzido pelos movimentos dos cavaleiros é bipartido e há uma combinação perfeita para uma prancha 4 × 4), o que obviamente é uma cobertura mínima da borda. Também não é difícil provar que a resposta é para um tabuleiro de xadrez sempre que : basta mostrar combinações para e faça um pouco de footwork de indução.m×nm,n33m,n6mn2m×nm,n33m,n6

Por outro lado, se o tabuleiro de xadrez fosse toroidal e fosse par, a prova nem exigiria a exibição de uma correspondência para tabuleiros pequenos: o mapa tem apenas ciclos de comprimento uniforme; portanto, deve haver uma correspondência perfeita.( x , y ) ( x + 1 , y + 2 )m,n(x,y)(x+1,y+2)

Existe algum equivalente para tabuleiros de xadrez retangulares , ou seja, existe uma maneira mais simples de mostrar que, para suficientemente grande sempre existe uma correspondência perfeita do tabuleiro de xadrez? Para placas grandes, a placa retangular e a placa toroidal são quase equivalentes no sentido de que a fração de arestas ausentes chega a zero, mas não conheço nenhum resultado teórico que garanta uma correspondência perfeita nesse caso.m,n

E se, em vez de pular em qualquer direção, um cavaleiro pular quadrados em qualquer direção? Ou, nesse caso, quadrados, com ímpar coprime? Se não é uma simples forma de provar que a resposta é para suficientemente grande (por exemplo, m, n \ GEQ C (p, q) ), como é C (p, q) ?( 2 , 3 ) ( p , q ) p + q p , q(1,2)(2,3)(p,q)p+qp,qmn2m,nm,nC(p,q)C(p,q)

ctgPi
fonte
Essa é uma boa pergunta.
Suresh Venkat
Suponho que a excursão de um cavaleiro seja suficiente. Aparentemente, as excursões fechadas sempre existem quando m,n>8 e mn são pares.
Timothy Sun

Respostas:

9

A resposta é NÃO para todos os grandes se, por exemplo, e . Por quê? Observe que, devido aos restantes agora o gráfico é a união disjunta (vértice) de três gráficos bipartidos e de cada um podemos selecionar a metade maior. Por exemplo, se , então podemos colocar (pelo menos) 5002 cavaleiros. (Isso ocorre porque tem seis classes que estão em três pares, as diferenças entre as cardinalidades dos pares são .)mn2m,np=6q=3mod3m=n=100x+ymod61,1,2

Eu não sei o que acontece se adicionarmos a condição de que e são primos relativos. (Observe que, além do divisor 2, isso é equivalente a e são primos relativos, na verdade, essa é a condição de que precisamos e que também mostra que sendo ímpar é necessário.)pqp+qp-qp+q

domotorp
fonte
Oh, bom argumento; Alterei a pergunta para refletir sua observação.
ctgPi