Combinatorial geometry question. (1 Viewer)

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Ten of Chad O Dude's top crushes are in a large field armed with one shot pistols. Each pair of girls is separated by a distinct distance. Each girl shoots the closest girl to her in an attempt to eliminate the competition.

What is the largest number of women Chad can end up with?
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Ten of Chad O Dude's top crushes are in a large field armed with one shot pistols. Each pair of girls is separated by a distinct distance. Each girl shoots the closest girl to her in an attempt to eliminate the competition.

What is the largest number of women Chad can end up with?
None, he can not luv dat feel.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Just want to clarify, is it possible for a girl to be shot before she gets a chance to shoot, and hence does not use her bullet?

ie. do all 10 bullets have to be shot.

But we could make this a probabiltiy question:

What are the chances that all 10 bullets are fired at Chad O Dude.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Nope, all shots are simultaneous.

(And lol).
 

Shadowdude

Cult of Personality
Joined
Sep 19, 2009
Messages
12,145
Gender
Male
HSC
2010
Just want to clarify, is it possible for a girl to be shot before she gets a chance to shoot, and hence does not use her bullet?

ie. do all 10 bullets have to be shot.

But we could make this a probabiltiy question:

What are the chances that all 10 bullets are fired at Chad O Dude.
0 because everyone loves The Chad:



---


and shouldn't the question in the OP be: "How many women are left over for Chad to hit on? Hence, assuming a 100% success rate in asking out women (because The Chad is great), how many girls will Chad end up with?"
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Well the girls are willing to kill for the chance of being with Chad, so I think its reasonable to assume they would say yes upon being asked out.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
I got 7?

Form a triangle with 3 girls, then using the other 7 girls form 3 pentagons around the triangle with each vertice of the triangle being a "centre" of a hexagon. The only girls who get shot are the three forming the triangle. Note that the hexagons are not regular.

Is this right or atleast close?
 
Last edited:

GoldyOrNugget

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
Oh seanie I love you!

First upper bound: 9 girls. At least one must die.

First lower bound: 8 girls. Obtained by creating 2 squares with 8 girls on the vertices (where both squares are separated by a lot) and placing the remaining 2 girls in the centre of the squares. The 8 vertex-girls will all fire at their respective centre-girls, killing only the two centre-girls. Add some random fuzzing to each coordinate to ensure distances are distinct.

So now we just have to decide whether we can indeed do 9. If the answer is 9, then only one girl dies, and the distance from her to every other girl is smaller than the distance between every other pair of girls. If you try to place points on a plane to keep this property true, you'll quickly realise that it's not possible. I can't quite explain why, but if we're sticking with regular polygons, the hexagon is the largest polygon before which the distance between a vertex and the centre exceeds the distance between consecutive points on the perimeter, and it only allows for 7 girls.

So I'll go with 8.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Nice! A straighforward proof we can't do better that 8:

Consider the set of all PAIRS of girls. These pairs can be ordered by distance. The closest pair of girls must shoot each other => at least two girls must die.

I think 8 is correct, I will try to do the "random fuzzing" tomorrow to obtain an explicit construction.
 

GoldyOrNugget

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
Consider the set of all PAIRS of girls. These pairs can be ordered by distance. The closest pair of girls must shoot each other => at least two girls must die.
That's very clean and elegant. How can I get better at these more abstract proofs? (i.e not the HSC-style "massage expression a into expression b")
 

abcdefghij123

New Member
Joined
Jun 12, 2011
Messages
9
Gender
Male
HSC
2012
obviously we cant go above 8 because there must be an absolute shortest distance between any two girls in the field (i don't really know what happens when there is equality in distances but it doesn't really matter for this idea). for this absolute shortest distance, both girls shoot at each other, hence killing two of them. whether 8 is possible i need to think about.

goldyornugget: your proof results in 4 deaths - remember, the girls in the centre of each square also get a shot!
 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
Ah yes, we probably can't obtain 8 then, I will think about this more later.
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
I got 7?

Form a triangle with 3 girls, then using the other 7 girls form 3 pentagons around the triangle with each vertice of the triangle being a "centre" of a pentagon. The only girls who get shot are the three forming the triangle. Note that the pentagons are not regular.
...
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
For 8 to be possible, all 10 girls must be in the same "system". For example, you can not separate them into 2 groups of 5 and forms squares etc. This is obvious since in a system atleast 2 girls must be shot. So for 8 to be possible there can only be one system.

Now in this system two girls must be placed very close to eachother such that they shoot eachother. The remaining 8 must be placed around them in an octagonal shape (although irregular) such that they shoot one of these girls. For this to be possible, they must be closer to one of these girls than any other girl. Let's consider a really simple case with a triangle where the vertices are two adjacent girls and one of the allocated girls to be shot. For the two girls to both be closer to the girl who needs to be shot than to eachother, the angle made at the centre of the octagonal shape must be >60.

However we have 8 girls to place, and if at the bare minimum we place them separated by a 60 degree angle, our "revolution" would be 480 degrees. Bu this is not possible since we can not exceed 360. Therefore we have a contradiction. Since this is the only possible way to arrange the girls for 8 of them to survive, and we just contradicted it and showed it's not a possible arrangement, it follows that there is no way to keep 8 girls alive.
 

abcdefghij123

New Member
Joined
Jun 12, 2011
Messages
9
Gender
Male
HSC
2012
realisenothing: i think you have to be a bit more rigorous in your proof that there cannot be 8. you are correct that if the two individuals who get shot are arbitrarily close then we have that contradiction because you are basically considering a 'revolution' around a single point - however in actuality there are two points. If the two people who get shot are a significant distance apart (but still the shortest distance), your thinking does not hold as a substantial proof.

I think I proved that 8 is impossible (although it is reasonably likely I have overlooked something or made a mistake), however it requires far more reasoning than that provided above (and far too much to feasibly post here). I showed goldyornugget and he seemed to agree that it held up. Furthermore, based on similar thinking to this proof, it is easy to show that 7 people is possible.
 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
realisenothing: i think you have to be a bit more rigorous in your proof that there cannot be 8. you are correct that if the two individuals who get shot are arbitrarily close then we have that contradiction because you are basically considering a 'revolution' around a single point - however in actuality there are two points. If the two people who get shot are a significant distance apart (but still the shortest distance), your thinking does not hold as a substantial proof.

I think I proved that 8 is impossible (although it is reasonably likely I have overlooked something or made a mistake), however it requires far more reasoning than that provided above (and far too much to feasibly post here). I showed goldyornugget and he seemed to agree that it held up. Furthermore, based on similar thinking to this proof, it is easy to show that 7 people is possible.
Pretty much this, this kind of question is a great example of why rigour is important in mathematics. I have been out all day so I STILL haven't looked at this properly, but will do so tomorrow and post whatever I can come up with.
 

abcdefghij123

New Member
Joined
Jun 12, 2011
Messages
9
Gender
Male
HSC
2012
Pretty much this, this kind of question is a great example of why rigour is important in mathematics. I have been out all day so I STILL haven't looked at this properly, but will do so tomorrow and post whatever I can come up with.
if your proof is anything like mind, a post online isn't realistic. Even if i was computer savvy it would require too many diagrams and explanations. The approximate process is the following:
1. do what realisenothing did and show that they cannot be arbitrarily close
2. construct a diagram with the two individuals who get shot (say points X and Y in the plane). divide the plane up into areas defined by the following lines:
a) the perpendicular bisector of XY
b) the line through Y perpendicular to XY
c) the line through X perpendicular to XY
(call the area of the plane between lines b) and c) area B, and call the area outside these lines A and A' (effectively the same due to symmetry))
3. from this diagram you can prove the impossibility of the following cases geometrically:
a) all 8 points in A or A' , but none in B
b) 1 point in B, and 7 in A or A' (this is basically the same proof as a) - it is a blatant corollary. I probably shouldnt consider it a separate proof)
c) 2 points in B, and 6 in A or A'
d) 3+ points in B, and 5- points in A or A'
also make sure you consider border cases as well.

for each case you should reach a definitive mathematical/geometrical contradiction/impossibility. don't just settle for: "well it is visually apparent that this particular construct won't work"

have fun :)
 
Last edited:

abcdefghij123

New Member
Joined
Jun 12, 2011
Messages
9
Gender
Male
HSC
2012
mmm. I think my solution is actually shorter than that, however it is more hacky and less 'clean'.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top