Jump to content


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 :-)
Guest Message by DevFuse
 

Photo
- - - - -

The army of ants


Best Answer plasmid, 15 August 2014 - 07:05 AM

Spoiler for not invoking any sort of x-axis
Go to the full post


  • Please log in to reply
9 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5815 posts
  • Gender:Male
  • Location:New York

Posted 11 August 2014 - 03:48 PM

An infinite army of ants comprises soldiers with integer coordinates on the lower half-plane including the x-axis (non-positive values of y.) The army advances upward by jumping over adjacent comrades to unoccupied positions. The y-value of the jumping ant thus increases by 2. The comrade, however, is killed in the process and removed from battle. The effect is like moves in checkers, where the jumped checker is removed, except that the ants may advance vertically as well as diagonally forward. Horizontal jumps are also permitted, but no ant may retreat. To win the war, an ant must reach an enemy stronghold somewhere in the upper half plane. Can the ants advance to arbitrarily large values of y?

 

Example of a jump to the northeast:

                                                       x
------ x x x x x x x x x x ---  x-axis --- x x x x x . x x x x -------
   ... x x x x x x x x x x ...         ... x x x x . x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...
   ... x x x x x x x x x x ...         ... x x x x x x x x x x ...


Edited by bonanova, 12 August 2014 - 03:52 AM.
Show jump

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 82 posts

Posted 14 August 2014 - 04:30 PM

I saw this puzzle in the same Peter Winkler book I mentioned elsewhere.

Spoiler for Here's what I think

  • 0

#3 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5815 posts
  • Gender:Male
  • Location:New York

Posted 14 August 2014 - 09:11 PM

Spoiler for it seems

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#4 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 15 August 2014 - 07:05 AM   Best Answer

Spoiler for not invoking any sort of x-axis

  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5815 posts
  • Gender:Male
  • Location:New York

Posted 15 August 2014 - 08:02 AM

Can we deduce from this an upper limit on y (for the OP)?
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 16 August 2014 - 03:28 AM

Converting my numbering to the type of numbering that would be used in the OP, my answer implies that if ants start off at y=0 and no higher, then they won't be able to reach y=7. It doesn't ensure that they can somehow reach y=6, it just doesn't rule it out as impossible.
  • 0

#7 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5815 posts
  • Gender:Male
  • Location:New York

Posted 16 August 2014 - 02:32 PM

It would be interesting compete with a list of moves that gets to the "highest" y-value.

Earlier solvers disallowing diagonal moves could get only to y=4.

I've played with this but it gets complicated too quickly.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#8 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 17 August 2014 - 05:57 AM

Actually, I overlooked that the OP said the ants can jump straight vertically and straight horizontally as well as diagonally. That makes my omission of ants on the opposite color square as the final goal if the grid is colored like a checkerboard (they can contribute to a solution by being jumped), and my counting of only ants that are within a 90 degree cone of the goal (ants can jump horizontally to enter such a cone and contribute to an answer) invalid.
  • 0

#9 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 18 August 2014 - 03:31 AM

Spoiler for revision

  • 0

#10 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5815 posts
  • Gender:Male
  • Location:New York

Posted 18 August 2014 - 04:31 PM

Spoiler for revision

 

 

That looks right. Nice work. bona_goldstar.gif


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users