Flashcard FC242098
Como determinar o máximo de pinos brancos quando a tentativa contém exatamente as mesmas letras da senha com repetições?
Sudoku e Jogos Similares
CESGRANRIO · 2012
Como determinar o máximo de pinos brancos quando a tentativa contém exatamente as mesmas letras da senha com repetições?
Mostrar resposta e comentário
Resposta
Máximo de pinos brancos: \(n-\displaystyle\sum_i \max(0,\,2m_i-n)\)
Explicação:
Para cada letra com multiplicidade \(m_i\) na senha de tamanho \(n\), é possível evitar que todas as suas cópias fiquem em posições corretas somente se \(m_i\le n-m_i\) (ou seja \(2m_i\le n\)).
Se \(2m_i>n\), pelo menos \(2m_i-n\) cópias dessa letra ficarão necessariamente nas mesmas posições (pinos pretos).
Somando-se esses inevitáveis pinos pretos por todas as letras obtém-se o mínimo de pinos pretos, e o máximo de brancos é \(n\) menos esse mínimo.
Exemplo:
Senha: A A A A B (n=5, multiplicidades: \(m_A=4,\;m_B=1\)).
Cálculo do mínimo de pretos: \(\max(0,2\cdot4-5)+\max(0,2\cdot1-5)=\max(0,3)+0=3\).
Logo, máximo de brancos = \(5-3=2\).
Tentativa que alcança isso: B A A A A → pinos pretos nas posições 2,3,4 (3 pretos) e pinos brancos nas outras 2 letras (B e um A em posições erradas).
Explicação:
Para cada letra com multiplicidade \(m_i\) na senha de tamanho \(n\), é possível evitar que todas as suas cópias fiquem em posições corretas somente se \(m_i\le n-m_i\) (ou seja \(2m_i\le n\)).
Se \(2m_i>n\), pelo menos \(2m_i-n\) cópias dessa letra ficarão necessariamente nas mesmas posições (pinos pretos).
Somando-se esses inevitáveis pinos pretos por todas as letras obtém-se o mínimo de pinos pretos, e o máximo de brancos é \(n\) menos esse mínimo.
Exemplo:
Senha: A A A A B (n=5, multiplicidades: \(m_A=4,\;m_B=1\)).
Cálculo do mínimo de pretos: \(\max(0,2\cdot4-5)+\max(0,2\cdot1-5)=\max(0,3)+0=3\).
Logo, máximo de brancos = \(5-3=2\).
Tentativa que alcança isso: B A A A A → pinos pretos nas posições 2,3,4 (3 pretos) e pinos brancos nas outras 2 letras (B e um A em posições erradas).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236914
Conteúdo do catálogo FC Concursos · Atualizado em