Triangle of Safety

Question

Saitama: "The Hero Association called me for a low-level mission, can you meet them as my representative?"
Genos: "No."
Saitama: "Aww, man.. That's not fun."
Then Saitama decided to meet Hero Association.

---

The world of One Punch Man consists of exactly 25 cities labeled $A$ to $Y$ (there used to be a city labeled $Z$, but it is abandoned and we will not use it in this puzzle). Each pair of cities are connected by a road hence there are 300 roads in total. Hero Association wants Saitama to plan a patrolling strategy.

There are 100 heroes (a.k.a riders) that will cycle their bike to patrol along their planned route each night. To make it happened, Hero Association wants to make 100 Triangle of Safety. Triangle of Safety is defined as a set of 3 different cities which has a road connecting each pair of them, i.e. a cycle of 3 cities, which will be a route for a patrolling rider. Obviously, these 100 Triangle of Safety must cover all roads.

This mission is, of course, really boring for Saitama. Can you help him to determine one of the possible configuration for 100 Triangle of Safety, or prove that it is an impossible mission?

---

_{^{This puzzle is based on a competitive programming problem authored by me. It is used in Indonesia National Contest 2017, a qualification round of The ACM International Collegiate Programming Contest (ICPC) Asia Jakarta 2017. The link of the problem is here.}}

Answer 1

Okay, I believe that it:

is possible

First:

Pretend all the cities are around in a circle, equidistant from their neighbours

Then we will:

Create 4 sets of 25 triangles with all 12 edge lengths, so that we can rotate each triangle around into the 25 possible positions for one particular orientation

This will:

Make a set of 100 triangles which covers each road exactly once

Namely, the sets are:

(a/b represents the arc lengths counting either way around the circle)
1/24, 3/22, 4/21
2/23, 8/17, 10/15
5/20, 9/16, 11/14
6/19, 7/18, 12/13

Demonstration:

In the below image, the shorter arc length s is selected for the label d_s. One of the 25 triangles generated from each line is shown, in the order orange, blue, green, red.

Answer 2

Well, since this was originally from an ICPC style competition, I'll give an ICPC style answer (apologies to whoever finds this unsatisfactory) that the task is

possible

Explanation:

I made a program that just swaps numbers around until the triples satisfy the criteria given. These are the triples my program generated:

[[22, 4, 7], [21, 14, 13], [7, 15, 11], [3, 9, 6], [1, 24, 20], [3, 20, 5], [1, 16, 22], [4, 14, 3], [10, 7, 23], [20, 17, 22], [11, 0, 9], [8, 2, 17], [4, 20, 23], [10, 13, 12], [14, 10, 16], [9, 5, 10], [7, 18, 1], [7, 24, 17], [8, 15, 14], [20, 18, 10], [17, 11, 4], [12, 21, 22], [16, 5, 21], [13, 23, 16], [7, 5, 14], [14, 19, 0], [21, 23, 1], [20, 8, 13], [24, 0, 16], [9, 24, 21], [16, 6, 17], [3, 11, 13], [8, 5, 23], [23, 19, 11], [17, 10, 15], [13, 6, 1], [5, 6, 22], [11, 14, 18], [0, 12, 18], [0, 13, 7], [8, 3, 0], [21, 8, 10], [4, 12, 15], [24, 18, 8], [12, 6, 8], [18, 4, 6], [1, 10, 0], [24, 15, 6], [11, 12, 16], [19, 13, 2], [12, 24, 23], [15, 3, 16], [7, 19, 9], [22, 24, 14], [17, 9, 13], [7, 3, 21], [1, 17, 14], [4, 2, 16], [20, 0, 6], [0, 21, 4], [14, 2, 20], [10, 19, 4], [22, 3, 10], [11, 24, 5], [6, 23, 14], [2, 23, 0], [18, 16, 9], [22, 9, 23], [7, 12, 20], [6, 2, 7], [12, 1, 3], [2, 21, 15], [12, 17, 19], [2, 3, 18], [6, 10, 11], [2, 5, 12], [15, 23, 18], [8, 4, 9], [8, 7, 16], [4, 5, 1], [24, 10, 2], [12, 9, 14], [19, 22, 8], [22, 13, 18], [21, 18, 17], [20, 11, 21], [20, 15, 9], [5, 17, 0], [5, 15, 13], [1, 8, 11], [0, 22, 15], [19, 21, 6], [24, 3, 19], [16, 19, 20], [2, 22, 11], [15, 1, 19], [1, 2, 9], [19, 18, 5], [4, 24, 13], [17, 3, 23]]

For a more mathy answer:

The "100 Triangles of Safety" are actually known as a Steiner triple system.

These systems are known to exist for any positive integer of the form $6n+1$ or $6n+3$, and there are several constructions known, for instance the Skolem construction (I don't find any of them particularly intuitive, though. If I do find one that is easy to explain I might edit it in here).