segunda-feira, 13 de junho de 2016

Xadrez - 64 Torres


Um problema do Torneio Internacional de Matemática das Cidades, 2005:
Preencha um tabuleiro de xadrez com 64 Torres, uma em cada casa. Você pode remover uma Torre por vez, desde que ela no momento ataque um número ímpar de Torres. Qual é o número máximo de Torres que podem ser removidas nesse processo?
(Uma Torre ataca outra Torre se elas estiverem na mesma linha ou na mesma coluna, e se não houver nenhuma outra peça entre elas.)

A problem from the International Mathematics Tournament of the Towns, 2005:
Fill a chessboard with 64 Rooks, one on each square. You are allowed to remove one Rook at a time, only if it currently attacks an odd number of Rooks. What is the maximum number of Rooks that can be removed in this process?
(A Rook attacks another Rook if they are on the same row or on the same column, and if there are no other pieces between them.)

PCFilho

10 comentários:

  1. Este comentário foi removido pelo autor.

    ResponderExcluir
    Respostas
    1. Este comentário foi removido pelo autor.

      Excluir
  2. Hint: in the beginning of the process, a Rook in one of the 4 corners cannot be removed, as it attacks 2 other Rooks. And it will continue to attack 2 other Rooks, unless you remove all the other Rooks from the same row, or from the same column. But that would include removing another "corner Rook".

    What can we conclude from this?

    ResponderExcluir
    Respostas
    1. Este comentário foi removido pelo autor.

      Excluir
  3. The maximum possible number of rook removals is fifty-nine (59).

    Here's the procedure for accomplishing this:

    First, you choose a row and column that aren't edges, then you remove, one by one, starting with the edges, all of the rooks other than the corner rooks that are not in that row or that column.

    Now, one by one, starting the outermost rooks, remove the rooks in that row and column, leaving the one located where that row and column intersect.

    Now you've got only five rooks left and you can't remove any more.

    ResponderExcluir
    Respostas
    1. Well done, Jake. We can remove 59 Rooks at most. Five Rooks must stay on the board: 4 in the corners, and 1 somewhere else.

      Excluir
  4. As I wrote above, in the beginning of the process, a Rook in one of the 4 corners cannot be removed, as it attacks 2 other Rooks. And it will continue to attack 2 other Rooks, unless we remove all the other Rooks from the same row, or from the same column. But that would include removing another "corner Rook".

    From that, we conclude that the 4 Rooks in the corners of the chessboard will never be removed, as each one of them will always attack 2 other Rooks, no matter how many Rooks we remove. For a corner rook to attack only one Rook, another corner Rook would have to be removed, which is impossible in the first place.

    Next, I note that we cannot leave behind only the four Rooks in the corners, because the last Rook we remove from the chessboard would either attack no Rook (if it is on one of the 36 central squares) or two corner Rooks (if it is on one of the 24 border squares). Either way, it is an even number of Rooks.

    Now, I just need to find a step-by-step solution in which 59 Rooks are removed. There are many possible ways to do this. I did it this way (the numbers denote the order in which the Rooks were removed):
    ** 01 02 03 04 05 06 **
    13 50 51 52 53 54 55 07
    14 15 16 17 18 19 56 08
    20 21 22 23 24 25 57 09
    26 27 28 29 30 31 58 10
    32 33 34 35 36 37 59 11
    38 39 40 41 42 43 !! 12
    ** 44 45 46 47 48 49 **

    The "!!" is the Rook that remains, together with the corner Rooks, marked as "**". :)

    ResponderExcluir
  5. Hi, Gents.

    It reminded me a book I had 30 and so years ago called "Ajedrez y las Matematicas - las relaciones matematicas en el ajedrez", too complex for my understanding, I must confess.

    Fluzão 2x0 Mulambos Paulistas

    ResponderExcluir
    Respostas
    1. Mauro,

      I would love to take a look at this book. Chess and math are two passions of my life.

      Fluzão 1 x 0, it was enough. :)

      Excluir

Regras para postar comentários:

I. Os comentários devem se ater ao assunto do post, preferencialmente. Pense duas vezes antes de publicar um comentário fora do contexto.

II. Os comentários devem ser relevantes, isto é, devem acrescentar informação útil ao post ou ao debate em questão.

III. Os comentários devem ser sempre respeitosos. É terminantemente proibido debochar, ofender, insultar e/ou caluniar quaisquer pessoas e instituições.

IV. Os nomes dos clubes devem ser escritos sempre da maneira correta. Não serão tolerados apelidos pejorativos para as instituições, sejam quais forem.

V. Não é permitido pedir ou publicar números de telefone/Whatsapp, e-mails, redes sociais, etc.

VI. Respeitem a nossa bela Língua Portuguesa, e evitem escrever em CAIXA ALTA.

Os comentários que não respeitem as regras acima poderão ser excluídos ou não, a critério dos moderadores do blog.