nosso roteiro ta bumbandoooooooooooo ! UHAUHUAUAHUSHAU'EM BREVE NOSSO VIDEO NO YOUTUBE ;Dfiiico feraw ! Um torneio eliminatorio de boxe foi organizada. Temos 114 participantes e por isso temos 57 partidas na primeira rodada do torneio. Na segunda rodada, os 57 lutadores restantes foram emparelhado, resultando em 28 jogos, um lutador ganhou por WO (isto e, nao tem que lutar nessa rodada). Os 29 lutadores restantes foram entao emparelhado, e assim por diante.(a) Quantos jogos ao todo foram necessarios para determinar um vencedor do torneio?(b) Quantos jogos seria necessario se n pessoas participaram no torneio (onde n representa um inteiro fixo, mas nao especificado numero)?Vamos definir uma funcao F(n) que devolve o numero de lutas necessarias para descobrir o vencedor do torneio com n participantes:F(n) : numero de lutas necessarias para descobrir o vencedor do torneio com n participantes.Observe que quando o n e par entao podemos realizar n/2 lutas e restaram n/2 lutadores. Quando n e impar, entao podemos realizar n/2 lutas e restaram n/2 + 1 lutadores. Logo, podemos obter a seguinte recursao:$$F(1) = 0$$$$F(n) =\begin{cases}F(\frac{n}{2}) + \frac{n}{2} & \mbox{se n e par}\\F(\frac{n}{2}+1) + \frac{n}{2} & \mbox{se n e impar}\\\end{cases}$$Testando alguns casos da recursao acima, podemos notar que F(n) = n-1, uma vez que, cada luta elimina um lutador e precisamos eliminar n-1 lutadores para encontrar o vencedor do torneio.Podemos provar este fato resolvendo a recorrencia acima:Suponha n = $2^k$. Logo, podemos escrever a recorrencia da seguinte maneira:$$F(2^0) = 0$$$$F(2^k) = F(2^{k-1}) + 2^{k-1}$$Utilizando o metodo da substituicao:$$F(2^k) = F(2^{k-1}) + 2^{k-1} \\F(2^{k-1}) = F(2^{k-2}) + 2^{k-2} \\F(2^{k-2}) = F(2^{k-3}) + 2^{k-3} \\\vdots \\F(2^{1}) = F(2^{0}) + 2^{0} \\$$Somando tudo temos:$$F(2^k) = F(2^{0}) + 2^{0} + 2^{1} + 2^{2} + \ldots + 2^{k-1} \\F(2^k) = 2^{k} - 1\\$$Desfazendo a substituicao, temos:$$F(n) = n - 1\\$$ Seja um fracao continua x = $[a_1;a_2,a_3,\ldots,a_n]$, chamamos de convergentes ou fracoes parciais a sequencia de numeros racionais dados por:,ou seja, Retirado: http://pt.wikipedia.org/wiki/Fra%C3%A7%C3%A3o_cont%C3%ADnuaVamos denotar cada $c_i por \dfrac{p_i}{q_i}$$c_0$ = $a_0$. Logo, $p_0 = a_0$ e $q_0 = 1$$c_1$ = $a_0 + \dfrac{1}{a_1}$ = $\dfrac{a_0a_1 + 1}{a_1}$. Logo, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$$c_2$ = $a_0 + \cfrac{1}{ a_1 + \cfrac{1}{a_2}}$ = $\displaystyle \dfrac{a_0a_1a_2 + a_2 + a_0}{a_1a_2 + 1}$ = $\dfrac{a_2(a_0a_1 + 1) + a_0}{a_1a_2 + 1}$ = $\dfrac{a_2p_1 + p_0}{q_1a_2 + q_0}$ Teorema: Seja $c_i = \dfrac{p_i}{q_i}$ a i-esima fracao parcial da fracao continua $[a_0,a_1,\ldots,a_n]$. Entao o numerador $p_i$ e o denominador $q_i$ de $c_i$ satisfazem as seguintes relacoes: $p_i = a_ip_{i-1} + p_{i-2}$, $q_i = a_iq_{i-1} + q_{i-2}$, para i=2,3,$\ldots$,n sendo que $p_0 = a_0$, $q_0=1$, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$1/11.0000000000000000003/21.5000000000000000007/51.39999999999999991117/121.41666666666666674141/291.41379310344827580199/701.414285714285714368239/1691.414201183431952558577/4081.4142156862745098871393/9851.4142131979695431453363/23781.4142136248948695708119/57411.41421355164605477819601/138601.41421356421356425647321/334611.414213562057320406114243/807821.414213562427273363275807/1950251.414213562363799470665857/4708321.4142135623746898701607521/11366891.4142135623728213643880899/27442101.4142135623731419979369319/66251091.41421356237308693022619537/159944281.41421356237309647854608393/386139651.414213562373094701131836323/932223581.414213562373095145318281039/2250586811.414213562373095145768398401/5433397201.4142135623730951451855077841/13117381211.4142135623730951454478554083/31668159621.41421356237309514510812186007/76453700451.41421356237309514526102926097/184575560521.41421356237309514563018038201/445604821491.414213562373095145152139002499/1075785203501.414213562373095145367296043199/2597175228491.414213562373095145886731088897/6270135660481.4142135623730951452140758220993/15137446549451.4142135623730951455168247530883/36545028759381.41421356237309514512477253282759/88227504068211.41421356237309514530122754096401/213000036895801.41421356237309514572722761475561/514227577859811.414213562373095145175568277047523/1241455192615421.414213562373095145423859315570607/2997137963090651.4142135623730951451023286908188737/7235731118796721.4142135623730951452470433131948081/17468600200684091.4142135623730951455964153172084899/42172931520164901.41421356237309514514398739476117879/101814463241013891.41421356237309514534761632124320657/245801858002192681.41421356237309514583922003724759193/593418179245399251.414213562373095145202605639573839043/1432638216492991181.414213562373095145489133282872437279/3458694612231381611.4142135623730951451180872205318713601/8350027440955754401.4142135623730951452850877693509864481/20158749494142890411.4142135623730951456882627592338442563/48667526429241535221.414213562373095145 Professor Ricardo tem n chips supostamenteidenticos que, em principio, sao capazes de testar uns aos outros. Um testadordo professor acomoda dois chips ao mesmo tempo. Quando os chips sao carregados,cada chip testa o outro e relata se e bom ou ruim. Um bom chip de sempre relatacom precisao se o outro chip e bom ou ruim, mas a resposta de um mau chip naopode ser confiavel. Assim, os quatro possiveis resultados de um teste sao comose