T01 Embaralhamento
Considere o seguinte trecho de código, que permuta os elementos do vetor deck:
for (int i = 0; i < N; i++) {</span><br /><span style="font-family: 'courier new', courier, monospace;"> int r = (int) (Math.random() * N);</span><br /><span style="font-family: 'courier new', courier, monospace;"> String t = deck[r];</span><br /><span style="font-family: 'courier new', courier, monospace;"> deck[r] = deck[i];</span><br /><span style="font-family: 'courier new', courier, monospace;"> deck[i] = t;</span><br /><span style="font-family: 'courier new', courier, monospace;">}
Suponha que deck[0..N-1] contenha \(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 que outras). O que acontece no caso \(N=2\)?
Sugestão. Use o postulado de Bertrand: para todo número real \(x>1\), existe um número primo \(p\) com \(x<p\leq2x\).