6
$\begingroup$

In a remote town where the internet has not yet reached, people use a indigenous telephone to communicate.

Each telephone call occupies the phone to the nearest minute ceiling. So if a call is 15 seconds long, it will be considered a 1 minute call. If it is 3 minute 2 seconds it will be a 4 minute call.

The telephone company charges 1 cent for the first minute, 2 for the second and so on.

One fine Saturday morning at 0900 hours, the Mayor's wife phones two close friends inviting them to an event the coming Monday at 6:00 pm.

The invite is to be forwarded to at least 1 and maximum of 3 other town residents via telephone. Each invite takes the same time in minutes as the invitee number.

Assuming there are no multiple invites the questions are :

1) What would be the minimum time taken to reach 50000 unique residents in the town? How much money would the telephone company have made in this case?

2) How many maximum invites could have been reached in the first three hours?

3) With above conditions What would be the strategy be to reach the maximum but get charged the minimum in the first three hours?

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ By "invitee number" do you mean that Wife = 1, friend1 = 2, friend2 = 3, friend1a = 3, friend1b = 4? $\endgroup$
    – JonTheMon
    Sep 18, 2015 at 16:11
  • 1
    $\begingroup$ So, Wife->F1 = 1 min, F1->F1a = 1, F1a->F1aa=1, etc? $\endgroup$
    – JonTheMon
    Sep 18, 2015 at 16:21
  • 2
    $\begingroup$ Must say I like this puzzle. the more I think about it the more compilcated it gets. Main question would be: when does it pay off to call more than 1 person? And this could vary in terms of cost and time $\endgroup$
    – Ivo
    Sep 18, 2015 at 16:44
  • 2
    $\begingroup$ If my calculations are correct you will reach 230,643,858,099 people in 1 hour when everyone decides to invite 3 others. So that must be a very large town lol, Or I did something wrong with my calculations of course $\endgroup$
    – Ivo
    Sep 18, 2015 at 17:26
  • 1
    $\begingroup$ @IvoBeckers Isn't Q1 easy to solve then. Or am I missing something. $\endgroup$
    – ghosts_in_the_code
    Oct 24, 2015 at 12:02

1 Answer 1

Reset to default
2
$\begingroup$

ghost_in_the_code's comment made me look at this question again and this is what I came up with.

Without looking at the cost it's pretty obvious that the fastest way to reach everyone is for everyone to forward 3 invites.

So let $f(x)$ be the function for the number of invitees that get added after $x$ minutes. It's not hard to see that this is

$f(x) = f(x-1) + f(x-3) + f(x-6)$

Because everyone that was added 1 minute ago can add one, everyone that was invited three minutes ago just finish their second invite and everyone that was invited six minutes ago finished their third invite.

Now we need to determine the base cases.
$f(1)=1$ this is the first invite of the mayor's wife
$f(2)=1$ this is the first invite of the $f(1)$
$f(3)=2$ this is the second invite of the mayor's wife plus the first invite of $f(2)$
$f(4)=3$ this is the second invite of $f(1)$ plus the first invites of $f(3)$
$f(5)=3$ this is the second invite of $f(2)$ plus the first invites of $f(4)$
$f(6)=5$ this is the second invites of $f(3)$ plus the first invites of $f(5)$

Now let $g(x)$ be the number of invites reached after $x$ minutes. This basically is

$g(x) = f(x) + f(x-1) + ... + f(1)$

Now using a computer program i saw that $g(24)=37088$ and $g(25)=57059$ so to partially answer Q1:

Afer 25 minutes 50,000 people can be reached.

To answer Q2 we just take $g(180)$:

After 3 hours 5,705,547,003,706,489,579,067,455,461,663,446 people can be reached.

I think that Q3 is not really clear what your asking. You either want to reach the maximum or you want to be charged the mininum or any step in between. We can determine how to get the cheapest for $X$ people or we can decide how many people we can reach for $X$ cents but you haven't stated that goal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Bravo !!! You got it correct. Q3 asks for the appropriate Tactic from this 'big' data. $\endgroup$
    – kanchirk
    Oct 24, 2015 at 13:55
  • 1
    $\begingroup$ By the way, here is my Java code pastebin.com/m1Zu4e9D $\endgroup$
    – Ivo
    Oct 24, 2015 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.