\n
\nO matem\u00e1tico franc\u00eas \u00c9douard Lucas<\/em><\/strong> (1842-1891), criador do famoso jogo Torre de Han\u00f3i, formulou um problema desafiador pouco antes de sua morte, em 1891. <\/p>\n
O problema possui o seguinte enunciado:<\/p>\n \u201cDe quantas maneiras [tex]n[\/tex] casais ([tex]n \\geq 3[\/tex]) podem sentar em [tex]2n[\/tex] cadeiras diferentes em torno de um c\u00edrculo de modo que pessoas do mesmo sexo n\u00e3o se sentem juntas e que nenhum homem fique ao lado de sua respectiva mulher?\u201d<\/strong><\/em><\/p>\n O enunciado do problema \u00e9 bem simples, n\u00e3o \u00e9 mesmo? J\u00e1 a sua solu\u00e7\u00e3o… A solu\u00e7\u00e3o do Problema de Lucas n\u00e3o \u00e9 o nosso foco principal; os Lemas de Kaplansky<\/strong> s\u00e3o os objetos de estudo desta Sala! Alguns conceitos e princ\u00edpios de contagem ser\u00e3o necess\u00e1rios para uma boa compreens\u00e3o do tema: Combina\u00e7\u00e3o simples; Princ\u00edpio Multiplicativo e Princ\u00edpio Aditivo. Se voc\u00ea n\u00e3o se lembra deles \u00e9 s\u00f3 clicar no bot\u00e3o abaixo.<\/p>\n \n \n ✏<\/strong> <\/span> Combina\u00e7\u00e3o simples<\/strong>: Uma das maneiras de agruparmos elementos de um dado conjunto \u00e9 escolh\u00ea-los levando-se em considera\u00e7\u00e3o apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos \u00e9 denominado uma Combina\u00e7\u00e3o simples<\/em><\/strong>. Particularmente, quando escolhemos [tex]r[\/tex] dentre [tex]n[\/tex] elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combina\u00e7\u00e3o simples de [tex]n[\/tex] elementos tomados [tex]r[\/tex] a [tex]r[\/tex]. A quantidade desse tipo de agrupamentos \u00e9 denotada por [tex]C_{n,r}[\/tex] ou [tex]C_n^r\\,[\/tex] e assim definida:<\/p>\n [tex]C_{n,r}=C_n^r=\\dfrac{n!}{(n-r)!\\,r!} \\text{, com } n,r\\in\\mathbb{N} \\text{ e } r\\leqslant n[\/tex].<\/p>\n \n ✏<\/strong> <\/span>Princ\u00edpio Fundamental da Contagem, ou Princ\u00edpio Multiplicativo<\/strong>: Se<\/p>\n ent\u00e3o o n\u00famero total de maneiras de tomarmos sucessivamente essas [tex]k[\/tex] decis\u00f5es (D1<\/strong> e D2<\/strong> e [tex]\\cdots[\/tex] e Dk<\/strong>) \u00e9 igual ao produto \n ✏<\/strong> <\/span>Princ\u00edpio Aditivo<\/strong>: Se<\/p>\n ent\u00e3o, a quantidade de maneiras de tomarmos uma das [tex]k[\/tex] decis\u00f5es (D1<\/strong> ou D2<\/strong> ou [tex]\\cdots[\/tex] ou Dk<\/strong>) \u00e9 \n<\/div>\n<\/div>\n Para compreendermos a utilidade do Primeiro Lema de Kaplansky, vamos come\u00e7ar explorando a resolu\u00e7\u00e3o de um problema, antes de apresentarmos o Lema.<\/p>\n \n Observe que, particularmente, o conjunto do primeiro exemplo representa uma possibilidade de escolha para este problema, mas o do segundo n\u00e3o, j\u00e1 que [tex]4[\/tex] e [tex]5[\/tex] s\u00e3o consecutivos. \nNo caso geral, o n\u00famero de subconjuntos com [tex]p[\/tex] elementos de [tex]\\{1,2,3,\u2026,n\\}[\/tex], com [tex]p\\leq n\/2[\/tex], nos quais n\u00e3o h\u00e1 n\u00fameros consecutivos \u00e9 [tex]C_{n-p+1}^{p}[\/tex]. Este \u00e9 exatamente o Primeiro Lema de Kaplansky: <\/p>\n \n Mesmo sabendo de sua import\u00e2ncia, o objetivo principal desta Sala n\u00e3o \u00e9 a nota\u00e7\u00e3o em si, mas sim resolver problemas de contagem utilizando essa nova t\u00e9cnica. Na verdade, a ideia central \u00e9 repetir esse racioc\u00ednio, mas em problemas com \u201croupagens\u201d diferentes. \n \n●<\/span> distribu\u00edmos os cinco sinais [tex]\u2212[\/tex] (o primeiro passo da escolha) Logo, pelo Princ\u00edpio Multiplicativo, a escola tem [tex]\\boxed{1\\cdot C_{6}^{4}=1 \\cdot 15=15}[\/tex] maneiras diferentes de repor essas aulas.<\/p><\/div>\n \n \n●<\/span> colocamos os nove sinais [tex]\u2212[\/tex]; Esse n\u00famero representa as maneiras de escolher os dias das provas. Mas, ap\u00f3s escolher os dias, temos que organizar a ordem na qual as provas ser\u00e3o aplicadas e isso pode ser feito de [tex]5!=120[\/tex] modos. \n Note que, at\u00e9 aqui, todos os problemas apresentavam, basicamente, sempre a mesma restri\u00e7\u00e3o: apenas n\u00e3o possuir n\u00fameros consecutivos<\/strong>. Novamente, iremos marcar com o sinal [tex]+[\/tex] a posi\u00e7\u00e3o dos elementos que far\u00e3o parte do subconjunto e com o sinal [tex]\u2212[\/tex] a posi\u00e7\u00e3o dos elementos que n\u00e3o far\u00e3o parte. Assim: \n \n Seguindo o mesmo racioc\u00ednio, vamos indicar pelo sinal [tex]+[\/tex] os elementos selecionados e pelo sinal [tex]-[\/tex] os n\u00e3o selecionados. Assim, arrumamos uma fila com [tex]p[\/tex] sinais [tex]+[\/tex] e [tex](n-p)[\/tex] sinais [tex]-[\/tex] de modo que entre dois sinais [tex]+[\/tex] haja pelo menos [tex]r[\/tex] sinais [tex]-[\/tex]. Como buscamos apenas solu\u00e7\u00f5es inteiras n\u00e3o negativas, podemos resolver a equa\u00e7\u00e3o fazendo as seguintes substitui\u00e7\u00f5es \n Como todas as inc\u00f3gnitas s\u00e3o n\u00fameros inteiros n\u00e3o negativos, aprendemos na Sala Combina\u00e7\u00e3o Completa<\/strong><\/span><\/a> que essa equa\u00e7\u00e3o possui [tex]\\boxed{CR\\,_{p+1}^{n-p-(p-1)r}=C_{n-(p-1)r}^{p}= \\dfrac {[n-(p-1)r]!}{p! \\cdot [n-p-(p-1)r]!}}[\/tex] solu\u00e7\u00f5es.<\/div>\n \n Assim, j\u00e1 podemos apresentar a generaliza\u00e7\u00e3o prometida do Primeiro Lema de Kaplansky:<\/p>\n \n Observe que: O Segundo Lema de Kaplansky apresenta a mesma ideia do Primeiro Lema; por\u00e9m, imp\u00f5e uma considera\u00e7\u00e3o extra de que [tex]1[\/tex] e [tex]n[\/tex] s\u00e3o n\u00fameros consecutivos. \n (I)<\/strong> Se o elemento [tex]1[\/tex] pertence ao subconjunto, ent\u00e3o devemos escolher [tex](p-1)[\/tex] elementos do conjunto [tex]\\{3,4,5,\u2026,n-1\\}[\/tex] (como o [tex]1[\/tex] figura no conjunto, n\u00e3o podemos ter os elementos [tex]2[\/tex] e [tex]n[\/tex]) tomando o cuidado de n\u00e3o escolhermos elementos consecutivos. \n (II)<\/strong> Se o elemento [tex]1[\/tex] n\u00e3o pertence ao subconjunto, ent\u00e3o devemos escolher [tex]p[\/tex] elementos do conjunto [tex]\\{2,3,4,\u2026,n\\}[\/tex] (como o [tex]1[\/tex] n\u00e3o figura no conjunto, podemos ter os elementos [tex]2[\/tex] e [tex]n[\/tex]) tomando o cuidado de n\u00e3o escolhermos elementos consecutivos. \n Pelo Princ\u00edpio Aditivo, por [tex]\\textcolor{#8B5A2B}{(i)}[\/tex] e por [tex]\\textcolor{#8B5A2B}{(ii)}[\/tex], a quantidade [tex]Q[\/tex] de subconjuntos em quest\u00e3o \u00e9 dada por: \n Assim, podemos apresentar o Segundo Lema de Kaplansky:<\/p>\n \n N\u00e3o estamos interessados que voc\u00ea apenas utilize e memorize as f\u00f3rmulas apresentadas; mas que, principalmente, voc\u00ea pratique e entenda as t\u00e9cnicas de contagem. Assim, note que ao resolvermos um problema com o Segundo Lema, utilizamos duas vezes o Primeiro Lema e o Princ\u00edpio Aditivo. \n Logo, pelo Princ\u00edpio Aditivo, h\u00e1 [tex]\\boxed{3+4=7}[\/tex] maneiras para a escolha dos dias de aula. \n \n Finalizando, pelo Princ\u00edpio Multiplicativo h\u00e1 [tex]\\boxed{450 \\cdot 24=10800}[\/tex] solu\u00e7\u00f5es para o problema.\n<\/p><\/div>\n \n Podemos generalizar o Segundo Lema, assim como fizemos para o Primeiro. \n 2\u00ba)<\/strong> Para a contagem do segundo caso, como os elementos [tex]1[\/tex] e [tex]2[\/tex] n\u00e3o pertencem ao subconjunto, ent\u00e3o devemos escolher tr\u00eas cadeiras do conjunto [tex]\\{ 3,4,5,6,7,8,9,10,11,12 \\}[\/tex] de modo que haja pelo menos duas cadeiras vazias entre os escolhidos. \n Portanto, pelo Princ\u00edpio Aditivo, a solu\u00e7\u00e3o deste problema \u00e9 dada pela soma das quantidades encontradas nos casos, ou seja, [tex]20 + 20 = \\boxed{40 \\text{ subconjuntos}}.[\/tex]\n<\/p><\/div>\n \n Assim, j\u00e1 podemos generalizar o Segundo Lema de Kaplansky. Essa generaliza\u00e7\u00e3o \u00e9 a resposta \u00e0 seguinte pergunta:<\/p>\n \n Aqui est\u00e1 a generaliza\u00e7\u00e3o prometida do Segundo Lema de Kaplansky:<\/p>\n \n Que tal voc\u00ea resolver alguns exerc\u00edcios?<\/p>\n \n \n \n \n \n \n \n A express\u00e3o que representa a quantidade de maneiras distintas das tr\u00eas agentes serem distribu\u00eddas nos vag\u00f5es \u00e9 <\/p>\n a) [tex]C_{4}^{3}+3![\/tex] \n \n \n \n \n \n 2\u00ba caso:<\/strong> Se o cavaleiro [tex]1[\/tex] n\u00e3o pertence ao grupo, ent\u00e3o devemos escolher [tex]5[\/tex] cavaleiros do conjunto [tex]\\{2,3,4,5,6,7,8,9,10,11,12 \\}[\/tex] de modo que n\u00e3o haja cavaleiros consecutivos. Isso pode ser feito de [tex]f(11,5)=C_{7}^{5}=21[\/tex] maneiras. \n \n \n \n \n Para encerrar, caso queira ver a Solu\u00e7\u00e3o de Kaplansky para o Problema de Lucas<\/strong>, clique AQUI<\/strong><\/span><\/a>. Equipe COM – OBMEP<\/strong><\/span><\/p>\n<\/div>\n \n \n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Clique no bot\u00e3o abaixo para visualizar a Sala. Lemas de Kaplansky O matem\u00e1tico franc\u00eas \u00c9douard Lucas (1842-1891), criador do famoso jogo Torre de Han\u00f3i, formulou um problema desafiador pouco antes de sua morte, em 1891. \u00c9douard Lucas Imagem extra\u00edda de Mancala World. O problema possui o seguinte enunciado: \u201cDe quantas maneiras [tex]n[\/tex] casais ([tex]n \\geq … <\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/b020.jpg\")
\u00c9douard Lucas<\/span>
\nImagem extra\u00edda de Mancala World<\/a>.<\/p>\n
\nEsse problema ficou conhecido como o Problema de Lucas, ou M\u00e9nage Pr\u00f2bleme, e os matem\u00e1ticos da \u00e9poca demoraram mais de meio s\u00e9culo para resolv\u00ea-lo.
\nParticularmente, em 1943, o matem\u00e1tico canadense-americano Irving Kaplansky<\/em><\/strong> (1917-2006) apresentou uma solu\u00e7\u00e3o para o Problema de Lucas em um artigo publicado no Bulletin of the American Mathematical Society<\/em>. Nessa solu\u00e7\u00e3o, Kaplansky desenvolveu dois m\u00e9todos de contagem que s\u00e3o conhecidos hoje como \u201cLemas de Kaplansky\u201d. (Na Matem\u00e1tica, lema \u00e9 um resultado intermedi\u00e1rio que \u00e9 utilizado para provar um outro resultado mais importante.)<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-2.jpg\")
Irving Kaplansky<\/span>
\nImagem extra\u00edda de PeoplePill<\/a>.<\/p>\n
\nEnunciaremos esses resultados e resolveremos alguns problemas de contagem com essas novas ferramentas. Apesar de n\u00e3o serem comumente abordados nas escolas durante o estudo da An\u00e1lise Combinat\u00f3ria, veremos que as aplica\u00e7\u00f5es desses lemas s\u00e3o simples e nos ajudar\u00e3o a solucionar exerc\u00edcios bem interessantes. Com rela\u00e7\u00e3o ao Problema de Lucas, devido \u00e0 variedade de t\u00e9cnicas de contagem em sua resolu\u00e7\u00e3o, deixaremos sua demonstra\u00e7\u00e3o no final da Sala apenas como leitura para os interessados.<\/p>\n\n
\n[tex]\\qquad \\qquad \\boxed{m_1\\times m_2 \\times \\cdots \\times m_k} \\, .[\/tex] <\/p>\n\n
\n[tex]\\qquad \\qquad \\boxed{m_1+ m_2 + \\cdots + m_k} \\, .[\/tex] <\/p>\n
\n
\n
\n
\n[tex]\\qquad \\qquad A = \\{1, 2, 3, 4, 5, 6, 7, 8\\},[\/tex]
\nde modo que em cada subconjunto n\u00e3o haja n\u00fameros consecutivos?
\nSolu\u00e7\u00e3o:<\/strong>
\nPara que n\u00e3o haja a necessidade de enumerar exaustivamente todos os subconjuntos com a propriedade requerida, ao definir um subconjunto de [tex]A[\/tex], iremos marcar com o sinal [tex]+[\/tex] a posi\u00e7\u00e3o dos elementos que far\u00e3o parte do subconjunto e com o sinal [tex]\u2212[\/tex] a posi\u00e7\u00e3o dos elementos que n\u00e3o far\u00e3o parte, considerando a posi\u00e7\u00e3o dos elementos na sequ\u00eancia [tex] 1, 2, 3, 4, 5, 6, 7, 8.[\/tex] Assim, por exemplo:
\n[tex]\\qquad \\{3, 6, 8\\}[\/tex] seria representado por [tex]\\,-\\,-\\,+\\, \\,-\\,-\\,\\,+\\,-\\,+[\/tex],
\n[tex]\\qquad \\{4, 5, 7\\}[\/tex] seria representado por [tex]\\, -\\,-\\,-\\,+\\,+\\,-\\,+\\,-[\/tex].<\/p>\n
\nPara formar um subconjunto com tr\u00eas elementos, sem dois n\u00fameros consecutivos, devemos distribuir tr\u00eas sinais [tex]+[\/tex] e cinco sinais [tex]\u2212~[\/tex], sem que haja dois sinais [tex]+[\/tex] consecutivos.
\nPara fazer isso:
\n●<\/span> colocamos os cinco sinais [tex]\u2212[\/tex] (o primeiro passo da escolha);
\n●<\/span>em seguida, distribu\u00edmos os tr\u00eas sinais [tex]+[\/tex] nos seis espa\u00e7os que ficaram definidos (representados abaixo pelos quadradinhos), com no m\u00e1ximo um sinal por espa\u00e7o. Perceba que isso pode ser feito de [tex]C_{6}^{3}[\/tex] maneiras diferentes.![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/002tex.png\")
\nFinalmente, utilizando o princ\u00edpio Multiplicativo, temos [tex]\\boxed{1 \\cdot C_{6}^{3}=20}[\/tex] subconjuntos.\n<\/div>\n
\nJustificativa:<\/strong> Seguindo o mesmo racioc\u00ednio da resolu\u00e7\u00e3o do Problema 1, devemos ter [tex]p[\/tex] sinais [tex]+[\/tex] e “[tex]n-p[\/tex]” sinais [tex]-[\/tex]. Ao distribuir os sinais [tex]-~[\/tex], temos “[tex]n-p+1[\/tex]” espa\u00e7os para os [tex]p[\/tex] sinais [tex]+[\/tex]. Assim, teremos:
\n●<\/span> [tex]1[\/tex] modo de posicionar os sinais [tex]\u2013[\/tex] e
\n●<\/span> [tex]C_{n-p+1}^{p}[\/tex] maneiras de organizar os sinais [tex]+[\/tex] nos espa\u00e7os criados.
\nAssim, n\u00e3o haver\u00e1 n\u00fameros consecutivos nos subconjuntos.<\/p>\n
\nO n\u00famero de subconjuntos com [tex]p[\/tex] elementos de [tex]\\{1,2,3,\u2026,n\\}[\/tex], sendo [tex]p\\leq n\/2 [\/tex] e nos quais n\u00e3o h\u00e1 n\u00fameros consecutivos, \u00e9:
\n[tex]\\qquad \\qquad \\boxed{f(n,p)= C_{n-p+1}^{p}}.[\/tex]<\/div>\n
\nEnt\u00e3o, que tal resolver alguns problemas?<\/p>\n
\nQuantas s\u00e3o as possibilidades distintas de se atender \u00e0s condi\u00e7\u00f5es dessa reposi\u00e7\u00e3o?
\n Solu\u00e7\u00e3o:<\/strong>
\nVamos representar cada um dos nove s\u00e1bados dispon\u00edveis para reposi\u00e7\u00e3o, em sequ\u00eancia, por um elemento do conjunto
\n[tex]\\qquad \\qquad S=\\{1,2,3,4,5 ,6,7,8,9\\}[\/tex].
\nAssim, para resolver este problema, vamos procurar subconjuntos do conjunto [tex]S[\/tex] com quatro elementos que n\u00e3o sejam n\u00fameros consecutivos, j\u00e1 que as reposi\u00e7\u00f5es n\u00e3o devem ser feitas em s\u00e1bados consecutivos.
\nPara formar um subconjunto com quatro elementos, sem dois n\u00fameros consecutivos, devemos distribuir quatro sinais [tex]+[\/tex] e cinco sinais [tex]\u2212[\/tex], sem que haja dois [tex]+[\/tex] consecutivos.
\nAssim,<\/p>\n
\n●<\/span> em seguida, nos seis espa\u00e7os que ficaram definidos, colocamos os quatro sinais [tex]+[\/tex], com no m\u00e1ximo um sinal por espa\u00e7o. ![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/003tex.png\")
Perceba que isso pode ser feito de [tex]C_{6}^{4}=15[\/tex] maneiras diferentes.
\nEm nota\u00e7\u00e3o, teremos: [tex]f(9,4)= C_{9-4+1}^{4}=C_{6}^{4}[\/tex].<\/p>\n
\nSolu\u00e7\u00e3o:<\/strong>
\nVamos representar cada um dos quatorze dias poss\u00edveis por um elemento do conjunto
\n[tex]\\qquad \\qquad M=\\{1,2,3,4,5,6,7,8,9,10,11,12,13,14\\}.[\/tex]
\nAssim, devemos contar quantos subconjuntos de [tex]S[\/tex] com [tex]5[\/tex] elementos existem de modo a n\u00e3o ter elementos consecutivos. Para realizar essa contagem,<\/p>\n
\n●<\/span> em seguida, distribu\u00edmos os cinco sinais [tex]+[\/tex] nos dez espa\u00e7os que ficaram definidos.
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/004tex.png\")
\nPerceba que isso pode ser feito de [tex]C_{10}^{5}=252[\/tex] maneiras diferentes.
\nUsando a nota\u00e7\u00e3o definida, teremos [tex]f(14,5)= C_{14-5+1}^{5}=C_{10}^{5}=252[\/tex].<\/p>\n
\nPortanto, pelo Princ\u00edpio Multiplicativo, h\u00e1 [tex]\\boxed{252\\cdot 120=30240}[\/tex] modos de aplicar essas provas.\n<\/p><\/div>\n
\nE se, por exemplo, quis\u00e9ssemos contar quantos subconjuntos, com [tex]3[\/tex] elementos, do conjunto [tex]S=\\{1,2,3,4,5,6,7,8,9,10\\}[\/tex] podemos formar de modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[\/tex] elementos n\u00e3o escolhidos, como por exemplo o subconjunto [tex]\\{2,6,9\\}[\/tex]?
\nVamos l\u00e1! <\/p>\n
\n[tex]\\qquad \\{2, 6, 9\\}[\/tex] seria representado por [tex]\\,-\\, +\\, -\\, -\\, -\\, +\\, -\\, -\\, +\\, -\\,,[\/tex]
\n[tex]\\qquad \\{3, 5, 10\\}[\/tex] seria representado por [tex]\\,- \\,- \\,+ \\,- \\,+ \\,- \\,- \\,- \\,- \\,+\\,.[\/tex]
\n(Observe que, particularmente, o conjunto do primeiro exemplo representa uma possibilidade de escolha, mas o do segundo n\u00e3o, j\u00e1 que [tex]3[\/tex] e [tex]5[\/tex] n\u00e3o possuem dois elementos n\u00e3o escolhidos entre eles.)
\nPara fazer essa contagem, vamos, inicialmente, posicionar os [tex]3[\/tex] sinais de [tex]+[\/tex] formando uma fila e deixando [tex]4[\/tex] espa\u00e7os entre eles.![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/005tex.png\")
Os sinais de [tex]\u2013[\/tex] ser\u00e3o colocados nesses espa\u00e7os. Vamos chamar de [tex]x,\\,y,\\, z[\/tex] e [tex]w[\/tex] a quantidade de sinais [tex]\u2013[\/tex] que colocaremos no primeiro, segundo, terceiro e quarto espa\u00e7os, respectivamente.![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/006tex.png\")
Dessa forma, devemos ter a seguinte equa\u00e7\u00e3o linear com solu\u00e7\u00f5es inteiras e n\u00e3o negativas:
\n[tex]\\qquad x+y+z+w=7[\/tex], com [tex]y \\geq 2~[\/tex] e [tex]~z \\geq 2.[\/tex]
\nNa Sala de Estudos sobre Combina\u00e7\u00f5es Completas<\/strong><\/span><\/a> aprendemos a contar quantas solu\u00e7\u00f5es tem uma equa\u00e7\u00e3o desse tipo, com esse tipo de restri\u00e7\u00f5es.
\nSubstituindo, [tex]y=a+2[\/tex] e [tex]z=b+2[\/tex], obtemos a equa\u00e7\u00e3o [tex]x+a+b+w=3[\/tex], que tem
\n[tex]\\qquad CR_{4}^{3}=C_{4+3-1}^{3}=C_{6}^{3}= \\dfrac {6!}{3! \\cdot 3!}= 20[\/tex] solu\u00e7\u00f5es.
\nPortanto, h\u00e1 [tex]20[\/tex] subconjuntos com [tex]3[\/tex] elementos de modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[\/tex] elementos n\u00e3o escolhidos.
\n\u00c9 dessa forma que iremos generalizar o Primeiro Lema de Kaplansky.<\/p>\n
\nChamando de [tex]x_{1},\\,x_{2},\\,x_{3},\\, \\dots ,\\,x_{p}[\/tex] e [tex]x_{p+1}[\/tex] a quantidade de sinais [tex]\u2013[\/tex] que ser\u00e3o colocados em cada um dos [tex]p+1[\/tex] espa\u00e7os existentes entre os sinais [tex]+[\/tex], temos que
\n[tex]\\qquad x_{1}+x_{2}+x_{3}+ \\dots +x_{p}+x_{p+1}=n-p[\/tex], com [tex]x_{1},~x_{p+1} \\geq 0~[\/tex] e [tex]~x_{2},~x_{3},~\\dots~,~x_{p} \\geq r[\/tex].<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/b002.png\")
<\/p>\n
\n [tex]\\qquad \\boxed{x_{2}=r+y_{2}}[\/tex], [tex]~\\boxed{x_{3}=r+y_{3}}, ~\\dots~ ,\\, \\boxed{x_{p}=r+y_{p}}[\/tex]
\nna equa\u00e7\u00e3o
\n [tex]\\qquad x_{1}+x_{2}+x_{3}+ \\dots +x_{p}+x_{p+1}=n-p.[\/tex]
\nCom isso, segue que:
\n[tex]\\qquad x_{1}+(r+y_{2})+(r+y_{3})+ \\dots + (r +y_{p})+x_{p+1}=n-p\\\\
\n\\qquad x_1+y_2+y_3+\u22ef+y_p+x_{p+1}+(p-1)r=n-p\\\\
\n\\qquad x_{1}+y_{2}+y_{3}+ \\dots + y_{p} +x_{p+1}=n-p-(p-1)r.[\/tex]<\/p>\n
\nDado um conjunto [tex]\\{1,2,3,4,\u2026,n \\}[\/tex], o n\u00famero de subconjuntos com [tex]p[\/tex] elementos de modo que entre cada dois elementos escolhidos para o subconjunto haja pelo menos [tex]r[\/tex] elementos n\u00e3o escolhidos \u00e9:
\n[tex]\\qquad \\qquad \\boxed{f(n,p,r)=C_{n-(p-1)r}^{p}}.[\/tex]<\/p>\n
\nPara [tex]r=0[\/tex], temos [tex]f(n,p,0)= C_{n}^{p}[\/tex]; o que corresponde ao n\u00famero de Combina\u00e7\u00f5es Simples de [tex]n[\/tex] elementos tomados [tex]p[\/tex] a [tex]p.[\/tex]
\nPara [tex]r=1[\/tex], temos [tex]f(n,p,1)=C_{n-p+1}^{p}[\/tex]; o que corresponde ao Primeiro Lema de Kaplansky.\n<\/p><\/div>\n
\n
\n
\n
\nPortanto, consideraremos nesta discuss\u00e3o que os n\u00fameros [tex]1,~2,~3,~\u2026,~n [\/tex] est\u00e3o colocados em c\u00edrculo, nesta ordem.
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/01\/b016.png\")
<\/p>\n
\nPor estarem em c\u00edrculo, os n\u00fameros [tex]1[\/tex] e [tex]n[\/tex] agora s\u00e3o consecutivos. Para resolver este problema, vamos determinar:
\n(I)<\/strong> a “quantidade de subconjuntos que satisfazem as condi\u00e7\u00f5es do problema e aos quais o elemento [tex]1[\/tex] pertence” e
\n(II)<\/strong> a “quantidade de subconjuntos que satisfazem as condi\u00e7\u00f5es do problema e aos quais o elemento [tex]1[\/tex] n\u00e3o pertence”.<\/p>\n
\nOra, como vimos no Primeiro Lema de Kaplansky, o n\u00famero de maneiras de escolhermos [tex](p-1)[\/tex] elementos (sinais [tex]+[\/tex]) em um conjunto que possui [tex](n-3)[\/tex] elementos (portanto, [tex](n-3)-(p-1)[\/tex] sinais [tex]-[\/tex]) sem que haja elementos consecutivos \u00e9 dado por:
\n[tex]\\qquad \\qquad f(n-3,p-1)=C_{n-3-(p-1)+1}^{p-1}=C_{n-p-1}^{p-1}\\,.\\qquad \\textcolor{#8B5A2B}{(i)}[\/tex]<\/p>\n
\nNovamente, pelo Primeiro Lema de Kaplansky, o n\u00famero de maneiras de escolhermos [tex]p[\/tex] elementos (sinais [tex]+[\/tex]) em um conjunto que possui [tex](n-1)[\/tex] elementos (portanto, [tex](n-1-p)[\/tex] sinais [tex]-[\/tex]) sem que haja elementos consecutivos \u00e9 dado por:
\n[tex]\\qquad \\qquad f(n-1,p)=C_{n-1-p+1}^{p}=C_{n-p}^{p}\\,.\\qquad \\textcolor{#8B5A2B}{(ii)}[\/tex]<\/p>\n
\n[tex]\\qquad Q=C_{n-p-1}^{p-1}~+~C_{n-p}^{p}~.[\/tex]
\nUtilizando agora a defini\u00e7\u00e3o de combina\u00e7\u00e3o simples, temos:
\n[tex]\\qquad Q=C_{n-p-1}^{p-1}~+~C_{n-p}^{p}\\\\
\n\\qquad Q=\\dfrac {(n-p-1)!}{(p-1)!\\cdot (n-2p)!} + \\dfrac{(n-p)!}{p! \\cdot (n-2p)!}\\\\
\n\\qquad Q=\\dfrac{(n-p-1)! \\cdot p+(n-p)!}{p! \\cdot (n-2p)!}\\\\
\n\\qquad Q=\\dfrac {(n-p-1)! \\cdot[p+(n-p)]}{p! \\cdot (n-2p)!}\\\\
\n\\qquad Q=\\dfrac {n \\cdot (n-p-1)!}{p! \\cdot (n-2p)!}\\\\
\n\\qquad Q= \\dfrac {n}{(n-p)} \\cdot \\dfrac{(n-p)!}{p! \\cdot (n-2p)!}\\\\
\n\\qquad Q= \\dfrac {n}{(n-p)} \\cdot C_{n-p}^{p}\\,.[\/tex]<\/p><\/div>\n
\nO n\u00famero de subconjuntos com [tex]p[\/tex] elementos do conjunto [tex]\\{1,2,3,\u2026,n \\}[\/tex] nos quais n\u00e3o h\u00e1 n\u00fameros consecutivos, considerando [tex]1[\/tex] e [tex]n[\/tex] como consecutivos, \u00e9 igual a
\n [tex]\\qquad \\qquad \\boxed{g(n,p)=\\dfrac {n}{n-p} \\cdot C_{n-p}^{p}}.[\/tex]<\/div>\n
\nVejamos mais dois problemas…<\/p>\n
\nSolu\u00e7\u00e3o<\/strong>:
\nVamos representar cada um dos sete dias da semana (segunda, ter\u00e7a, quarta, quinta, sexta, s\u00e1bado e domingo) por um elemento do conjunto [tex]S=\\{1,2,3,4,5 ,6,7 \\}[\/tex]. Perceba que no nosso problema os n\u00fameros [tex]1[\/tex] e [tex]7[\/tex] s\u00e3o consecutivos.
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/01\/b017.png\")
\nEnt\u00e3o, vamos abrir o problema em dois casos:
\n(I)<\/strong> O dia [tex]1[\/tex] foi escolhido; e
\n(II)<\/strong> O dia [tex]1[\/tex] n\u00e3o foi escolhido.<\/p>\n(I)<\/strong> No primeiro caso, com o [tex]1[\/tex] no conjunto, temos apenas tr\u00eas situa\u00e7\u00f5es a considerar: [tex]\\{1,3,5 \\}[\/tex], [tex]\\{1,3,6 \\}[\/tex] e [tex]\\{1,4,6 \\}[\/tex]. Poder\u00edamos ter conseguido esse resultado sem a necessidade de escrever todas as solu\u00e7\u00f5es:
\nUtilizando o Primeiro Lema de Kaplansky, como o [tex]1[\/tex] j\u00e1 foi escolhido, temos que escolher dois elementos do conjunto [tex]\\{3, 4, 5, 6 \\}[\/tex] sem que haja dois consecutivos. Da\u00ed, temos dois sinais [tex]\u2013[\/tex] e dois sinais [tex]+[\/tex]:
\n[tex]\\qquad \\qquad \\quad \\quad\\textcolor{#4B240B}{ \\Box~-~\\Box~-~\\Box} [\/tex]
\nAo formar uma fila com os sinais [tex]-[\/tex], h\u00e1 [tex]C_{3}^{2}=3[\/tex] modos de posicionar os sinais [tex]+[\/tex].
\n(II)<\/strong> J\u00e1 no segundo caso, temos que escolher tr\u00eas elementos [tex]\\{ 2,3,4,5,6,7 \\}[\/tex] sem que haja n\u00fameros consecutivos. Aqui devemos ter tr\u00eas sinais [tex]\u2013[\/tex] e tr\u00eas sinais [tex]+[\/tex], sem que haja dois sinais [tex]+[\/tex] consecutivos.
\n[tex]\\qquad \\qquad \\quad \\quad\\textcolor{#4B240B}{ \\Box~-~\\Box~-~\\Box~-~\\Box} [\/tex]
\nAo formar uma fila com os sinais [tex]-[\/tex], h\u00e1 [tex]C_{4}^{3}=4[\/tex] modos de posicionar os sinais [tex]+[\/tex].<\/ul>\n
\nObserve que, utilizando a f\u00f3rmula do Segundo Lema de Kaplansky, temos:
\n[tex]\\qquad \\qquad g(7,3)= \\dfrac{7}{7-3} \\cdot C_{7-3}^{3}= \\dfrac{7}{4} \\cdot 4=\\boxed{~7~}.[\/tex]<\/p><\/div>\n
\nSolu\u00e7\u00e3o:<\/strong>
\n(1)<\/strong> O n\u00famero de maneiras de escolhermos as [tex]4[\/tex] cadeiras das [tex]15[\/tex] poss\u00edveis em c\u00edrculo, sem que haja cadeiras adjacentes, pode ser calculada pelo Segundo Lema de Kaplansky:
\n[tex]\\quad \\begin{align}g(15,4)&=\\dfrac{15}{15-4} \\cdot C_{15-4}^{4}= \\dfrac{15}{11} \\cdot C_{11}^{4}\\\\
\n&= \\dfrac {15}{11} \\cdot \\dfrac {11!}{4! \\cdot (11-4)!}\\\\
\n&=450.\\end{align}[\/tex]
\nPortanto, existem [tex]450[\/tex] modos de escolher as cadeiras que ser\u00e3o ocupadas.
\n(2)<\/strong> Ap\u00f3s escolher as cadeiras, devemos posicionar os amigos; o que pode ser feito de [tex]4!=24[\/tex] maneiras.<\/p>\n
\nPara ajudar na generaliza\u00e7\u00e3o, considere o problema a seguir e acompanhe atentamente a sua solu\u00e7\u00e3o.<\/p>\n
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2024\/01\/Kaplansky-12.jpg\")
\nSolu\u00e7\u00e3o:<\/strong>
\nObserve que o que queremos calcular \u00e9 a quantidade de subconjuntos, com [tex]3[\/tex] elementos, do conjunto
\n[tex]\\qquad \\qquad \\quad \\quad S= \\{1,2,3,4,5,6,7,8,9,10,11,12 \\}[\/tex], sendo [tex]1[\/tex] e [tex]12[\/tex] consecutivos,
\nde modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[\/tex] elementos n\u00e3o escolhidos; como, por exemplo, os subconjuntos [tex]\\{1,4,10 \\}[\/tex], [tex]\\{2,7,11 \\}[\/tex] e [tex]\\{3,6,12 \\}[\/tex].
\nPara resolver este problema, vamos dividi-lo em dois casos:
\n1\u00ba) Os subconjuntos que cont\u00eam algum dos elementos [tex]\\{ 1, 2 \\}[\/tex]; e
\n2\u00ba) Os subconjuntos que n\u00e3o cont\u00eam nenhum dos elementos [tex]\\{ 1, 2 \\}[\/tex].<\/p>\n1\u00ba)<\/strong> Para a contagem do primeiro caso, como o [tex]1[\/tex] j\u00e1 figura no conjunto, n\u00e3o podemos ter os elementos [tex]2[\/tex], [tex]3[\/tex], [tex]11[\/tex] e [tex]12[\/tex]. Assim, devemos escolher dois elementos do conjunto [tex]\\{4,5,6,7,8,9,10 \\}[\/tex] de modo que haja pelo menos duas cadeiras vazias entre os escolhidos.
\n●<\/span> Ora, como vimos na generaliza\u00e7\u00e3o do Primeiro Lema de Kaplansky, o n\u00famero de maneiras de escolhermos dois elementos em um conjunto que possui sete elementos de modo que n\u00e3o haja pelo menos dois elementos consecutivos \u00e9 dado por:
\n[tex]\\qquad f(7,2,2)=C_{7-(2-1)2}^{2}=C_{5}^{2}=10.[\/tex]
\n●<\/span> De modo an\u00e1logo, tamb\u00e9m temos [tex]10[\/tex] subconjuntos, satisfazendo a restri\u00e7\u00e3o, em que o elemento [tex]2[\/tex] est\u00e1 contido.
\nAssim, temos [tex]2 \\cdot 10=20[\/tex] subconjuntos que cont\u00eam algum dos elementos do conjunto [tex]\\{1, 2 \\}[\/tex].<\/p>\n
\nNovamente, pela generaliza\u00e7\u00e3o do Primeiro Lema de Kaplansky, o n\u00famero de maneiras de escolhermos [tex]3[\/tex] elementos em um conjunto que possui [tex]10[\/tex] elementos de modo que entre cada dois elementos escolhidos haja, no conjunto, pelo menos [tex]2[\/tex] n\u00e3o escolhidos \u00e9:
\n[tex]\\qquad f(10,3,2)=C_{10-(3-1) \\cdot 2}^{3}=C_{6}^{3}=20.[\/tex]<\/ul>\n
\nEssa quantidade de subconjuntos pode ser calculada pela soma do “n\u00famero de subconjuntos satisfazem as exig\u00eancias e n\u00e3o cont\u00eam um dos elementos [tex]\\{1,2,3,4, \\cdots , r \\}[\/tex]” com “o n\u00famero de subconjuntos que satisfazem as exig\u00eancias e cont\u00eam um desses elementos”.
\nEnt\u00e3o, vamos calcular essa soma.
\nObserve que:
\nO n\u00famero de subconjuntos que satisfazem as exig\u00eancias e n\u00e3o cont\u00eam um dos elementos [tex]\\{1,2,3,4, \\cdots , r \\}[\/tex] \u00e9 igual a [tex]f(n-r,p,r).[\/tex]
\nO n\u00famero de subconjuntos que satisfazem as exig\u00eancias e cont\u00eam um desses elementos \u00e9 igual a [tex]r \\cdot f(n-2r-1,p-1,r).[\/tex]
\nCalculando a soma [tex]S=f(n-r,p,r)+rf(n-2r-1,p-1,r)[\/tex], temos:
\n[tex]\\qquad S=C_{n-r-(p-1) \\cdot r}^{p} + r\\cdot C_{n-2r-1-(p-1-1) \\cdot r}^{p-1}\\\\
\n\\qquad S=C_{n-p \\cdot r}^{p} + r \\cdot C_{n-p \\cdot r-1}^{p-1}\\\\
\n\\qquad S=C_{n-p \\cdot r}^{p}+r \\cdot \\dfrac {(n-p \\cdot r-1)!}{(p-1)! \\cdot (n-p \\cdot r-p)!}\\\\
\n\\qquad S=C_{n- p \\cdot r}^{p}+ r \\cdot \\dfrac {(n-p \\cdot r-1)!}{(p-1)!\\cdot (n-p \\cdot r-p)!} \\cdot \\dfrac {(n-p \\cdot r)}{(n-p \\cdot r)} \\cdot \\dfrac {p}{p}\\\\
\n\\qquad S=C_{n-p \\cdot r}^{p}+ \\dfrac {p \\cdot r} {n-p \\cdot r} \\cdot C_{n-p\\cdot r}^{p}\\\\
\n\\qquad S=C_{n-p \\cdot r}^{p} \\cdot \\left(1+ \\dfrac {p \\cdot r}{n-p \\cdot r}\\right)\\\\
\n\\qquad S=\\dfrac {n} {n-p \\cdot r} \\cdot C_{n-p \\cdot r}^{p}\\,.[\/tex]
\nA nota\u00e7\u00e3o dessa generaliza\u00e7\u00e3o \u00e9 [tex]\\boxed{g(n,p,r)= \\dfrac {n} {n-p \\cdot r} \\cdot C_{n-p \\cdot r}^{p}}.[\/tex]\n<\/div>\n
\nO n\u00famero de subconjuntos com [tex]p[\/tex] elementos do conjunto [tex]\\{1,2,3,4, \\cdots , n \\}[\/tex], considerando [tex]1[\/tex] e [tex]n[\/tex] consecutivos, de modo que entre cada dois elementos escolhidos para o subconjunto haja pelo menos [tex]r[\/tex] elementos n\u00e3o escolhidos \u00e9 dado por:
\n[tex]\\qquad \\qquad \\boxed{g(n,p,r)= \\dfrac {n} {n-p \\cdot r} \\cdot C_{n-p \\cdot r}^{p}}.[\/tex]
\nNote que:
\nPara [tex]r=0[\/tex], temos [tex]g(n,p,0)= C_{n}^{p}[\/tex]; o que corresponde ao n\u00famero de Combina\u00e7\u00f5es Simples de [tex]n[\/tex] elementos tomados [tex]p[\/tex] a [tex]p.[\/tex]
\nPara [tex]r=1[\/tex], temos [tex]g(n,p,1)= \\dfrac {n} {n-p} \\cdot C_{n-p}^{p}[\/tex]; o que corresponde ao Segundo Lema de Kaplansky.\n<\/div>\n
\n
\n
\n
\nBasta imaginar o conjunto [tex]\\{1, 2, 3, 4, …, 14, 15 \\}[\/tex], onde os elementos escolhidos recebem o sinal [tex](+)[\/tex] e os elementos n\u00e3o escolhidos [tex](-)[\/tex].
\nPortanto, teremos [tex]10[\/tex] sinais [tex]-[\/tex] gerando [tex]11[\/tex] espa\u00e7os.
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-13.jpg\")
\nAgora, temos [tex]C_{11}^{5}= 462[\/tex] maneiras para distribuir os sinais [tex]+[\/tex].
\nPortanto, o professor tem [tex]462[\/tex] modos de escolher as cadeiras.\n<\/div>\n<\/div>\n<\/div>\n
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-14.jpg\")
\nPara que as letras S<\/strong> n\u00e3o fiquem lado a lado, basta escolher [tex]4[\/tex] espa\u00e7os n\u00e3o adjacentes dois a dois.
\nPelo Primeiro Lema de Kaplansky, isso pode ser feito de [tex]f(10,4)=C_{7}^{4}=35[\/tex] maneiras.
\nAp\u00f3s escolhidas as posi\u00e7\u00f5es das letras S<\/strong>, temos que arrumar as outras letras ([tex]4[\/tex] letras I<\/strong>, [tex]1[\/tex] letra M<\/strong> e [tex]1[\/tex] letra P<\/strong>) nos [tex]6[\/tex] espa\u00e7os restantes, o que pode ser feito por uma permuta\u00e7\u00e3o com repeti\u00e7\u00e3o [tex]P_{6}^{4,1,1}= \\dfrac {6!}{4!\\,1!\\,1!}=30[\/tex].
\nPelo Princ\u00edpio Multiplicativo, h\u00e1 [tex]35 \\cdot 30=1050[\/tex] anagramas.\n<\/div>\n<\/div>\n<\/div>\n
\nb) [tex]C_{6}^{3}[\/tex]
\nc) [tex]C_{4}^{3} \\cdot 3![\/tex]
\nd) [tex]P_{6}^{3}[\/tex]
\ne) [tex]P_{4}^{3} \\cdot 3![\/tex] <\/p>\n
\n1\u00ba) Escolher os tr\u00eas vag\u00f5es que as agentes ser\u00e3o distribu\u00eddas;
\n2\u00ba) Organizar as tr\u00eas agentes nesses vag\u00f5es.
\nA primeira decis\u00e3o possui [tex]f(6,3)=C_{4}^{3}[\/tex] e a segunda decis\u00e3o possui [tex]P_{3}=3![\/tex] possibilidades de escolha.
\nLogo, pelo Princ\u00edpio Multiplicativo, temos [tex]C_{4}^{3} \\cdot 3![\/tex] maneiras distintas.\n<\/div>\n<\/div>\n<\/div>\n
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-15.jpg\")
\na) [tex]72[\/tex]
\nb) [tex]108[\/tex]
\nc) [tex]144[\/tex]
\nd) [tex]192[\/tex]
\ne) [tex]216[\/tex]<\/p>\n
\nIsso pode ser feito de [tex]f(6,3)=C_{4}^{3}=4[\/tex] maneiras.
\nPor\u00e9m, como a ordem de ocupa\u00e7\u00e3o desses lugares resulta em solu\u00e7\u00f5es diferentes, temos [tex]P_{3}=3!=6[\/tex] possibilidades de acomoda\u00e7\u00e3o para essas [tex]4[\/tex] maneiras.
\nLogo, h\u00e1 [tex]4 \\cdot 6=24[\/tex] possibilidades para as tr\u00eas primeiras ocupa\u00e7\u00f5es.
\nE para as tr\u00eas ocupa\u00e7\u00f5es seguintes temos, tamb\u00e9m, [tex]P_{3}=3!=6[\/tex] possibilidades de escolha.
\nPelo Princ\u00edpio Multiplicativo, h\u00e1 [tex]24 \\cdot 6=144[\/tex] solu\u00e7\u00f5es.
\nEntretanto, existe tamb\u00e9m a possibilidade de iniciar a ocupa\u00e7\u00e3o com as cadeiras [tex]2[\/tex] e [tex]5[\/tex]. Isso pode ocorrer de [tex]P_{2}=2!=2[\/tex] modos. Logo em seguida, temos [tex]P_{4}=4!=24[\/tex] modos para as quatro ocupa\u00e7\u00f5es seguintes.
\nNovamente pelo Princ\u00edpio Multiplicativo, h\u00e1 [tex]2 \\cdot 24=48[\/tex] solu\u00e7\u00f5es.
\nAssim, pelo princ\u00edpio aditivo, h\u00e1 [tex]144+48=192[\/tex] maneiras de ocupa\u00e7\u00e3o.\n<\/div>\n<\/div>\n<\/div>\n
\nImagine os doze cavaleiros em um c\u00edrculo.
\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-16.jpg\")
\nDevemos escolher cinco sem que haja cavaleiros consecutivos.
\n1\u00ba caso:<\/strong> Se o cavaleiro [tex]1[\/tex] pertence ao grupo, ent\u00e3o devemos escolher [tex]4[\/tex] cavaleiros do conjunto [tex]\\{3,4,5, \\cdots , 11 \\}[\/tex] (como o [tex]1[\/tex] j\u00e1 figura no conjunto, n\u00e3o podemos ter os cavaleiros [tex]2[\/tex] e [tex]12[\/tex]) tomando o cuidado de n\u00e3o pegarmos cavaleiros consecutivos. Isso pode ser feito de [tex]f(9,4)=C_{6}^{4}=15[\/tex] maneiras.<\/p>\n
\nPortanto, h\u00e1 [tex]15+21=36[\/tex] solu\u00e7\u00f5es.
\nUtilizando a nota\u00e7\u00e3o do Segundo Lema de Kaplansky, [tex]g(12,5)=\\dfrac {12}{(12-5)} \\cdot C_{(12-5)}^{5}= \\dfrac {12}{7} \\cdot C_{7}^{5}=36[\/tex] solu\u00e7\u00f5es.\n<\/div>\n<\/div>\n<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2023\/11\/Kaplansky-17.jpg\")
Imagem adaptada do site iStock<\/strong><\/a>. (Acesso em 24\/01\/2024.)<\/p>\n
\nAl\u00e9m disso, temos [tex]P_{4}=4!=24[\/tex] maneiras de arruma\u00e7\u00e3o dos carros nessas vagas.
\nAssim, pelo Princ\u00edpio Multiplicativo, existem [tex]294 \\cdot 24=7056[\/tex] maneiras de ocupar as quatro vagas.
\nObs: Na solu\u00e7\u00e3o desse exerc\u00edcio n\u00e3o consideramos a possibilidade de rota\u00e7\u00e3o do estacionamento.\n<\/div>\n<\/div>\n<\/div>\n
\nPelo Segundo Lema de Kaplansky, h\u00e1 [tex]g(12,4)=\\dfrac {12}{8} \\cdot C_{8}^{4}[\/tex] possibilidades para a escolha dos assentos dos homens. Al\u00e9m disso, temos [tex]P_4=4![\/tex] e [tex]P_8=8![\/tex] maneiras de acomodar os homens e as mulheres, respectivamente. Como a mesa pode ser girada de [tex]12[\/tex] maneiras, contamos cada solu\u00e7\u00e3o [tex]12[\/tex] vezes.
\nAssim, a resposta do problema \u00e9 [tex]\\dfrac {\\dfrac {12}{8} \\cdot C_{8}^{4} \\cdot 4! \\cdot 8!}{12}=203\\;212\\;800[\/tex].\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n \tA vers\u00e3o apresentada foi extra\u00edda da refer\u00eancia [3] e pode trazer alguma dificuldade para quem n\u00e3o est\u00e1 habituado com a leitura de textos de Matem\u00e1tica.\n<\/p>\n
\n
\n
\n[1]<\/strong> A Matem\u00e1tica do Ensino M\u00e9dio<\/strong>\u00a0(volume 2): Cole\u00e7\u00e3o do Professor de Matem\u00e1tica \u2013 Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto C\u00e9sar Morgado.
\n[2]<\/strong> A Matem\u00e1tica do Ensino M\u00e9dio<\/strong>\u00a0(volume 2): Cole\u00e7\u00e3o do Professor de Matem\u00e1tica \u2013 Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto C\u00e9sar Morgado.
\n[3]<\/strong> An\u00e1lise Combinat\u00f3ria e Probabilidade<\/strong>\u00a0\u2013 Augusto C\u00e9sar Morgado; Jo\u00e3o Bosco Pitombeira de Carvalho; Paulo Cesar Pinto Carvalho e Pedro Fernandez.
\n[4]<\/strong> Matem\u00e1tica Discreta<\/strong>: Cole\u00e7\u00e3o Profmat \u2013 Augusto C\u00e9sar Morgado; Paulo Cesar Pinto Carvalho.
\n[5]<\/strong> O Problema de Lucas (M\u00e9nage Pr\u00f2bleme) <\/strong>\u2013 Francisco Carpegiani Medeiros Borges. Online Encyclopedia Riordanica<\/strong><\/span><\/a><\/div>\n