POSCOMP 2007, Questão 18, Matemática

18. [MT] Um professor de programação passa um trabalho e avisa à turma que vai utilizar um verificador automático para detectar trabalhos copiados. Os alunos descobrem que o verificador não é capaz de identificar a cópia se as linhas do programa não aparecem na mesma ordem. Além disso, eles também descobrem que uma rotina do trabalho de um de seus colegas continua funcionando corretamente se as linhas são trocadas de ordem, mas nenhuma linha aparece à distância maior do que 1 de sua posição original. Indique o número de alunos que podem entregar uma cópia do trabalho quando n = 7 (incluindo o próprio autor do trabalho).
a) 32
b) 21
c) 14
d) 128
e) 64


Resolução:

trabalho_original

Seja a seguinte notação, quando o trabalho não trocou nenhuma linha escrevemos IIIIIII. Quando o trabalho tem a sexta linha trocada com a sétima escrevemos IIIIIX.

trabalho_mudado

É como se trocássemos os II por um X. Assim temos as seguintes sequências, a sem nenhum X:

  1. IIIIIII

Então os com somente um X.

  1. IIIIIX
  2. IIIIXI
  3. IIIXII
  4. IIXIII
  5. IXIIII
  6. XIIIII

Os com dois X:

  1. IIIXX
  2. IIXIX
  3. IXIIX
  4. XIIIX
  5. IIXXI
  6. IXIXI
  7. XIIXI
  8. IXXII
  9. XIXII
  10. XXIII

E os com três X:

  1. IXXX
  2. XXXI
  3. XXIX
  4. XIXX

Como não podemos usar mais que três X, então temos o número de combinação foi de 21, alternativa B.

4 thoughts on “POSCOMP 2007, Questão 18, Matemática

  1. Encontrei uma solução realmente bonita para o problema:

    Note:
    Seja t(n) o número de soluções (trocas) possíveis para um programa de n linhas.
    A situação pode ser simplificada, sem perda de generalidade, se pensarmos: trocar ou não a primeira linha com a segunda.

    Então t(n) é a soma do total quando se troca a primeira linha com a segunda MAIS o total de quando se mantém a primeira linha na posição original

    Quando se troca as duas primeiras linhas o total passa a ser t(n – 2) (duas linhas a menos pra trocar), e quando se mantém a primeira linha, o total é t(n-1) (uma linha a menos pra trocar)

    Então t(n) = t(n-1) + t(n-2)

    Série de fibonacci!

    Avaliando-se para n = 7
    1
    2
    3
    5
    8
    13
    21

    E mais uma vez consegui fugir de um problema de combinatória :)

    A tua solução é interessante, mas imprática pra n muito grande já que o número de combinações vai crescer exponencialmente com n.

  2. Mais do que isso! Acabei de encontrar uma uma redução direta desse problema a um outro bem semelhante: Como escrever um inteiro não negativo n como uma soma de um’s e dois’s?

    http://books.google.com/books?id=jKY7Ta9LdLgC&pg=PA50&lpg=PA50&dq=fibonacci+and+combinatorics&source=bl&ots=tPH3ZF5oEq&sig=nN87WNqfBhIp_LVpvWI2SjwEIQ0&hl=en&ei=xU-YSqKBNuSK8QbV3LG3BQ&sa=X&oi=book_result&ct=result&resnum=4#v=onepage&q=fibonacci and combinatorics&f=false

  3. Tem um problema parecido, que era um robô que só tem duas instruções, ir um metro pra frente ou dois metros pra trás. Daí a pergunta era quantas maneiras ele podia andar um certa distância de n metros.

Leave a Reply

Your email address will not be published. Required fields are marked *