Prova de correção do algoritmo para determinar se os elementos de uma matriz são repetidos um número igual de vezes

Peço desculpas pelo título longo, mas realmente não sabia como escrevê-lo de maneira diferente, sem a falta de informações sobre o conteúdo.

Recentemente, fiz um exame universitário sobre algoritmos paralelos. Um exercício me pediu para escrever um algoritmo para determinar se os elementos de uma matriz, vamos chamá-lo A, foram repetidos um número igual de vezes.

Por exemplo:

1) A = 1 8 8 1 8 1 1 8: a resposta é sim, todo número é repetido 2 vezes.

2) A = 7 8 8 5 5 4 7 8: a resposta é não.

Eu tive que escrever o algoritmo para um modelo específico de computação paralela, uma PRAM: o modelo exigia que eu usasse algumas técnicas para evitar conflitos de leitura / gravação e outros problemas, mas isso não é relevante. O que acabei com foi uma nova matriz, vamos chamá-la B, que eu posso definir da seguinte maneira:Given the array A, B[i] contains the number of repetitions of the element A[i] within A.

Por exemplo:

1) A = 1 8 8 1 8 1 1 8

B = 4 4 4 4 4 4 4 4

2)A = 7 8 8 5 5 4 7 8

B = 2 3 3 2 2 1 2 3

Como você pode pensar e esperar, a única coisa que resta a fazer é verificar se cada elemento de Bé igual ao outro, mas ... acontece que eu sou masoquista e a pressão do exame (mais eu tive um pouco temperatura) me levou a seguir outro caminho. Além disso, a comparação de elementos de uma matriz não é imediata usando este modelo de computação.

Portanto, para verificar se todos os elementos de Bsão iguais, somai todos eles e dividi o resultado pelo número de elementos de B: se o resultado foi igual a um elemento de B (por exemplo, o primeiro B[0]), o algoritmo retornou true( falsecaso contrário).

Tomando o exemplo acima:

1) sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32-> 32 / 8 = 4 = B[0]-> Sim.

2) sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18-> 18 / 8 ≠ 2 = B[0]-> Não.

Eu sei que é um absurdo, mas foi o que eu vim.

Eu verifiquei essa abordagem com várias combinações diferentes de matrizes / números, e parece funcionar. O problema é que estou tendo dificuldade em encontrar uma prova (matemática) de que o algoritmo está correto. Além do resultado do exame, que ainda não conheço, estou muito interessado em saber se há alguma prova / explicação matemática que indique que essa abordagem está correta ou não, e é por isso que preciso de ajuda.

Espero ter postado a pergunta no site StackExchange certo. Caso contrário, redirecione-me para o site certo.

Agradeço antecipadamente.

Não, seu algoritmo não funciona. Considere se a matriz A é

A = [1 1 1 1 1 2 2 3 3 3 3 3 3].

Então a matriz B será

B = [5 5 5 5 5 2 2 6 6 6 6 6 6].

A soma de B será 65 e o comprimento de B será 13; portanto, após a divisão, obteremos o número 5. Isso é igual ao primeiro elemento de B, portanto seu algoritmo emitirá "Sim". No entanto, nem todos os elementos de B são iguais e a resposta correta é "Não". Portanto, seu algoritmo fornece a saída errada neste caso.

Boa tentativa, no entanto! Descobrir como construir B foi provavelmente a parte mais difícil desse problema.

Como eu encontrei isso: não consegui encontrar um contra-exemplo com dois números distintos, então tentei com três números distintos. Indique que frequência cada um desses números aparece. Então a matriz terá o comprimento , e B conterá o valor repetido vezes, o valor repetido vezes, e repetido vezes, então a soma dos elementos de B é . Podemos encontrar um contra-exemplo se encontrarmos uma solução sobre os números inteiros positivos para a equação diofantina$u,v,w$$u+v+w$$u$$u$$v$$v$$w$$w$$u^2+v^2+w^2$

de modo que ou . Isso é equivalente a$v\ne u$$w \ne u$

onde são inteiros positivos e ou . Escolhi alguns valores pequenos de e tentei resolver esta equação diofantina usando Wolfram Alpha. A primeira solução que encontrei foi , , , mas também existem muitas outras. Em retrospecto, acho que poderia ter simplificado ainda mais$u,v,w$$v\ne u$$w \ne u$$u$$u=5$$v=2$$w=6$

mas eu não percebi e acabou não importando.

[2,2,5,5,5,5,5,6,6,6,6,6,6] é um contra-exemplo.

como descobri isso: (O último passo disso foi um script Python.) Para que nem todos sejam iguais, é necessário que haja pelo menos dois números distintos que apareçam. No entanto, as médias são estritamente entre o mínimo e o máximo, portanto, para passar pelo seu critério, deve haver pelo menos três números distintos. Eu simplesmente imaginei que deveria haver um contra-exemplo com apenas três números distintos. Pelo motivo que dei duas frases atrás, com apenas três números distintos, é preciso apenas verificar se a média é o número do meio. Com essa observação, escrevi um script Python para tentar triplos em relação à ordem lexicográfica de [sum, maior, médio, menor], e a matriz que dei corresponde ao menor contra-exemplo que o script encontrou.