First, we note that if we have 1 gold ball only, then we need:
- 1 measurement in a group of 2 balls
- 2 measurements in a group of 4 balls
- 3 measurements in a group of 8 balls
Start by measuring 1, 2, 3, 4, 5.
- If there are gold balls in the group, then measure 6, 7, 8, 9, 10, 11.
- If there are gold balls in the group, then measure 5, 6, 7.
- If there are no gold balls among them, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 8, 9, 10, 11, so we can find the gold balls with the remaining 2 measurements.
- If there are gold balls in 5, 6, 7, then measure 5, 8, 9. If there are gold balls there, then 5 must be gold, and we can find the other gold ball among 6, 7, 8, 9, 10, 11 with the remaining 3 measurements. If there is no gold ball among 5, 8, 9, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 6, 7, so again we can find them with only 3 measurements.
- If there are no gold balls in the group, then measure 5, 12, 13.
- If there are no gold balls among them, then measure 14, 15. If none of them is gold, then measure individually 1, 2, and 3 to find which are the 2 gold balls among 1, 2, 3, 4. Otherwise, there is a gold ball among 1, 2, 3, 4, and among 14, 15, and we can find them with the remaining 3 measurements.
- If there are gold balls among 5, 12, 13, then measure 5, 14, 15. If none of them is gold, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 12, 13, so we can find them with 3 measurements. Otherwise, 5 is gold, and again we can find the other gold ball among 1, 2, 3, 4, 12, 13, 14, 15 with 3 measurements.
- If there are no gold balls among 1, 2, 3, 4, 5, then we measure 6, 7, 8.
- If there are gold balls in the group, then measure 9, 10, 11, 12, 13.
- If there are no gold balls among them, we measure individually 6, 7, 8, 14.
- If there is a gold ball among 9, 10, 11, 12, 13, then there is another one among 6, 7, 8. We measure 8, 9. If none of them is gold, then we can find the gold among 6, 7, and the gold among 10, 11, 12, 13, with 3 measurements total. If there is a gold ball among 8, 9, then we measure 10, 11, 12, 13. If none of them is gold, then 9 is gold and we find the other gold ball among 6, 7, 8 with 2 more measurements. If there is a gold ball among 10, 11, 12, 13, then we can find it with 2 measurements. The other gold ball must be 8.
- If there are no gold balls in the group, then measure 9, 10.
- If there are no gold balls among them, then measure individually 11, 12, 13, 14.
- If there are gold balls among 9, 10, then measure 11, 12, 13, 14. If there is a gold ball among them, then there is another one among 9, 10, and we can find them both with 3 measurements. Otherwise, we measure 9 and 10 individually.
