I have the following math quiz:
You have 4 Red Balls & 4 Green Balls. You cannot see the color of the balls but you have a machine (or function) which takes 2 balls as input and returns true, when both balls are red, or false if it isnt the case. What is the minimum amount of measures you have to do, to find 2 red balls (you dont have to the function to return true, its also okay when you can be 100% sure that two balls are red).
Just by trying I've found 6 as my smallest number:
- Divide the set into 3 smaller sets: 3, 3, 2
- For both sets with 3 balls measure each ball against the others. This takes 3 moves per set. If the function never returns true, you know there must be 2 greens in the set.
- As both sets with 3 balls must contain 2 green balls, the remaining 2 balls must be red.
How can I prove that the least amount of moves is 6 (or maybe lower)?