Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help these poor little frogs!

  1. Oct 7, 2005 #1
    A small stream has seven equidistant stones in line from one bank to the other. Three black and three white frogs on either side are sitting on the three nearest stones to their respective banks like so: B B B _ W W W with one stone unoccupied in the middle. Can you help both group of frogs to cross to the other side if (a) A frog can only shift to a stone ahead of it or can jump over an opposite colour frog; (b) No frog can move backward or into the water and one stone cannot accommodate more than one frog at a time. The real challenge however is: can you device a strategy for m black and n white frogs (with the assumption that there are m + n + 1 stones laid across) in a similar situation? Can you also come up with a formula for minimum no of steps required?
     
  2. jcsd
  3. Oct 7, 2005 #2
    Answer for the 3B-3W problem (in white)

    BBB_WWW 0
    BBBW_WW 1
    BB_WBWW 2
    B_BWBWW 3
    BWB_BWW 4
    BWBWB_W 5
    BWBWBW_ 6
    BWBW_WB 7
    BW_WBWB 8
    _WBWBWB 9
    W_BWBWB 10
    WWB_BWB 11
    WWBWB_B 12
    WWBW_BB 13
    WW_WBBB 14
    WWW_BBB 15

    15 steps. Note the symmetry between step n and step 15 - n.
     
  4. Oct 7, 2005 #3
    Supposedly, this solution has been seen used by mountain goats when two groups approach each other on a ledge only one goat wide. They must have been trained in goat school when they were young.
    The rules for all goats (or frogs):
    1)Stand and wait if Tail in front of you walks to a Nose pointed towards you.
    2)When Nose to Nose, jump over it when space behind it is ready, but stand and wait if they jump over you first.
    3)When Tail jumps over nose ahead walk forward to Nose and wait.
    4)When no more Noses face you, follow Tail of leader as normal.

    BxW for number of jump steps
    B+W for number of walk up steps
    Total steps = (B+W) + BxW

    Passing begins when one leader steps forward Nose to Nose with oncoming leader.
     
  5. Oct 7, 2005 #4

    ranger

    User Avatar
    Gold Member

    May I ask why everyone keeps posting their answers in white :confused:
     
  6. Oct 8, 2005 #5
    So that people who don't want to read the answer can more easily avoid doing so.
     
  7. Oct 8, 2005 #6

    ranger

    User Avatar
    Gold Member

    Makes perfect sense when you put it that way. Thanks for clearing that up.
     
  8. Oct 15, 2005 #7
  9. Oct 26, 2005 #8
    Never mind.


    Galaxy....... :confused:
     
    Last edited: Oct 26, 2005
  10. Oct 27, 2005 #9

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    The set of rules given for the solution is really hard to implement because they're from the perspective of each frog (which would be fine for goats). Personally, I prefer this 3rd person pespective:

    Code (Text):
    while not done:
      For each original group of frogs:
        For each frog in the group, from front to back:
          if canJump:
            jump
          else if canWalk:
            walk
            break //from the 'each frog' loop
     
    Easy as pie.
     
  11. Oct 28, 2005 #10
    A fly in the pie!
    As a group taking the left side 1st frog cannot jump, so it walks.
    Then second frog cannot jump but since there is now room to walk, it walks.
    Same for third – and now they are stuck.

    Unless you get one the frogs to eat this fly we’ll have to consider this code has a bug in it.
     
  12. Oct 30, 2005 #11

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    I think you're missing the very important "break" statement, which is equivalent to "go back to the other group when you walk a frog"
     
  13. Oct 31, 2005 #12
    Ok I see that in the format now.
    But where is the command to get it out of the loop telling the lead frogs alternately walk up the bank on either side to infinity.
    No jump commands given to frogs 2 or 3, while walk commands sent leaders going up the bank.
    CODE cannot assume "walk" onto a rock is different than "walk" onto or up the bank is different until you code it.
    Still a fly in the pie.
     
  14. Oct 31, 2005 #13

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    Uh, the 'universe' doesn't include a bank in this case. It only has to do with the rock crossing. The problem is trivial after that so why would I write code for it? No one bothered showing the frogs leaving the rocks in their solutions.
     
  15. Oct 31, 2005 #14
    Your right, assuming a closed universe, without 'one bank to the other'; your choice of code works fine for third person rules
    Except the first person rules you didn’t care for; it left them following leader on as normal. The individual rules do work better for wild goats since they had to work out the problem for real, without a third person supervisor. Actually caught on film for some nature show a while back.
     
  16. Nov 2, 2005 #15
    I cant get it any simpler than:
    m*n + n/2*(n+3) + m/2*(m+3)
    for the minimum (and maximum :)) possible number of movements.

    Derivation:

    say m+n+1=t

    there are m*n jumps so we must end up removing m*n from the total number of stones traversed.

    t+(t-1)+(t-2)...(t-(n-1)) b frog moves
    t+(t-1)+(t-2)...(t-(m-1)) w frog moves

    n*t+ (-1-2-3...-(n-1)) brining out t
    n*t+ ((n-1)/2 * (-1-(n-1))
    n*t+ ((n-1)/2 * (1-n-1))
    n*t+ ((n-1)/2 * (-n))
    n* (t - (n-1)/2) factoring out n
    n* (n+m+1 +(-n+1)/2) replacing t with n+m+1
    n* (2m+2n+2-n+1) /2
    n* (2m+n+3) /2

    same will apply for the w frogs with m and n reversed. thus,
    all things considered:

    n* (2m+n+3) /2 + m* (2n+m+3) /2 - m*n
    m*n + n^2/2 + 3n/2 + n*m + m^2/2 + 3m/2 -m*n
    m*n + n/2*(n+3) + m/2*(m+3)
     
    Last edited: Nov 2, 2005
  17. Nov 3, 2005 #16
    Even simpler to double check
    Using link from post #7 setting m=n=3
    Your formulas above; jumps = 9 walks =18 total=27
    Formulas from post #3; jumps = 9 walks =6 total=15
    Actual test run at link site gives 15
    Pays to double check

    you must have been counting the steps getting out to the starting position
     
  18. Nov 5, 2005 #17
    I'm mearly counting the number of moves (steps) to get all the frogs off of all the stones. (Which indeed yields the same number of steps getting out to the start if you were to leave the frogs on the stones.)

    If I were to solve it as you did:
    I would start with the fact that each frog must traverse z+1 stones where z is the number of frogs of the opposite color. Thus we have w*(b+1) + b*(w+1) traversions. We still have w*b jumps so:
    w*(b+1) + b*(w+1) - b*w
    wb+w+wb+b -wb
    w+b+w*b
    :)
     
    Last edited: Nov 5, 2005
  19. Nov 5, 2005 #18
    You mean as the original problem was given; where "either side" was defined as "the three nearest stones to their respective banks".

    If you want to redefine either side as "on the banks" and solve as you tried you'd need about 39 steps anyway.
     
  20. Nov 5, 2005 #19
    My interest in a problem has nothing to do with anything that's "given" but what is more thought provoking. When I wrote "If I had solved it as you had" I had already infered that that was how it was originally given, I just didn't care to check. The way I originally solved the problem was by starting all the frogs on the stones in the given configuration, and getting them all off.

    I have checked my solution for several different values of m and n.

    I do realise now, though, that my mistake was in not specifying exactly what I was solving.
     
    Last edited: Nov 5, 2005
  21. Nov 7, 2005 #20
    A small stream has seven equidistant stones in line from one bank to the other. Three black and three white frogs on either side are sitting on the three nearest stones to their respective banks like so: B B B _ W W W with one stone unoccupied in the middle. Can you help both group of frogs to cross to the other side if (a) A frog can only shift to a stone ahead of it or can jump over an opposite colour frog; (b) No frog can move backward or into the water and one stone cannot accommodate more than one frog at a time. The real challenge however is: can you device a strategy for m black and n white frogs (with the assumption that there are m + n + 1 stones laid across) in a similar situation? Can you also come up with a formula for minimum no of steps required?
    well, it's more or less a game of complex leapfrog. Answer's in white font below.

    1:MMM_NNN
    2: MMMN_NN
    3: MM_NMNN
    4: MMN_MNN
    5: M_NMMNN
    6:MN_MMNN
    7: MNM_MNN
    8: MNMNM_N
    9: MNMNMN_
    10: MNMN_NM
    11: MN_NMNM
    12: _NMNMNM
    13: N_MNMNM
    14: NNM_MNM
    15: NNMM_NM
    16: NNMMN_M
    17: NNM_NMM
    18: N_MNNMM
    19:NNM_NMM
    20: NNMN_MM
    21: NN_NMMM
    22:NNN_MMM
     
    Last edited: Nov 7, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help these poor little frogs!
Loading...