N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance error of E.
Player 1 has J locations where $$J < N$$
Player 2 has K locations where $$K < N$$
And for this problem we assume $$(J + K) > N$$
Players 1 and 2 agree to pool their locations to win the prize, but not before they each determine that they have the location of all N items. i.e. $$ J \bigcup K = N $$
Each player wants proof that the other player has some number of locations which they themselves do not have.
Is it possible for a player to prove to the other that they have a location that the other player does not have without disclosing that location?
I call my best guess the triangle game (or sub-game if your prefer) Here is one round of Player 1 trying to prove a location to player 2.
- Player 1 picks a point on the map x1,y1
- Player 2 picks a point on the map x2,y2 and a condition 'player 1's point will be in the triangle formed by x1,y1 x2,y2 and x3,y3'
- Player 1 picks a point on the map x3,y3 for which at least one his points falls inside the triangle
The condition in step 2 may also be 'player 1's point will not be in the triangle formed by x1,y1 x2,y2 and x3,y3'.
Player 2 will try to pick a point and a condition such that he can confirm that Player 1's point is not one of his K points.
The players may have to play this triangle game many rounds in order to verify a point.
This problem is based on the DARPA Network Challenge
N items=10 red balloons map=the continental United States prize=$40,000 distance error of E < 1.0 mile