You may already be familiar with algorithms to compute the majority using multiple queries. The way these problems work is that you are given a bin of $n$ marbles of binary colors, whose colors you cannot see, and an oracle will tell you some information about a group of different marbles of $k$ size if you choose them.

In this case, $k=4$. $n$ is irrelevant, because I'm curious only about a subset of the bin of size $k$. In this case, our oracle will only tell you the difference between the numbers of the two colors $a$ and $b$, i.e. $|\sum b - \sum a|$, which $=2$ if there are $3$ of one color and $1$ of the other.

Thus, the following permutations of marbles colored 1 and 0 will return $2$:

  • 1110
  • 1101
  • 1011
  • 0111
  • 0001
  • 0010
  • 0100
  • 1000

My question is, is it possible to determine which color is in the majority using only one additional query? I know that it is possible to do so in 1.5 additional queries on average, by using a "control marble," which you know is in the majority (by knowing whether the other $n-4$ marbles are the same color).

If you replace the first marble in the group with the control marble, and then ask the oracle again, then one of the 8 possible permutations will result in a $4$, 3 of them will result in a $0$, and the remaining 4 will result in a $2$ (again). You can then replace the second marble in the group instead for the queries that returned $2$ again, and get a definitive answer as to whether the control marble is in the majority within that group or not.

So, is it possible to reduce this to one query to the oracle that will tell you what marble is in the majority within the group? If not, why?

  • $\begingroup$ Sorry, I'm not familiar with the algorithms you refer to in the first paragraph. Can you give a self-contained specification of this problem, without reference to some other problem we might not have seen? Assume we have no background, and give a complete description of the problem. In any case, if $k=4$, it sounds like you are dealing with a completely finite situation, so you should be able to work out the solution (once the problem has been clearly specified) through brute-force enumeration. Does that work? If it does, this isn't research-level. $\endgroup$ – D.W. May 8 '18 at 21:53
  • $\begingroup$ Relevant: "From discrepancy to majority", D. Eppstein and D. S. Hirschberg, Algorithmica 80 (4): 1278–1297, 2018, doi.org/10.1007/s00453-017-0303-7 $\endgroup$ – David Eppstein May 8 '18 at 22:03
  • $\begingroup$ @D.W. A solution is easy. A solution in one query is not. A self-contained example is if the control marble is of color 1. We need to determine whether that marble is in the majority of the $k$ size group in a single query to the oracle (if it's possible). This is true for exactly half of the possible color permutations (listed in the question) -- but is there an algorithm you can use to determine whether the group is one of those permutations in one query? $\endgroup$ – swallis May 8 '18 at 22:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.