4

I want to share a problem on a facebook group : https://www.facebook.com/groups/419858384791916/permalink/640398286071257/

99 people, numbered 2 to 100, are all on one side of a river and wish to reach the other side. There is a single boat with infinite capacity, but a group of people can only ride the boat together if every pair of people on the boat have numbers that are relatively prime. How many back-and-forth trips are needed to transport every person across the river?

kong
  • 595
  • 1
    Hint: Think about how to transport the people with even numbers. – Mark Bennet Jan 12 '15 at 11:03
  • 1
    Query: does there have to be a person in the boat on every trip (i.e. return journey), or is there a captain who does that? – Mark Bennet Jan 12 '15 at 11:05
  • If there is no person that return in the boat, I think the solution is $49$. Why? See @Mark Bennet's hint. :) – Alex Silva Jan 12 '15 at 11:17
  • @AlexSilva Note - if you think correctly about the problem you will see that there are a number of people who could act as "captain" and stay in the boat all the time until the last journey. I think we also need some clarity about what a "back-and-forth" trip is, because the crossings come in pairs until the last crossing (or the first crossing could be the spare one) - how do we count the spare. – Mark Bennet Jan 12 '15 at 11:25

1 Answers1

2

  1. See, that $97$ (or any prime number greater than $50$) is relatively prime with all other numbers. Make number $97$ a captain - it can travel with any number.

  2. See, that two even numbers can't travel together. There is then need for at least $50$ trips.

  3. See, that for every even $2k\geq 2$, $2k$ and $2k+1$ are relatively prime.

  4. For every even number $2k$ (except $96$ and $100$), $2k, 2k+1, 97$ travels to the other side, $97$ comes back - $48$ two way trips.

  5. $96$ and $97$ travels to the other side, $97$ travels back - $1$ two-way trip

  6. $100$ and $97$ travels to the other side - $1$ one-way trip

We have then $49$ two-ways trips and $1$ one-way trip.

Jaroslaw Matlak
  • 4,895