Not friends on the earth

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Not friends on the earth

Postby balr » Wed Feb 23, 2011 10:27 pm UTC

For the purpose of these puzzles, the Earth is a uniform, smooth, sphere of circumference 40,000km.

Easy to start:

a. Two people who dislike each other very much stand at the North Pole. One moves to be as far away from the other person as they can. How far is that?

Now, the real problems:

b. Three people who each dislike the other two stand at the North Pole. Two move away so that all three of them are as far away from the other two as they can be (i.e. the three distances are equal and maximal). How far is that?

c. Four people who each dislike the other three stand at the North Pole. Three move away so that all four of them are as far away from the other three as they can be (i.e. the six distances are equal and maximal). How far is that?

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Not friends on the earth

Postby balr » Wed Feb 23, 2011 11:18 pm UTC

To clarify a possible misreading: everyone stays on the surface of the earth at all times.

thicknavyrain
ThinkGravyTrain
Posts: 913
Joined: Sun Sep 30, 2007 12:41 pm UTC
Location: The Universe

Re: Not friends on the earth

Postby thicknavyrain » Wed Feb 23, 2011 11:52 pm UTC

Out of curiosity, does this make sense if of the group with three people who dislike the original first two people, one of them intentionally stays at the north pole when there's someone from the first group there? Because that's the scenario painted by what you said. It doesn't create a situation of being maximally away from the first two people. Just saying.
RoadieRich wrote:Thicknavyrain is appointed Nex Artifex, Author of Death of the second FaiD Assassins' Guild.

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Not friends on the earth

Postby phlip » Thu Feb 24, 2011 1:13 am UTC

I think they meant that each one of the group of three hates the other two people from that same group of three... the group being independent of the group of two in the first part.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Not friends on the earth

Postby Qaanol » Thu Feb 24, 2011 1:26 am UTC

As I read it
Spoiler:
We’re just being asked for the arc length (ie. angle times radius) between vertices of a maximal (line/equilateral triangle/tetrahedron) inscribed in a sphere of known radius, along the surface of the sphere. These are of course well-known values.

So the problem generalizes to the “easy case” of finding the angular separation between adjacent vertices of platonic solids, and the “hard case” of doing the same for convex regular polytopes in n-space.
wee free kings

ARandomDude
Posts: 60
Joined: Mon Dec 28, 2009 7:10 pm UTC

Re: Not friends on the earth

Postby ARandomDude » Thu Feb 24, 2011 3:28 am UTC

As far as I know, it's the same idea as molecular shapes.

http://www.sparknotes.com/testprep/book ... ion8.rhtml

Ralp
Posts: 25
Joined: Sat Dec 16, 2006 9:44 am UTC
Location: internet
Contact:

Re: Not friends on the earth

Postby Ralp » Thu Feb 24, 2011 3:33 am UTC

Qaanol wrote:As I read it
Spoiler:
We’re just being asked for the arc length (ie. angle times radius) between vertices of a maximal (line/equilateral triangle/tetrahedron) inscribed in a sphere of known radius, along the surface of the sphere. These are of course well-known values.

So the problem generalizes to the “easy case” of finding the angular separation between adjacent vertices of platonic solids, and the “hard case” of doing the same for convex regular polytopes in n-space.
I agree with this and I don't find this puzzle very interesting. But I am a little curious to know the answer to the next extrapolated case, the configuration of 5 enemies on the sphere.
Spoiler:
I am certain the "equal and maximal" condition can't continue to hold for all pairwise distances (unless maybe in 4+ dimensions? I don't care about that though). And I'm pretty confident that even the distance to the nearest enemy can't be the same for all five, except in strictly sub-optimal arrangements.

Is it just south pole, north pole, and then 3 dudes 120ᵒ apart around the equator? That's boring too if so. The 6 case is just points of an octahedron; does 7 get any more interesting?

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Not friends on the earth

Postby phlip » Thu Feb 24, 2011 3:54 am UTC

Ralp wrote:
Spoiler:
Is it just south pole, north pole, and then 3 dudes 120 apart around the equator? That's boring too if so.

Spoiler:
That, or the 6-point case with one point removed (eg one pole and four equally-spaced on the equator). That way has the nearest-point-is-equal property, too.

The best case for 7 is a bit more interesting, though... it's not simply the best case for 8 with one point removed, I think there's room for improvement from there.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Not friends on the earth

Postby Qaanol » Thu Feb 24, 2011 5:03 am UTC

Another variant would be, “Given N equal classical point-charges, how can they be arranged on a conducting sphere (or other shape—right circular cylinder anyone?) in a (stable?) equilibrium?”
wee free kings

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Not friends on the earth

Postby jestingrabbit » Thu Feb 24, 2011 5:25 am UTC

Qaanol wrote:Another variant would be, “Given N equal classical point-charges, how can they be arranged on a conducting sphere (or other shape—right circular cylinder anyone?) in a (stable?) equilibrium?”


This is very nearly the thomson problem (there the condition is for least energy, whereas you state it as an equilibrium, and there could easily be local equilibria, especially for large numbers of charges).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Not friends on the earth

Postby jaap » Thu Feb 24, 2011 6:47 am UTC

I find the 8 node case the most interesting, since the answer is not what most people's first instinct says it is.
Spoiler:
They are not arranged like the vertices of a cube, ...
Spoiler:
... , but are in fact arranged like the vertices of a square antiprism.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Not friends on the earth

Postby Qaanol » Thu Feb 24, 2011 9:15 am UTC

jaap wrote:I find the 8 node case the most interesting, since the answer is not what most people's first instinct says it is.
Spoiler:
They are not arranged like the vertices of a cube, ...
Spoiler:
... , but are in fact arranged like the vertices of a square antiprism.

Excellent observation.
wee free kings

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Not friends on the earth

Postby balr » Thu Feb 24, 2011 10:17 am UTC

Ralp.....The 2, 3, 4 solutions may not be very interesting, but I do not think there are any solutions for 5 and above.

The original puzzle asks for the distances to be maximal and equal. Your suggested 5 solution has four people around the equator. They are not all the same distance from each other, even though they are all the same distance from the North Pole person.

I am not averse to people relaxing the conditions for a more interesting puzzle; just want to ensure that the original puzzle is not forgotten in the switch to a wider case. Thanks everyone for playing, whichever puzzle you are solving :)

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Not friends on the earth

Postby Ankit1010 » Thu Feb 24, 2011 1:55 pm UTC

Like ARandomDude said, this simply corresponds to the arrangements of atoms in a molecule. They are distributed exactly according to this principle, so that the total distance between each pair is maximized.

3 Corresponds to sp2 hybridization, linear so they are 120 degrees apart on the equator.
5 corresponds to sp3 , so they form a tetrahedron, with one of the vertices at one of the poles.

That also explains why 8 corresponds to the square antiprism.

Equal distances are possible if there is a hybridization scheme which is symmetric.

charonme
Posts: 141
Joined: Sun May 18, 2008 11:18 am UTC

Re: Not friends on the earth

Postby charonme » Sun Mar 06, 2011 1:10 pm UTC

can some of the distances decrease temporarily at some moment during the moving? In other words, only the ending positions are evaluated?

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Not friends on the earth

Postby balr » Sun Mar 06, 2011 8:57 pm UTC

Thanks for asking for clarification.

My unstated assumptions in the original question were for
  • final distance
  • as measured on the surface (ie no tunnelling with tape measures)
So we're looking for final great circle distances.

charonme
Posts: 141
Joined: Sun May 18, 2008 11:18 am UTC

Re: Not friends on the earth

Postby charonme » Mon Mar 07, 2011 6:29 am UTC

So then I guess a better way would be saying "Distribute N points on a sphere surface..." rather than having them all start at the north pole

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Not friends on the earth

Postby balr » Mon Mar 07, 2011 12:24 pm UTC

charonme wrote:So then I guess a better way would be saying "Distribute N points on a sphere surface..." rather than having them all start at the north pole


Puzzles are often characterized by being expressed in a narrative form, and wrapped in a story. Some can be re-cast into a formal mathematical form as a first stage in solving.

What is perhaps interesting about this puzzle is that it has now had nearly two weeks of being reformulated in various ways, but no solutions. So, just possibly, re-casting some puzzles into a formal mathematical form is a dead end that is not conducive to solutions.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Not friends on the earth

Postby jestingrabbit » Mon Mar 07, 2011 5:33 pm UTC

bair, I think people were just holding off from solving because it was pretty straightforward.

Just to be clear,

Spoiler:
For two people, the answer is half the circumference of a great circle. They are always on some great circle together, and when positioned antipodally their distance is maximized.

For three it is one third the circumference of a great circle. There is always a unique plane through the three people, and they are always standing on the circumference of a circle in that plane, namely the cross section of the sphere. The sum of their distances is at most twice the circumference of that circle, so they have to maximize that circumference, so they are on a great circle and the symmetry condition gets you the rest of the way.

The only case that is slightly interesting is where you have 4 people. They're going to be arranged in a tetrahedron, or else they won't satisfy the symmetry condition. I could look up the dimensions of a tetrahedron, or I could calculate the angle... I'll calculate.

wlog, lets have the centre of the earth at (0,0,0) and one of the people is at the north pole with coordinates u=(1,0,0). wlog, another is in the xy plane, and because we're on a sphere, we can require that they're at [imath]v = (\cos\theta , \sin\theta, 0).[/imath] Furthermore, if we let

[math]A = \begin{pmatrix} 1 & 0 & 0 \\ 0& -1/2 & \sqrt{3}/2 \\ 0 & -\sqrt{3}/2 & -1/2 \end{pmatrix}[/math]

then A is a rotation by [imath]2\pi/3[/imath] in the yz plane, and one of the other people are at w = Av. Furthermore, we need [imath]u\cdot v = v\cdot w.[/imath] Plugging in some values,
[math]w = Av = \left( \cos\theta, -\frac{1}{2}\sin\theta, \frac{\sqrt{3}}{2}\sin\theta \right),[/math][imath]u\cdot v = cos\theta[/imath] and [imath]v\cdot w = \cos^2 \theta - \frac{\sin^2\theta}{2}.[/imath]

Therefore,
[math]\begin{align*}\cos\theta &= \cos^2 \theta - \frac{\sin^2\theta}{2} \\
&= \frac{3}{2} \cos^2 \theta - \frac{1}{2} \\
0 &= 3 \cos^2 \theta - 2\cos\theta - 1\\
\cos\theta &= \frac{2 \pm \sqrt{ 4 +12} }{6} \\
\cos\theta &= \frac{-1}{3}\\
\theta &= \arccos(-1/3).\end{align*}[/math]
So the distance is [imath]\arccos(-1/3)/2\pi[/imath] times the circumference. Wikipedia agrees. I'm done... yay.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Tass
Posts: 1909
Joined: Tue Nov 11, 2008 2:21 pm UTC
Location: Niels Bohr Institute, Copenhagen.

Re: Not friends on the earth

Postby Tass » Fri Mar 18, 2011 8:12 am UTC

balr wrote:ie no tunnelling with tape measures.


The great arch distance and the tunneling distance depends monotonely on each other, so this does not change the puzzle.

charonme wrote:can some of the distances decrease temporarily at some moment during the moving?


For the simple cases asked in the OP it does not make a difference. I am unsure if it ever does. If so what is the lowest number for which we can get a stable equilibrium that is not optimal?


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests