questão de análise combinatória

rebecaszz escreveu:Seja S um subconjunto de {1,2,3,...,1989} de modo que não há dois membros de S que diferem de 4 ou 7. Qual a máxima quantidade de números que S pode ter?

Tem o gabarito?

Algo perto de 722?

JaquesFranco escreveu:

rebecaszz escreveu:Seja S um subconjunto de {1,2,3,...,1989} de modo que não há dois membros de S que diferem de 4 ou 7. Qual a máxima quantidade de números que S pode ter?

Tem o gabarito?

Algo perto de 722?

905 o gabarito, desculpa n ter postado antes

rebecaszz

Pela Regra XI: a postagem do gabarito, se souber, é obrigatória.
Por favor leia/siga sempre, todas as Regras, para não correr o risco de ter suas postagens bloqueadas.

Eu não sei se tem uma maneira mais fácil de proceder, mas a questão pode ser feita assim.

Considere o conjunto A ={1,2,3,...,11}. O maior número de elementos que um subconjunto B de A pode ter de forma que a diferença entre dois de seus elementos não  é 4 nem 7 é 5.

Pra ver isso basicamente eu analisei todos os casos possíveis. Repare que pra cada elemento em B, existem exatamente 2 elementos que nao podem estar em B. Por exemplo, se 1∈B, então nem 5 nem 8 estão em B. Daí a ideia é supor que 1 ∈ B (isso sempre pode ser feito) e reparar que nos 4 proximos elementos vamos adicionar mais 4 novas restrições. Isso implica que teremos 5 elementos em B e 6 que não poderão estar. Mas sao mtos casos, então nao vou escrever aqui. Espero que esteja correto.

Bom, mas assumindo essas coisas, como 181.11 = 1991 consideramos os conjuntos:

\( A_k = \{ 11k - 10, 11k- 9, ..., 11k\} = ]11(k-1), 11k] \cap \mathbb N \)

Ou seja,
A₁ = {1,2,3,4...,11},
A₂ = {12,13,..., 22},
...
A₁₈₁ = {1981, 1982, ..., 1991}

Se S é um subconjunto de {1,2,..., 1989} satisfazendo as condições do enunciado, então cada B_k = A_k Ո S também satisfaz. Pelo que vimos acima, cada B_k tem no maximo 5 elementos. Daí S tem no máximo 181.5 = 905 elementos. Pra ver que esse maximo de fato pode ser atingido, basta exibir um exemplo onde S tem 905 elementos. Isso pode ser feito da seguinte forma:

O X X O X O O X O X X

O diagrama acima representa os números que estão em cada B. O símbolo O indica que "está" e X indica que "não está". Por exemplo,
B₁ = {1,4,6,7,9}
B₂ = {12, 15, 17, 18, 20}
etc

Em outras palavras, S = { conjunto dos números que deixam resto 1,4,6,7 ou 9 na divisão por 11}. Assim, S tem 905 elementos e satisfaz as condições pedidas.

DaoSeek escreveu:Eu não sei se tem uma maneira mais fácil de proceder, mas a questão pode ser feita assim.

Considere o conjunto A ={1,2,3,...,11}. O maior número de elementos que um subconjunto B de A pode ter de forma que a diferença entre dois de seus elementos não  é 4 nem 7 é 5.

Pra ver isso basicamente eu analisei todos os casos possíveis. Repare que pra cada elemento em B, existem exatamente 2 elementos que nao podem estar em B. Por exemplo, se 1∈B, então nem 5 nem 8 estão em B. Daí a ideia é supor que 1 ∈ B (isso sempre pode ser feito) e reparar que nos 4 proximos elementos vamos adicionar mais 4 novas restrições. Isso implica que teremos 5 elementos em B e 6 que não poderão estar. Mas sao mtos casos, então nao vou escrever aqui. Espero que esteja correto.

Bom, mas assumindo essas coisas, como 181.11 = 1991 consideramos os conjuntos:

\( A_k = \{ 11k - 10, 11k- 9, ..., 11k\} = ]11(k-1), 11k] \cap \mathbb N \)

Ou seja,
A₁ = {1,2,3,4...,11},
A₂ = {12,13,..., 22},
...
A₁₈₁ = {1981, 1982, ..., 1991}

Se S é um subconjunto de {1,2,..., 1989} satisfazendo as condições do enunciado, então cada B_k = A_k Ո S também satisfaz. Pelo que vimos acima, cada B_k tem no maximo 5 elementos. Daí S tem no máximo 181.5 = 905 elementos. Pra ver que esse maximo de fato pode ser atingido, basta exibir um exemplo onde S tem 905 elementos. Isso pode ser feito da seguinte forma:

O X X O X O O X O X X

O diagrama acima representa os números que estão em cada B. O símbolo O indica que "está" e X indica que "não está". Por exemplo,
B₁ = {1,4,6,7,9}
B₂ = {12, 15, 17, 18, 20}
etc

Em outras palavras, S = { conjunto dos números que deixam resto 1,4,6,7 ou 9 na divisão por 11}. Assim, S tem 905 elementos e satisfaz as condições pedidas.

muito obrigada, eu não tinha conseguido de jeito nenhum resolver <33

rebecaszz escreveu:muito obrigada, eu não tinha conseguido de jeito nenhum resolver <33

Pois é, mas sendo sincero, eu nao gostei muito não da solução. Na verdade, eu resolvi uns dois dias atrás mas nao postei porque estava tentando melhorar, mas não consegui. Basicamente eu tentei descobrir um caso onde o maximo é atingido e depois verificar que é de fato o máximo. Repare que podemos descrever um subconjunto de {1,2,3,...,1989} que contem o número 1 como uma sequencia de números, onde cada número denota a diferença entre o termo anterior e o posterior. Por exemplo:
3,2,4,5,7,3,4
Denota o seguinte conjunto:
{1,4,6,10,15,22,25,29}
Pois:
1 --> primeiro elemento
4   = 1   + 3
6   = 4   + 2
10 = 6   + 4
15 = 10 + 5
22 = 15 + 7
25 = 22 + 3
29 = 25 + 4

Assim, o que a gente quer é uma sequencia de números que nao possua termos consecutivos somando nem 4 nem 7. De preferencia periodica. Pensando assim encontrei a sequencia
3,2,1,2,3, 3,2,1,2,3, 3,2,1,2,3...
sempre repetindo o trecho 3,2,1,2,3,  que corresponde ao conjunto S com 905 elementos. O fato de ser periodico, torna possivel analisar cada periodo pra provar que é de fato a situação maxima. Mas mesmo assim, parece uma solução muito ruim. Se vc encontrar uma maneira melhor por favor coloque aí