Minimal regular expressions?
http://uva.onlinejudge.org/external/127/12739.pdf
Minmax like Mastermind? FFT?
If A-B>C-D, A-C>B-D
http://uva.onlinejudge.org/external/127/12740.pdf
You have a graph of information: one node for every known tribe with the amount of known members in it, one edge between nodes if you know they are not the same tribe. You must make sure that at all times you either have one node with number bigger than the sum of the others or no independent set with sum bigger than the sum of the rest. Probably the proof of no big independent set comes from having cliques in your graph (you can only take at most 1 node from each clique for an independent set)
https://dl.dropboxusercontent.com/u/28563282/graph.html (wip)
Idea: a "good set" has a candidate tribe, a number of unknown tribes and a smaller good set completely connected to the candidate. When adding a node it goes to the unknown tribes, strategy is to request an edge between the candidate and an unknown iff (calculate condition from size of candidate, size of good set and number of unknowns), else give the edge to the smaller good set. Adding an edge between an unknown and the candidate pushes the unknown into the smaller good set (as unknown)
Conjecture: one strategy is having for each x a k where you queried all pairs (x,x-y) with y