Operação com conjuntos (combinatória)
2 participantes
Página 1 de 1
Operação com conjuntos (combinatória)
Surpreendentemente, esse problema apareceu numa questão de cálculo, postada aqui no fórum pela usuária Giovana Martins. Segue o enunciado.
Para a questão, considere que os conjuntos podem ter elementos repetidos. Por exemplo, {1,2,3,3,3,4,4} é um "conjunto" válido.
Considere um conjunto A finito de números reais não negativos. Se A possui 2 ou mais elementos, então Giovana pode realizar a seguinte operação:
1° Passo: Escolher 2 elementos x,y do conjunto A
2° Passo: Criar dois novos conjuntos. Os elementos do primeiro conjunto serão todos os elementos de A, exceto x e y, acrescidos de x+y. Os elementos do segundo conjunto serão todos os elementos de A, exceto x e y, acrescidos de |x-y|.
3º Passo: Apagar o conjunto A.
Por exemplo, caso seja A = {1,2,3,4,5}, escolhendo x = 4 e y = 5, os dois novos conjuntos serão: {1,2,3,9} e {1,2,3,1}
Digamos que Giovana realiza essa operação sucessivamente com os conjuntos que tem a disposição até não ser mais possível.
a) Mostre que se A tem m elementos, então Giovana pode realizar no máximo \(2^{m-1}-1\) operações. Após isso haverão \(2^{m}\) conjuntos com 1 elemento.
b) Mostre que os conjuntos finais obtidos não dependem da ordem de realização das operações.
c) Mostre que se m deixa resto 0 ou 3 na divisão por 4, e A = {1,2,3,...,m} então um dos conjuntos finais é {0}
d) Mostre que se m deixa resto 1 ou 2 na divisão por 4, e A = {1,2,3,...,m} então {0} não é um dos conjuntos finais.
e) Considere a seguinte questão: É possível escolher números distintos do conjunto {4,6,8,..., 2m} de forma que sua soma seja \(\dfrac{m(m+1)}2 - 2\)? Qual a relação dessa pergunta com os itens anteriores?
Para a questão, considere que os conjuntos podem ter elementos repetidos. Por exemplo, {1,2,3,3,3,4,4} é um "conjunto" válido.
Considere um conjunto A finito de números reais não negativos. Se A possui 2 ou mais elementos, então Giovana pode realizar a seguinte operação:
1° Passo: Escolher 2 elementos x,y do conjunto A
2° Passo: Criar dois novos conjuntos. Os elementos do primeiro conjunto serão todos os elementos de A, exceto x e y, acrescidos de x+y. Os elementos do segundo conjunto serão todos os elementos de A, exceto x e y, acrescidos de |x-y|.
3º Passo: Apagar o conjunto A.
Por exemplo, caso seja A = {1,2,3,4,5}, escolhendo x = 4 e y = 5, os dois novos conjuntos serão: {1,2,3,9} e {1,2,3,1}
Digamos que Giovana realiza essa operação sucessivamente com os conjuntos que tem a disposição até não ser mais possível.
a) Mostre que se A tem m elementos, então Giovana pode realizar no máximo \(2^{m-1}-1\) operações. Após isso haverão \(2^{m}\) conjuntos com 1 elemento.
b) Mostre que os conjuntos finais obtidos não dependem da ordem de realização das operações.
c) Mostre que se m deixa resto 0 ou 3 na divisão por 4, e A = {1,2,3,...,m} então um dos conjuntos finais é {0}
d) Mostre que se m deixa resto 1 ou 2 na divisão por 4, e A = {1,2,3,...,m} então {0} não é um dos conjuntos finais.
e) Considere a seguinte questão: É possível escolher números distintos do conjunto {4,6,8,..., 2m} de forma que sua soma seja \(\dfrac{m(m+1)}2 - 2\)? Qual a relação dessa pergunta com os itens anteriores?
Última edição por DaoSeek em Dom 14 Jul 2024, 17:15, editado 1 vez(es)
DaoSeek- Jedi
- Mensagens : 316
Data de inscrição : 29/07/2022
Giovana Martins gosta desta mensagem
Re: Operação com conjuntos (combinatória)
Boa noite, Daoseek. Espero que esteja bem!
Quando possível, poste a resolução do meu problema, por favor kkkk.
Sou terrível em combinatória. Não consegui resolver este também, não kkk.
Giovana Martins- Grande Mestre
- Mensagens : 8026
Data de inscrição : 15/05/2015
Idade : 23
Localização : São Paulo
Re: Operação com conjuntos (combinatória)
Vou postar amanhã então.
Pra quem está se indagando como esse problema apareceu numa questão de cálculo, o problema original continha um produto de vários cossenos, como este:
\( \cos a_1 \cos a_2 \cos a_3 \cos a_4 \)
E usamos a identidade \( \cos x cos y = \dfrac{\cos(x+y) + \cos(x-y)}2\) para obter :
\( \cos a_1 \cos a_2 \cos a_3 \cos a_4 = \dfrac{\cos a_1 \cos a_2 \cdot \cos (a_3+a_4) + \cos a_1 \cos a_2 \cos (a_3-a_4)}2\)
Ou seja, sendo A o conjunto dos argumentos dos cossenos em cada produto, iniciamos com \(A = \{a_1, a_2, a_3, a_4\}\) e trocamos para \( \{a_1, a_2, a_3+a_4\}\) e\( \{a_1, a_2, a_3- a_4\}\). No problema estávamos interessados em continuar esse procedimento e ver o que encontraríamos, e daí surgiu essa questão.
Pra quem está se indagando como esse problema apareceu numa questão de cálculo, o problema original continha um produto de vários cossenos, como este:
\( \cos a_1 \cos a_2 \cos a_3 \cos a_4 \)
E usamos a identidade \( \cos x cos y = \dfrac{\cos(x+y) + \cos(x-y)}2\) para obter :
\( \cos a_1 \cos a_2 \cos a_3 \cos a_4 = \dfrac{\cos a_1 \cos a_2 \cdot \cos (a_3+a_4) + \cos a_1 \cos a_2 \cos (a_3-a_4)}2\)
Ou seja, sendo A o conjunto dos argumentos dos cossenos em cada produto, iniciamos com \(A = \{a_1, a_2, a_3, a_4\}\) e trocamos para \( \{a_1, a_2, a_3+a_4\}\) e\( \{a_1, a_2, a_3- a_4\}\). No problema estávamos interessados em continuar esse procedimento e ver o que encontraríamos, e daí surgiu essa questão.
Última edição por DaoSeek em Dom 14 Jul 2024, 18:42, editado 1 vez(es)
DaoSeek- Jedi
- Mensagens : 316
Data de inscrição : 29/07/2022
Re: Operação com conjuntos (combinatória)
Esqueci de falar no enunciado que A tem elementos não negativos (editei pra corrigir). Pra que o enunciado seja verdadeiro mesmo para elementos negativos, precisamos trocar x+y por |x+y| no segundo passo.
Segue então uma possível solução.
Segue então uma possível solução.
- Solução Letra a):
Pode ser contado diretamente, ou provado por indução, por exemplo. Se m = 1, A tem um elemento, e não é possível realizar nenhuma operação. Logo, a fórmula funciona nesse caso. Supondo verdadeira para m elementos, se A tem m+1 elementos, a primeira operação transforma esse conjunto em dois conjuntos de cardinalidade m. Em cada um deles é possível realizar \(2^{m-1} -1\) operações. Logo, o total possível de operações é \( 2(2^{m-1} -1 1) + 2 = 2^m - 1\). Portanto, segue por indução o resultado.
- Dica Letra b):
Se A = {a,b} então os conjuntos finais são {|a+b|}, {|a-b|}. Se A = { a,b,c} os conjuntos finais serão {|a+b+c|}, {|-a+b+c|}, {|a-b+c|}, {|a+b-c|}. Teste alguns casos, encontre um padrão e prove!
- Solução letra b):
Seja \(A = \{ a_1, a_2, \cdots, a_m\}\). Primeiro observamos que qualquer conjunto unitário obtido ao final das operações tem um elemento da forma \( \pm a_1 \pm a_2 \pm \cdots \pm a_m \) para alguma escolha de sinais. Agora observamos que temos \(2^{m}\) desses elementos e apenas \(2^{m-1} \) conjuntos. Isso significa que temos mais números da forma \( \pm a_1 \pm a_2 \pm \cdots \pm a_m \) do que conjuntos. Mais precisamente, temos o dobro de números. Para simplificar, vamos considerar A = {a,b,c}. Dessa forma, as possíveis escolhas de sinais são:
+a+b+c
-a+b+c
+a-b-c
+a+b-c
-a-b+c
-a+b-c
+a-b-c
-a-b-c
Ou seja, temos 8 possibilidades. Notamos que
|+a+b+c| = |-a-b-c|
|-a+b+c| = |+a-b-c|
|+a-b+c| = |-a+b-c|
|+a+b-c| = |-a-b+c|
Esses são justamente os 4 elementos finais. Repare que se para alguma escolha de sinais, digamos a-b+c, temos soma positiva, isto é, a-b+c ≥ 0, então na "escolha simétrica" (trocando todos os sinais) teremos soma negativa: -a+b-c ≤ 0. E a como a operação sempre privilegia a soma positiva, no final o resultado obtido é apenas uma das duas possibilidades.
Pra ver que de fato todas as "escolhas de sinais a menos de simetria" de fato ocorrem, basta mostrar como produzir cada uma delas. Isso é equivalente a dizer qual sequencia de conjuntos/elementos escolhemos até obter um conjunto unitário. Segue o algoritmo (vou dar um exemplo apenas, pois é mais fácil do que explicar o caso geral). Digamos que A = {a,b,c,d,e} e que queremos chegar no conjunto {|+a-b+c-d+e|}. Para isso, escolhemos dois elementos quaisquer de A e aplicamos a operação. Vamos supor que escolhemos os elementos a,b. Com isso obtemos os conjuntos
{a+b,c,d,e} e { a-b,c,d,e}
(o segundo conjunto poderia ser b-a, a depender de quem é maior, mas vamos supor que é a-b)
Notamos que em +a-b+c-d+e, os sinais de a e b são distintos. Por isso, vamos continuar a operação com o conjunto {a-b,c,d,e}. Escolhemos novamente 2 elementos, digamos que foram c,e. Com isso produzimos dois conjuntos, mas como os sinais de c,e são iguais em +a-b+c-d+e, o unico que interessa é:
{a-b,c+e,d}
Realizamos denovo a operação, digamos que escolhemos a-b, c+e. Cada termo já possui 2 parcelas, mas o importante é que na expressão +a-b+c-d+e, "a-b" tem sinal igual a "c+e". Assim, o conjunto escolhido será:
{a-b+c+e,d}
Por fim, observamos que na expressão a-b+d+e deve ter sinal oposto a d. Assim, o conjunto final será:
{(a-b+c+e)-d} = {a-b+c-d+e}
(poderia ser {d-(a-b+c+e)} = {-a+b-c+d-e} a depender de quem é maior, mas o ponto é que conseguimos obter |+a-b+c-d+e|)
De maneira geral, para produzir uma "escolha de sinais" basta proceder dessa forma. Isso verifica que os conjuntos finais não dependem da ordem das operações feitas.
- Solução Letra c):
Observamos que:
2-1 = 4-3 , daí: -1+2+3-4 = 0
6-5 = 8-7, daí: -5+6+7-8 = 0
Logo, em geral caso seja m = 4k, temos:
(-1+2+3-4) + (-5+6+7-+ (-9+10 +11-12) + ... + ( -(m-3)+(m-2)+(m-1)-m ) = 0
Logo, existe uma escolha de sinais do conjunto {1,2,3,...,m} que tem zero como resultado, caso seja m = 4k
Para m = 4k+3, similarmente temos:
(-1 -2 + 3) + (-4+5+6-7) + (-8+9+10-11) + ...+ ( -(m-3)+(m-2)+(m-1)-m ) = 0
Novamente existe uma escolha de sinais produzindo zero.
Portanto nesses casos, {0} é um conjunto final
- Solução Letra d):
Basta verificar que caso seja m = 4k+1 ou m = 4k+1, qualquer soma da forma:
±1±2±3±...±m
é impar!! Em particular, não pode ser zero!
- Solução Letra e):
Observamos que caso {0} seja um conjunto final de A = {1,2,...,m}, então existe uma escolha de sinais
±1±2±3±...±m
cuja soma é zero. Como 1+2+...+m = m(m+1)/2, isso é equivalente a dividir o conjunto A em uma união disjunta B∪C, onde a soma dos elementos de cada conjunto é m(m+1)/4. Seja B o conjunto que contém o elemento 1 e seja B' = {2}∪ B'', o conjunto obtido multiplicando-se cada elemento de B por 2. Notamos que B'' está contido em {4,...,2m} e que a soma dos elementos de B'' é m(m+1)/2 - 2.
Isto é, o problema de encontrar um subconjunto de {4,...,2m} cuja soma dos elementos é igual a m(m+1)/2 - 2 é equivalente a encontrar uma escolha de sinais de ±1±2±3±...±m cuja soma é 0.
Obs.: essa pergunta está aqui porque esse outro problema combinatório apareceu em outra solução dada para o problema de cálculo original!!.
DaoSeek- Jedi
- Mensagens : 316
Data de inscrição : 29/07/2022
![-](https://2img.net/i/empty.gif)
» Operação com conjuntos
» Operação com conjuntos
» Operação com Conjuntos
» Operação com Conjuntos
» Operação entre conjuntos
» Operação com conjuntos
» Operação com Conjuntos
» Operação com Conjuntos
» Operação entre conjuntos
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
|
|