CT. Odd People
This week we consider an odd number of odd people are milling about
with water pistols, on a large flat field. At a signal, everyone turns and squirts the closest
person (We may assume, since they are just milling about randomly, there is
a unique closest person to squirt.) Show that there will always be at least
person left dry!
Last week’s puzzle on Perfectly Summing Sets can be solved in many different ways; here’s one!
This one is not particularly efficient— you can look for some ways to have fewer numbers and a smaller total.
Let’s take the numbers 10, 15 and 18 as an example. We first pick a common multiple of these, say 90, which we’ll call P. We actually chose the least common multiple, but any multiple will do fine.
Now we add up P in a few ways:
P = 10 + 80
P = 15 + 75
P = 18 + 72
So we throw 80, 75 and 72 into our set to get 10, 15, 18, 72, 75 and 80
This is where we are being incredibly inefficient. There are many much more clever ways to get totals of 90, with a smaller least common multiple or using lots of powers of 2, which we’ll need in a moment.
The least common multiple Q of our set is 3600; the key now is: we have 3P, with the sums we have. Can we get all the way up to Q = 40 P? In other words, using more divisors of Q, can we sum up to another 37P?
Indeed we can, since 40 is full of divisors, and 37 = 2 + 5 + 10 + 20. So we add 2P, 5P, 10P and 20P to our set, obtaining
10, 15, 18, 72, 75, 80, 180, 450, 900, 1800
which all divide their total, 3600.
What if Q/P = 40 had not been full of divisors? Some multiple of 2
Of course, in this particular case, we could have done much better indeed, since 10, 15, 18, 2, 45 is a perfectly summing set with a total of 90.
Here’s another example, which shows some potential shortcuts. Consider 5, 7, 11, with a least common multiple of P = 385. We can get totals of 385 using lots of powers of 2, for a smaller grand total:
P = 5 * 77 = 5 * (1 + 4 + 8 + 64)
P = 7 * 55 = 7 * (1 + 2 + 4 + 16 + 32)
P = 11*35 = 11 * ( 1 + 2 + 32)
Now then, throwing in all the new numbers we used, 5, 20, 40, 320, 7, 14, 28, 112, 224, 11, 22 and 352,
we will have a least common multiple of Q = 5*7*11 * 64 = 64P.
Powers of two are always full of divisors, so we can be sure we can use factors of 64 to form 64 – 3 = 61. So we now throw in: 1P, 4P, 8P, 16P and 32P, obtaining the perfectly summing set:
5, 20, 40, 320, 7, 14, 28, 112, 224, 11, 22, 352, 385, 1540, 3080, 6160 and 12 320 which totals to 24640.
This looks bad, but the first procedure we gave gives a Q of 1 492 260: the smallest multiple of this Q that is full of divisors is probably in the trillions.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
kraDen said,
August 24, 2007 at 4:54 am
Assumption that there is a unique person to shoot at counts out the case where a number of people are at the corners of a regular polygon.
With 3 people 2 are equally close and will shoot each other. 3rd person will shoot whoever is closer of the other 2 but will remain dry.
Same argument works for any odd number of people. The fact that person A is closest to person B is an if and only if condition i.e. they will shoot each other. So if we have 2N+1 people they pair up into N pairs who shoot each other leaving 1 person left who shoots whoever they are closest too but who no one shoots.
Implies he/she remains dry.
Only thing I disagree with is that your statement “there is a unique closest person to squirt” implies that there “will always be at least
person left dry” where as in fact there will always be one and only one
person left dry.
cheers
Ken
cheers
Ken
strauss said,
August 26, 2007 at 11:51 am
This example might help:
Folks might not pair up, and there really may be more than one dry person!
kraDen said,
August 27, 2007 at 5:22 am
Hi,
Though a straight line can hardly be considered random (unless we are dealing with a 1 dimensional world) I see your point. Based on my new understanding I reread the question and thought about why you had specified an ‘odd’ number of people. That along with my original pairing idea Has put me onto what I think is the right track.
‘Odd’ is necessary to avoid the situation where people are in a configuration where they do pair up. So with an even number of people everyone could get shot.
So if we now take another look at the puzzle. We can eliminate those who form pairs as the shoot each other. We are sure that no larger self groups of equidistant people exist by the condition that ‘there is a unique closest person to squirt’. We are now left with a group again containing an odd number of people that do not pair up (i.e. in no case will the person you shoot be shooting back). Of these remaining group there must be one who is the furthest from any one else. By definition they can not be shot as all the rest are closer to someone else.
It is possible with certain layouts that multiple people may not be shot but the above shows that we a guaranteed of at least 1.
Cheers
Ken
giorgis said,
August 31, 2007 at 4:33 am
If a bunch of people are on the circumference of a circle with one poor fellow at the center, as long as they a little more than r appart everybody shoots the dude at the center. You put equispaced 5 to a circle, the dude in the center gets it, and only one on the rim gets it leaving 4 out of six dry.
(An even number of people though)
Giorgis
strauss said,
August 31, 2007 at 9:01 am
— but is it necessarily so, that someone must remain dry, regardless of how the folks are arranged?
thebiggnome said,
February 6, 2009 at 11:10 am
Say three odd people stand on the vertices of an equilateral triangle, facing the center. If each chooses to squirt the odd person on his or her left, no one remains dry.
Am I missing something?
strauss said,
February 6, 2009 at 12:27 pm
Hi there! Yes, we have to assume that everyone has a unique person to shoot at, that there are no “ties”. This is pretty natural– in the real world, one wouldn’t expect two distances to be exactly the same!