Tuesday Puzzle

Re: Tuesday Puzzle

If I am reading this right, there may be more than one solution.

Can we assume that:

The tickets are strictly point-to-point. (i.e. a ticket bought at Station A to Station C is different from a ticket bought at Station B to station C);

The tickets are directional(i.e. a ticket bought at station A to Station B is different than a ticket bought at station B to station A)?

yes to both

I made those assumptions

And concluded that your question included part of the answer.

I guess they no longer call this the prime line?

Re: I made those assumptions

I was thinking in terms of graphs, not primes.

Now that we have established that the problem can be modeled as a complete digraph, the answer is left as an exercise to the reader. ;-)

If I get some time later today I'll look into the multiple solutions angle.

Re: I made those assumptions

Thinking a little more about this, I see two solutions, the one I ws thinking of earlier and one where you add twice as many new stops, and leave this as a prime line.

Simple algebra often corrects holes in my reasoning!

To the man who only has a hammer...

... the whole world looks like a nail.

I see this as a graph-theory problem. I'd be interested to see your 'prime' approach to it.

For each pair of stations A & B, there are two kinds of tickets: A->B and B->A. Representing the system as a complete digraph with stations as nodes and tickets as edges, we can deduce the following for a system with n stations:

* You will need n(n-1) kinds of tickets to handle all possible trips.

* Adding one station will require 2n new tickets.

* Adding m stations will require m(m-1) + 2mn new tickets.

Given the 46 additional ticket types in the problem, I see two solutions:

With n=23 and m=1, we will require 2*23 = 46 new tickets.

With n=11 and m=2, we need 2(2-1) + 2*2*11 = 2+44 = 46 new tickets.

Re: To the man who only has a hammer...

I think we saw it essentially the same way. My solution had nothing to do with primes -- I was just noting that the answers did (starting with 23 stations or going from 11 to 13 stations).

I approached it two [obviously equivalent] ways:

Delta: If you have N stations and add one, you are going to have to print one ticket from each of the prior N stations to the new one and one ticket from the new one to each of the N prior stations. So the number of new tickets is 2N. Obviously, add one more station and you are going to add 2*(N+1) more. So we are looking for 2*(N+(N+1)+...) = 46, or N+(N+1)+... = 23, which experimentation shows has a solution only at N = 11,23.

Total number of tickets approach: You start off with n stations, each of which has tickets to the other n-1 stations, or n*(n-1) tickets.

Add k stations, and you will now have (n+k)*(n+k-1) tickets. So we have:

(n+k)*(n+k-1) - n*(n-1) = 46

n^2 + 2nk + k^2 - n - k - (n^2 -n) = 46

2nk + k^2 -k =46

k *(2n + k - 1) = 46

The only factors of 46 are 1,2,23,and 46, and only 1 and 2 work for k (with the reasonable assumption that the subway system didn't start with a negative number of stations!)

;-) for both.