Enigma for thought

General
1

Hello, dear Prologians,

Can anyone suggest a solution to the following enigma?

“All stations of Line L sell tickets for all other stations. If a few stations are added, it will be necessary to print 46 additional tickets. What is the exact number of these “few stations” and how many stations were there before?”

Here is a possible hint to begin:

If : Number of types of tickets = x(x-1)

then : Number of types of tickets + 46 = (x+y)(x+y-1)
(y = a few additional stations, then “y” must be a positive integer >= 2)

then : x = 23/y – y/2 + 1/2

…

I would very much appreciate your help in solving this enigma.

2

Do you mean “enigma” or homework?

3

Thank you for your reply. This enigma was recently posted by an engineer who graduated from a school I also once attended. But that was more a quarter of a century ago, and I got all my grades since then. So this surely is not intended as a homework - at best, it might be to check that my grades are still valid.

I thought it might interest some just for the pleasure of it. I do confess that I did not get much beyond my hint.

Best.

4

Another possible hint: OEIS A000217

5

Very interesting. Thank you.

6

I admit I don’t understand the problem statement. Say we have exactly three stops, along a line.

A --- B --- C

How many tickets are we selling now? From where to where? Is it:

A --> B
A --> C
B --> C
B --> A
C --> B
C --> A

or is it something else?

PS: Did you find this on Facebook? How about your friend? The last time I encountered a similar enigma, I got it from my dad, who got it on Facebook. I am only asking because I am keeping notes. I apologize if the question is inappropriate.

7

Dear Mr. Vassilev,

Thank you for your message. I have asked my acquaintance engineer, with whom I occasionally correspond on his blog, the permission to forward to you the article in which he quoted this problem. Moreover, another reader seems to have found a solution in the meantime and I also asked him if I could transmit it to you. I am waiting for their reply and will let you know as soon as I receive them.

With my best regards in the meantime,

André Linden

8

I still don’t know understand the problem statement :frowning: but I guess this ship has sailed now.

9

I am not sure I understand it either because the answer seems to easy once you know about Complete Graphs.

The complete graph on n vertices is denoted by Kn .

If you look at all of the occurrences of the sequence in OEIS A000217 one of them is

Number of edges in complete graph of order n, K_n.

So my take is the number 46 is the difference between two of the numbers, where each number represents the number of stations. The two numbers (n) with the proper difference is 1081 and 1035.

However for a K_n graph the connections have no direction but the tickets have a direction, e.g. from A to B would be one edge and from B to A would be another edge, so the relationship needs to account for this. This is easily handled by noting that for each edge in the K_n graph they would need to be doubled so a relationship of 2 needs to be used for the edges in the calculation.

Here is the table I get

n	 K_n       K_n 
          directed	Diff
0	   0         0	 
1	   1         2	   2
2	   3         6	   4
3	   6        12	   6
4	  10        20	   8
5	  15        30	  10
6	  21        42	  12
7	  28        56	  14
8	  36        72	  16
9	  45        90	  18
10	  55       110	  20
11	  66       132	  22
12	  78       156	  24
13	  91       182	  26
14	 105       210	  28
15	 120       240	  30
16	 136       272	  32
17	 153       306	  34
18	 171       342	  36
19	 190       380	  38
20	 210       420	  40
21	 231       462	  42
22	 253       506	  44
23	 276       552	  46
24	 300       600	  48
25	 325       650	  50
26	 351       702	  52
27	 378       756	  54
28	 406       812	  56
29	 435       870	  58
30	 465       930	  60
31	 496       992	  62
32	 528      1056	  64
33	 561      1122	  66
34	 595      1190	  68
35	 630      1260	  70
36	 666      1332	  72
37	 703      1406	  74
38	 741      1482	  76
39	 780      1560	  78
40	 820      1640	  80
41	 861      1722	  82
42	 903      1806	  84
43	 946      1892	  86
44	 990      1980	  88
45	1035      2070	  90
46	1081      2162	  92
47	1128      2256	  94
48	1176      2352	  96
49	1225      2450	  98
50	1275      2550	 100
51	1326      2652	 102
52	1378      2756	 104
53	1431      2862	 106

Looking at the Diff list we find 46 when there are 23 stations (n), so the number of existing stations before 1 is added is 22.

Also there could be more than one station added in which case the sum of the values in the Diff list need to sum to 46 but also have the constraint that they are consecutive and start at one greater than the number of existing stations, e.g. 22 + 24 = 46 thus the number of existing stations is 10.

10

If you consider the tickets symmetric:

:- use_module(library(clpfd)).

t(0, 0).
t(N, T) :- N #> 0, N1 #= N - 1, T #= N + T1, t(N1, T1).

tickets(N, T) :- N1 #= N - 1, t(N1, TN), T #= TN.

%?- [N, M] ins 0..25, N #> M, tickets(N, TN), tickets(M, TM), TN - TM #= 46.
%@ N = 14,
%@ M = 10,
%@ TN = 91,
%@ TM = 45 .

So, 4 new stations.

If each station sells both directions tickets for all the other stations:

:- use_module(library(clpfd)).

t(0, 0).
t(N, T) :- N #> 0, N1 #= N - 1, T #= N + T1, t(N1, T1).

tickets(N, T) :- N1 #= N - 1, t(N1, TN), T #= 2*TN.

%?- [N, M] ins 0..25, N #> M, tickets(N, TN), tickets(M, TM), TN - TM #= 46.
%@ N = 13,
%@ M = 11,
%@ TN = 156,
%@ TM = 110 ;
%@ N = 24,
%@ M = 23,
%@ TN = 552,
%@ TM = 506 .

So either 2 or 1 new stations are fine, depending on the initial number.

I suspect the sense of the question was the first one.

11

Mr. Vassilev,

I just received permission from the author’s article who quoted the enigma to forward it to you. Here is the link to his blog:

It also includes the comment from the reader who gave his solution to the problem (and from whom I borrowed the hint). This article appeared on the author’s blog in the Swiss-French newspaper Le Temps on September 1 last. If you have any problem with the language, please let me know and I will be happy to help translating the content.

Thank you for your interest and assistance in trying to solve this problem,

André Linden

13

The interesting thing is that based on our interpretation of the problem we both get two solutions and our two solutions are the same.

Solution:
Original number of stations
10 or 22

1 Like
15

Thank you so much for such a clear and prompt solution - in fact, for the two solutions which you found. Do you allow me to convey them to the author of the blog where the enigma was posted and the link of which I gave to Mr. Vassilev? One of the blog’s readers, who was the first to offer a complete solution, already expressed his interest for a logic programming approach to such a problem, which he describes as a challenge (you can easily follow our discussion using the link to the blog which I indicated to Mr. Vassilev - or I can send it again to you, if you wish).

Thank you very much again for your involvement in solving this problem.

A. L.

16

I know you selected to respond to meditans but new users often don’t know there are 2 different reply options. One for the last post and one for the original post.

For my post (EricGT) feel free to share. Unless I note otherwise all the content I post as a user, not as an admin is

Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)

I thought all content posted on the site by default was CC but in checking the Terms of Service that is not the case.

17

Dear EricG,

Thank you very much for your very helpful and precious research. As I already asked meditans with regard to his solutions, do you allow me to convey your findings and your very clear explanations to the author of the blog where the enigma problem was posted? I sent the blog’s link to Mr. Vassilev and could forward it again to you, as well as to meditans, in the event you might wish to follow the discussion there.

André Linden

18

Yes I already have. (ref)

Thanks. I was just interested in knowing if I understood the problem correctly and had the correct answers. Since meditans came up with the same set of answers in a different means I am satisfied that I understood the problem correctly and have derived valid answers.

The main reason I posted my findings was because others might find it of value in understanding the problem. The reason I did not post a Prolog solution is because as I often suggest, it is better to start doing such problems by hand on pen and paper to get a better understanding of the problem then translate that into a model that can be used to solve the problem. Also since I knew of OEIS, I could use that to verify I was generating the set of Kn correctly. If you look at my post edits I actually had a slight typo that I have since corrected. Also OEIS A000217 shows what I believe is a valid connection between your initial equation x = 23/y – y/2 + 1/2 and Kn.

While I do understand the answer by meditans because I knew of the means to solve it soon after the problem was posted, only in working the problem the way I did would I understand what is happening in the solution by meditans. :slightly_smiling_face:

19

You did provide a significant assistance, as asking “What is the number of tickets sold on a line with exactly three stops?” was the right approach, according to the blog participant who found a first solution to the problem. I had the intuitive feeling that this was a graph problem, and EricG’s impressive documentation sheds an equally important light on the issue.

Incidentally, I noticed that I affected your deep slav soul and, if such is the case, I cannot forgive myself because I also happen to belong to the category of people which George Mikes, in his book How To Be An Alien, says that they have the worst kind of soul: the Slavs. So, please let me redeem myself from this unforgivable sin:

Уважаемый господин Васильев,

Хотя я гражданин Швейцарии, мои родители были русскими по происхождению. Я тоже принадлежу к той категории людей, у которых, по словам Джорджа Майка, самая ужасная душа. Особенно это касается логики: я ее не понимаю и не могу объяснить, почему … Вот почему мне нужно логическое программирование.

Большое спасибо за вашу помощь.

Андреи Линден

20

Sure @linden, I usually assume everything I post in a public forum is public, so go ahead.

Thanks for asking though, very polite of you :slight_smile:

22

Thank you very much for your proposal. Here is the full solution offered by one of the readers of the blog where the enigma was posted (I translated it from the original French and hope this will still make sense):

%%
If : Number of tickets = x(x-1)

then : Number of types of tickets + 46 = (x+y)(x+y-1)
(y = a few additional stations, therefore “y” must be a positive integer >= 2)

then : x = 23/y – y/2 + 1/2

Since “x” must be a positive integer >= 2, then the expression (23/y -y/2)*2 must be an uneven positive integer.
(23/y -y/2)*2 = 46/y – y
46 can only be divided by :
1 (but y < 2) ;
2 ;
23 (but 46/23 -23 <0) ;
46 (but 46/46 – 46 <0).

y = 2
%%

24

Yes, they do in SWI-Prolog:

?- [X, Y] ins -1…100, X*(X-1)+46 #= (X+Y)*(X+Y-1),
| label([X,Y]), write(X-Y), nl, fail; true.
11-2
23-1
true.