Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

Question

I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.

I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it A, were repeated an equal number of times.

For example:

1) A = 1 8 8 1 8 1 1 8 : the answer is yes, every number is repeated 2 times.

2) A = 7 8 8 5 5 4 7 8 : the answer is no.

I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it B, which I can define as follow: Given the array A, B[i] contains the number of repetitions of the element A[i] within A.

For example:

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

As you might think and expect, the only thing left to do would be to check if every element of B is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.

So, to check if all the elements of B are the same, I summed all of them and divided the result by the number of elements of B: if the result was equal to an element of B (for example the first, B[0]) then the algorithm returned true (false otherwise).

Taking the example above:

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

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

I know it's absurd, but that's what I came up to.

I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.

I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.

Thank you in advance.

Answer 1

No, your algorithm doesn't work. Consider if the array A is

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

Then the array B will be

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

The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5. This is equal to the first element of B, so your algorithm will output "Yes". Nonetheless, not all elements of B are the same, and the correct answer is "No". So, your algorithm gives the wrong output on this case.

Nice try, though! Figuring out how to build B was probably the hardest part of this problem.

---

How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers. Let $u,v,w$ denote how often each of those numbers appear. Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$. We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation

$${u^2 + v^2 + w^2 \over u+v+w} = u$$

such that $v\ne u$ or $w \ne u$. This is equivalent to

$$u^2 + v^2 + w^2 = u(u+v+w),$$

where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$. I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha. The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well. In retrospect I guess I could have simplified further to

$$v^2 + w^2 = uv + uw$$

but I didn't notice and it turned out not to matter.

Answer 2

[2,2,5,5,5,5,5,6,6,6,6,6,6] is a counterexample.

how I found that: ​ ​ ​ (The last step of this was a Python script.) ​ For them to not all be equal, there need to be at least two distinct numbers that appear. ​ However, averages are strictly between the min and the max, so to pass your criterion there must be at least three distinct numbers. ​ I simply figured there ought to be a counterexample with only three distinct numbers. ​ For the reason I gave two sentences ago, with just three distinct numbers, one only needs to check for whether-or-not the average is the middle number. ​ With that observation, I wrote a Python script to try triples with respect to the lexicographic order of [sum,largest,middle,smallest], and the array I gave corresponds to the smallest counterexample that script found.