Questões de EFAF Matemática

Mais longa sequência crescente

 

Um problema clássico em computação é denominado mais longa subsequência crescente. Esse problema consiste em, dada uma sequência S de números, encontrar uma subsequência R tal que

 

    • R é obtida removendo alguns elementos de S, sem alterar a ordem dos elementos não removidos.
    • Os números de R estão ordenados do menor para o maior.
    • R tem o maior número de elementos possível.

 

Por exemplo, para a sequência de sete elementos S = {7, 4, 1, 5, 6, 2, 3}, uma possível mais longa subsequência crescente é R = {1, 2, 3}, com três elementos (note que esta não a única possível mais longa subsequência crescente de S).

Para qual das sequências a seguir a maior subsequência máxima tem exatamente dois elementos?

Divisão de chocolate

 

Vô Quico comprou uma barra de chocolate para suas duas netas, Lúcia e Beatriz. A barra é composta de quatro linhas e quatro colunas de quadrados. Em exatamente dois quadrados, que podem estar em qualquer posição na barra, há uma figurinha colada. Vô Quico gostaria de dar dois pedaços de tamanhos iguais, um para cada neta, cada pedaço contendo uma figurinha. Mais precisamente, ele gostaria de dividir a barra bem na metade, com um único corte vertical ou horizontal, deixando uma figurinha em cada pedaço.

A figura acima mostra dois exemplos. A barra da esquerda vô Quico pode dividir na metade com um corte horizontal, e cada metade contém uma figurinha. Mas a barra da direita ele não consegue dividir em dois pedaços iguais, separando as figurinhas, com um único corte horizontal ou vertical.

 

Quantas das seguintes seis barras de chocolate vô Quico consegue dividir em dois pedaços iguais, separando as figurinhas, com um único corte horizontal ou vertical?

O Aladino tem um tapete quadrado como o da figura ao lado. O tapete tem o mesmo número de pontos, dispostos em duas linhas, ao longo de cada lado do tapete. Infelizmente, o tapete dobrou-se.

 

Quantos pontos existem no tapete do Aladino?

O Rodrigo queria que a soma dos três números em cada linha e em cada coluna da tabela ao lado fosse a mesma. O Rodrigo cometeu um erro.

 

Que número deve o Rodrigo corrigir?

As idades dos membros de uma família de cangurus são 2, 4, 5, 6, 8 e 10 anos. A soma das idades de quatro dos cangurus é 22 anos.

 

Quais são as idades dos outros dois cangurus?

Os cinco carros seguintes, numerados com 1, 2, 3, 4 e 5, estão a mover-se na mesma direção.

Primeiro, o último carro (numerado com 5) ultrapassa os dois carros à sua frente. Em seguida, o penúltimo carro ultrapassa os dois carros à sua frente. Finalmente, o carro do meio ultrapassa os dois carros à sua frente.

 

Por que ordem ficam os carros no final?