## Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

### #1

Posted 27 January 2008 - 12:25 AM

One of them, Alex by name, proposes a new game.

Not surprisingly, it involves a challenge.

Look here fellas, he croaked, as he drew four X's on the

ground so that they formed the four corners of a square.

We all start out on one of these corners. Then we take

turns jumping over each other. The object is to end up

sitting on new spots that form a larger square. The frog

who makes the final jump to form the square is the winner.

Here are the rules:

[1] We can jump another frog from any distance.

[2] We land an equal distance away from the jumped frog: if he's 2 feet away, I land 2 feet beyond him.

[3] Jumps are in a straight line: initial position, jumped frog and landing position are in a straight line.

One of the other frogs, amazingly named Jamey, wondered

why they had to take turns. Maybe I want to think about

my next jump for a bit, I don't want to hold up the game.

OK, then, we'll jump one at a time, but not necessarily in order,

Alex agreed.

Can you prove that it's possible to win the game ... or not?

If so, how many jumps will it take?

*Vidi vici veni.*

### #2

Posted 27 January 2008 - 02:37 AM

### #3

Posted 27 January 2008 - 09:57 AM

### #4

Posted 28 January 2008 - 11:15 AM

### #5

Posted 29 January 2008 - 03:40 AM

My guess is that it is impossible, i have tests this week, but if i've got time upcoming weekend i'll try to prove it using math (or write a program which tries an x number of steps and leave that running for an hour or so, though that isn't a proof it is safe to say that there 'll probably not be a solution if it isn't found then).

I agree that it's probably impossible, and since it's posted by bonanova there's no doubt an elegant way to prove it. Still, a programmatic test sounded fun. My first attempt used random selection and went deep, but I figured that was unlikely to succeed so this morning I modified it to use a brute force approach. With 12*11^(n -1) possibilities for each jump (I ruled out having a frog immediately jump back to his previous position), it doesn't take long to run into computing limitations. So far, however, I can say with a fair amount of certainty, barring a bug in my code, that there is not a solution in under 10 jumps.

### #6

Posted 29 January 2008 - 04:04 AM

The frogs will eat any bugs.I agree that it's probably impossible, and since it's posted by bonanova there's no doubt an elegant way to prove it. Still, a programmatic test sounded fun. My first attempt used random selection and went deep, but I figured that was unlikely to succeed so this morning I modified it to use a brute force approach. With 12*11^(n -1) possibilities for each jump (I ruled out having a frog immediately jump back to his previous position), it doesn't take long to run into computing limitations. So far, however, I can say with a fair amount of certainty, barring a bug in my code, that there is not a solution in under 10 jumps.

Your code must include a fairly tight test for "squareness".

Care to share that part of it?

I ran across a question that asked how efficiently that test could be implemented.

*Vidi vici veni.*

### #7

Posted 29 January 2008 - 05:46 AM

Your code must include a fairly tight test for "squareness".

Care to share that part of it?

I ran across a question that asked how efficiently that test could be implemented.

That did prove a bit more challenging than I expected. My test certainly ain't "tight," but I think it's workable. I would be happy to have it inspected by all y'all mathy people:

Here's the theory:

1. For each frog, get the distance to the other three frogs.

2. Get the max and min distances.

3. If all four frogs share the same max and min distances, they must form a square. (an unproven supposition, but I believe it should hold)

[C#]bool IsLargerSquare(){ List<double> lengths = new List<double>(); double firstMax = 0; double firstMin = 0; for (int i = 0; i < 4; i++) { lengths.Clear(); lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 1) % 4)].Pos)); lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 2) % 4)].Pos)); lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 3) % 4)].Pos)); double max = Math.Round(MaxInList(lengths), PRECISION); double min = Math.Round(MinInList(lengths), PRECISION); if (i == 0) // max/min of first frog { firstMax = max; firstMin = min; } else // other frogs. compare to original max/min { if (firstMax != max) return false; if (firstMin != min) return false; } } if (firstMin > 1) return true; // make sure it's larger than the original square else return false;}

### #8

Posted 29 January 2008 - 08:48 AM

In only one case [square] do the points individually have the same max and min.

So I think you're condition is correct.

Look at post #6 here

Look at post #15 [and others] here, also

*Vidi vici veni.*

### #9

Posted 30 January 2008 - 12:17 PM

*Vidi vici veni.*

### #10

Posted 31 January 2008 - 02:46 PM

After looking at those other forums I decided to revisit the square-checking algorithm. Although my updated solution still uses a lot of steps (and appears to require just as much code as my previous proposal), it is actually drastically more efficient, and I don't see how to optimize it much more using only high level code. Of course I'd love suggestions.

Here's the theory:

1. The x and y differences between any point and any two adjacent points are inverses with a perpendicular slope. For example: (1,2) and (-2,1), (1,2) and (2,-1), (0,1) and (1,0).

2. The x and y differences between any adjacent point and the opposite point must match the differences between the first point and the other adjacent point.

3. If those conditions are met ... it's a square!

That's it. No multiplication, division, or square roots needed other than to verify that a found square is actually larger than the original. Also, I learned a few things from my first attempt:

1. All values will be integers, so no floating point math is required.

2. We only need to examine two jumps of the 12 possible from the original position, since everything else is just symmetry.

3. The actual formula for the total possibilities is 2 + 2(11 + 11^2 + 11^3 ... 11^n-1) where n is the depth (i.e., number of jumps).

Using this approach my test evaluates 3.5 million jumps/sec. Unfortunately, that only yielded about one more ply to the testable depth. If I run it overnight, I will still only be able to examine 11 or perhaps 12 jumps deep. Of course, I could find ways to reduce the evaluation of the insane numbers of symmetrical positions, but that would just be OCD in action.

So, while I am fairly certain it's impossible, I naturally wanted a simpler expanation, so I applied what I had just learned ...

Simple enough, but I'm sure even that can be reduced.

Just for fun, I present to you the code ...

[codebox] class FrogSim

{

const int MAX_DEPTH = 9;

const int SLOPE_NEG = -2;

const int SLOPE_ZERO = -1;

const int SLOPE_ONE = 1;

const int SLOPE_POS = 2;

int result = 0;

long tested = 0;

FrogList frogs;

public FrogSim()

{

// setup

frogs = new FrogList();

frogs.Add(new Frog(new Point(0, 0)));

frogs.Add(new Frog(new Point(1, 0)));

frogs.Add(new Frog(new Point(0, 1)));

frogs.Add(new Frog(new Point(1, 1)));

}

public void RunSim()

{

DateTime start = DateTime.Now;

bool success = false;

// recursively call jump for only 2 jumps at base level

if (Jump(0, 1, 1)) success = true; // jump 1 and ...

else if (Jump(0, 3, 1)) success = true; // jump 3. those are the only two necessary tests due to symmetry

// get total time

TimeSpan duration = DateTime.Now.Subtract(start);

string timeMessage = "\n\nTotal time: " + (int)duration.TotalSeconds + " seconds.";

string message;

if (success)

{

message = "Formed a larger square in " + result.ToString() + " jumps!" + timeMessage;

}

else

{

message = "Failed to achieve a square in " + MAX_DEPTH + " jumps.\n" +

"Attempted " + tested.ToString() + " possibilities." + timeMessage;

}

Debug.WriteLine(message);

MessageBox.Show(message);

}

bool Jump(int jumper, int jumped, int depth)

{

tested++;

int iLastJumper = jumper;

int iLastJumped = jumped;

Point startingPos = frogs[jumper].Pos;

frogs[jumper].Jump(frogs[jumped]);

if (IsLargerSquare())

{

result = depth;

return true;

}

else

{

if (depth < MAX_DEPTH)

{

for (int iJumper = 0; iJumper < 4; iJumper++)

{

for (int iOffset = 1; iOffset < 4; iOffset++)

{

int iJumped = (iJumper + iOffset) % 4;

if (! (iJumper == iLastJumper && iJumped == iLastJumped))

{

if (Jump(iJumper, iJumped, depth + 1))

{

return true;

}

}

}

}

}

}

// restore the previous position

frogs[jumper].Pos = startingPos;

return false;

}

bool IsLargerSquare()

{

// get x/y differences from first point to two other points

int x1 = frogs[1].Pos.X - frogs[0].Pos.X;

int y1 = frogs[1].Pos.Y - frogs[0].Pos.Y;

int x2 = frogs[2].Pos.X - frogs[0].Pos.X;

int y2 = frogs[2].Pos.Y - frogs[0].Pos.Y;

// get their absolute values

int absX1 = Math.Abs(x1);

int absY1 = Math.Abs(y1);

int absX2 = Math.Abs(x2);

int absY2 = Math.Abs(y2);

// get their relative slope (negative, positive, zero, or one)

int slope1 = GetSlope(x1,y1);

int slope2 = GetSlope(x2, y2);

if (absX1 == absY2 && absY1 == absX2 && slope1 == -slope2)

{

// 1 and 2 are adjacent. frog 3 is distant (compare to 1)

return IsValidOppositePoint(frogs[3].Pos, frogs[1].Pos, x2, y2) && IsLarger(x1, y1);

}

// get diffs to third point only if first two were not adjacent

int x3 = frogs[3].Pos.X - frogs[0].Pos.X;

int y3 = frogs[3].Pos.Y - frogs[0].Pos.Y;

int absX3 = Math.Abs(x3);

int absY3 = Math.Abs(y3);

int slope3 = GetSlope(x3, y3);

if (absX1 == absY3 && absY1 == absX3 && slope1 == -slope3)

{

// frog 2 is distant (compare to 1)

return IsValidOppositePoint(frogs[2].Pos, frogs[1].Pos, x3, y3) && IsLarger(x1, y1);

}

else if (absX2 == absY3 && absY2 == absX3 && slope2 == -slope3)

{

// frog 1 is distant (compare to 2)

return IsValidOppositePoint(frogs[1].Pos, frogs[2].Pos, x3, y3) && IsLarger(x1, y1);

}

return false;

}

int GetSlope(int x, int y)

{

if (x == 0)

{

return SLOPE_ONE;

}

else if (y == 0)

{

return SLOPE_ZERO;

}

else if (x > 0 == y > 0)

return SLOPE_POS;

else

{

return SLOPE_NEG;

}

}

bool IsValidOppositePoint(Point ptOpp, Point ptAdj, int xDiff, int yDiff)

{

int x4 = ptOpp.X - ptAdj.X;

int y4 = ptOpp.Y - ptAdj.Y;

return (x4 == xDiff && y4 == yDiff);

}

bool IsLarger(int xDiff, int yDiff)

{

return Math.Sqrt((xDiff * xDiff) + (yDiff * yDiff)) > 1;

}

}

class Frog

{

public Point Pos;

public Frog(Point startingPosition)

{

Pos = startingPosition;

}

public void Jump(Frog jumpee)

{

Pos = new Point(((jumpee.Pos.X - Pos.X) * 2) + Pos.X, ((jumpee.Pos.Y - Pos.Y) * 2) + Pos.Y);

}

public override string ToString()

{

return Pos.ToString();

}

}

class FrogList : List<Frog>

{

public override string ToString()

{

string sFrogs = "";

foreach (Frog frog in this)

{

sFrogs += frog.ToString() + "\n";

}

return sFrogs;

}

}[/codebox]

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users