T01 Embaralhamento falho
Considere o seguinte trecho de código, que permuta os elementos do vetor deck:
for (int i = 0; i < N; i++) {
int r = (int) (Math.random() * N);
String t = deck[r];
deck[r] = deck[i];
deck[i] = t;
}
Suponha que deck[0..N-1] contém \(N\) strings diferentes. Prove que, se \(N>2\), então a permutação que obtemos ao executar o código acima não resulta em uma permutação uniforme de deck (isto é, há permutações mais prováveis do que outras). O que acontece no caso \(N=2\)?
Sugestão. Embora não seja a única, uma possível abordagem consiste em fazer uma certa contagem. Para essa abordagem, considere inicialmente o caso em que \(N\) é um número primo. Para o caso geral, você pode usar o postulado de Bertrand: para todo número real \(x>1\), existe um número primo \(p\) com \(x<p\leq2x\).
Observação. Lembre que há uma folha específica para entrega de exercícios teóricos: