All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Four balloons (Posted on 2016-01-12) Difficulty: 2 of 5
You are given four balloons: red, blue, green and yellow. Some (or all) of the balloons might be counterfeit.
A detector box can display the quantity of counterfeit balloons inside the box.
Your task is to detect all the genuine balloons using the detector box not over three times.

How would you do it?

Source: Russian Kvantik.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
re: Solution / efficiency challenge Comment 4 of 4 |
(In reply to Solution by Jer)

I investigated further.  In the worst case you do need to use the detector 3 times and put 3 in each time. (9 detections total.)  But in some of the cases after the first use or two you can use the machine fewer times or with fewer balloons.

none 0,0,0 *
A 1,1,1
B 1,1,0
C 1,0,1 *U
D 0,1,1 *
AB 2,2,1
AC 2,1,2 **
AD 1,2,2 **
BC 2,1,1 **
BD 1,2,1 **
CD 1,1,2
ABC 3,2,2 *
ABD 2,3,2 *U
ACD 2,2,3
BCD 2,2,2
ABCD 3,3,3 *
* The first detection is a 0 means only D is unknown, so use the machine a second time with just D.  4 detections.
* The first detection is a 3 means only D is unknown, so use the machine a second time with just D.  4 detections.

*U If the first two are 1,0 we are done.  C is the only fake.  6 detections.
*U If the first two are 2,3 we are done.  A,B,D are all fake.  6 detections.

** If the first two are 1,2 we know D is fake as is either A or B.  Just test A for the last use.  7 detections.
** If the first two are 2,1 we know C is fake as is either A or B.  Just test A for the last use.  7 detections.

The remaining six cases each begin with 1,1 or 2,2 but it will require testing ACD as my earlier post indicated.  9 detections.


This refinement reduces the expected number of uses from 3 down to 42/16=2.625 and the expected number of ballons in the machine from 9 down to 110/16=6.875


  Posted by Jer on 2016-01-14 10:40:32
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information