[tex3]\frac{k}{a} \geq \frac{b - 1}{2b}[/tex3]
Olimpíadas ⇒ (IMO) Análise Combinatória Tópico resolvido
Moderador: [ Moderadores TTB ]
-
theblackmamba 
- Mensagens: 3723
- Registrado em: Ter 23 Ago, 2011 15:43
- Última visita: 20-11-19
- Localização: São Paulo - SP
Jan 2012
03
13:57
(IMO) Análise Combinatória
Em uma competição, existem [tex3]a[/tex3]
competidores e [tex3]b[/tex3]
juízes, onde [tex3]b \geq 3[/tex3]
e é um inteiro ímpar. Cada juíz aprova ou reprova o competidor. Suponha que [tex3]k[/tex3]
é o número tal que, para quaisquer dois juízes, sua escolha coincida para o máximo [tex3]k[/tex3]
competidores. Prove que:
Última edição: MateusQqMD (Dom 31 Mai, 2020 20:13). Total de 2 vezes.
Razão: tex --> tex3
Razão: tex --> tex3
"A coisa mais incompreensível do universo é que ele é compreensível"
- Albert Einstein
- Albert Einstein
-
Tassandro - Mensagens: 1905
- Registrado em: Sáb 15 Fev, 2020 17:01
- Última visita: 03-10-23
- Localização: Teresina, PI.
Mai 2020
31
06:37
Re: (IMO) Análise Combinatória
theblackmamba,
Forme uma matriz em que as colunas representam os concorrentes e as linhas representam o juízes. E temos um 1 quando o juiz aprova o competidor correspondente e um 0, caso contrário. Um par de entradas na mesma coluna é "bom" se for igual. Assim, o número de bons pares em quaisquer duas linhas é no máximo [tex3]k[/tex3] , de onde o número total de bons pares na matriz é no máximo [tex3]\binom{b}{2}\cdot k=\frac{kb(b-1)}{2}[/tex3] . Em qualquer coluna, se há [tex3]i[/tex3] zeros, então o total de bons pares é [tex3]\binom{i}2+\binom{j}2,[/tex3] sendo [tex3]j=b-i.[/tex3] Escrevendo [tex3]b=2m-1[/tex3] (já que [tex3]b[/tex3] é ímpar), nós temos que
[tex3]\binom i2+\binom j2-m^2=(m-i)^2+(m-i)=(m-j)^2+(m-j)\geq0\tag*{}[/tex3]
Uma vez que [tex3](m-i)\geq0[/tex3] ou [tex3](m-j)\geq0[/tex3] .
Então, o menor número de bons pares é [tex3]{am^2}=\frac{a(b-1)^2}4[/tex3] . Assim,
[tex3]\frac{a(b-1)^2}4\leq\frac{kb(b-1)}2\to\frac{k}{a} \geq \frac{b - 1}{2b}\tag*{}[/tex3]
Forme uma matriz em que as colunas representam os concorrentes e as linhas representam o juízes. E temos um 1 quando o juiz aprova o competidor correspondente e um 0, caso contrário. Um par de entradas na mesma coluna é "bom" se for igual. Assim, o número de bons pares em quaisquer duas linhas é no máximo [tex3]k[/tex3] , de onde o número total de bons pares na matriz é no máximo [tex3]\binom{b}{2}\cdot k=\frac{kb(b-1)}{2}[/tex3] . Em qualquer coluna, se há [tex3]i[/tex3] zeros, então o total de bons pares é [tex3]\binom{i}2+\binom{j}2,[/tex3] sendo [tex3]j=b-i.[/tex3] Escrevendo [tex3]b=2m-1[/tex3] (já que [tex3]b[/tex3] é ímpar), nós temos que
[tex3]\binom i2+\binom j2-m^2=(m-i)^2+(m-i)=(m-j)^2+(m-j)\geq0\tag*{}[/tex3]
Uma vez que [tex3](m-i)\geq0[/tex3] ou [tex3](m-j)\geq0[/tex3] .
Então, o menor número de bons pares é [tex3]{am^2}=\frac{a(b-1)^2}4[/tex3] . Assim,
[tex3]\frac{a(b-1)^2}4\leq\frac{kb(b-1)}2\to\frac{k}{a} \geq \frac{b - 1}{2b}\tag*{}[/tex3]
Dias de luta, dias de glória.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 1 Respostas
- 777 Exibições
-
Última msg por FelipeMartin