How to find indexes of numbers that has many occurrences? Disclaimer: This is a simplified part of a question from my homework, addressing the point that I didn't figure out.


  let A be a 1-indexed sorted array of $n$ elements.
  
  There are at most 3 numbers that has at least $\lfloor n/4 \rfloor+1$
  occurrences.
  
  Find three indexes that will surely "hit" all such numbers. Explain why it's certain.


Because this is a sorted array, all such numbers will be stacked together, so each "number group" have a limited freedom to travel around the array.

It feels like going symmetrically for $n/4$, $n/2$ and $3n/4$ would be a wise guess, but I'm not sure how to prove it, and furthermore $n$ might not be a multiplicity of 4, so we have to round up or down the indexes.

How can I tackle such question?
Let's assume for simplicity that $n$ is divisible by $4$. Aiming for a contradiction, suppose that there is some popular number (a number is popular if it appears at least $n/4+1$ times) which does not appear at any of the positions $n/4,n/2,3n/4$. Denote this popular number by $x$.


  Can $x$ appear before position $n/4$? between positions $n/4$ and $n/2$? between positions $n/2$ and $3n/4$? after position $3n/4$?


If the answer to all of these questions is no, then we have reached a contradiction, and the only way out is that $x$ appears in one of the positions $n/4,n/2,3n/4$.