19
$\begingroup$

You want to put some fish in a square tank. But these fish fight whenever they are in the same tank. Sadly, you have only 1 tank, but you can put glass panes inside the tank to divide it, not necessarily into equal parts. There are some restrictions.

  1. No 2 fish will be in the same area.
  2. Each fish has to see every other fish (They cannot see each other through corners).
  3. The fish can see only through 1 glass pane(So, Only adjacent fish can see each other ignore case of transparency)
  4. Assume the panes can only be placed from the base of the tank and perpendicular to it. (Basically consider only the top 2D view to solve)

What is the maximum number of fish possible?

Some Diagrams for initial cases [Red represents Fish, Blue represents Glass Panes]:

  • 2 fish

    2 Fish

  • 3 fish

    3 fish

  • 4 fish

    4 fish

I came up with this problem while seeing some Siamese fighting fish in my tank.

$\endgroup$
4
  • 1
    $\begingroup$ Since these are (transparent) glass panes, is there anything stopping the fish from seeing other fish across multiple panes? $\endgroup$ Commented Jun 11 at 15:57
  • 1
    $\begingroup$ @BenjaminWang No, They can only see each other through 1 pane. So Only adjacent fish can see each other $\endgroup$
    – NoName
    Commented Jun 11 at 15:59
  • $\begingroup$ The tank has 3 dimensions right, up and down as well as forward, back, left, right? Could you put some panes at different angles or horizontally as well as vertically? It would be difficult to get them food/feed them if they were basically boxed in, but curious if that is an option? $\endgroup$
    – Brad
    Commented Jun 11 at 17:29
  • 1
    $\begingroup$ in 2D, rot13(Qbrfa'g gur sbhe pbybe gurberz nccyl naq fnl jr pnaabg unir zber guna 4 svfu?) $\endgroup$ Commented Jun 11 at 17:33

2 Answers 2

17
$\begingroup$

The maximum number is

four.

Reasoning:

Suppose five areas is possible. Then pick any point in each area and call them the five vertices of a graph. And draw an edge from every vertex to every other vertex along a path where a fish might see another fish. These edges do not intersect because the fish tank is two-dimensional. Then the resulting graph is a complete graph on five vertices, drawn on a plane, which does not exist.

$\endgroup$
6
  • 2
    $\begingroup$ Actually the puzzle doesn't say the tank is 2D anywhere. $\endgroup$
    – qwr
    Commented Jun 11 at 17:02
  • $\begingroup$ @qwr I am sorry if the question was not clear, I completely missed to include your point. $\endgroup$
    – NoName
    Commented Jun 11 at 17:06
  • 1
    $\begingroup$ Interesting. It seems that in 3D there is no upper limit. $\endgroup$ Commented Jun 12 at 0:13
  • $\begingroup$ The association with a planar complete graph is appropos, but it could be made tighter. Represent each section of the tank as a vertex. Represent the barrier between each pair of adjacent sections as an edge. Requirements (2) and (3) are equivalent to requiring this graph to be complete. As you already say, requirement (4) is equivalent to requiring this graph to be planar. $\endgroup$ Commented Jun 12 at 14:39
  • $\begingroup$ Having made that association, there is no need for a proof by contradiction. Taking v as the number of vertices of the graph, completeness requires the number of edges, e, to be (v)(v-1)/2. Euler's formula as applied to planar graphs requires that e ≤ 3 v - 6. A little algebra then gets us this inequality in v alone: v ² - 7 v + 12 ≤ 0. The largest integer (or real number) satisfying that inequality is 4. $\endgroup$ Commented Jun 12 at 14:47
2
$\begingroup$

The maximum number is

4

because the problem you enunciated is equivalent to

the problem of the four-color map, with your restrictions translated in the following way:

point 1= An area can have only one color.

points 2 and 3 = Adjacent areas must have different colors.

point 4 = All of this takes place in a plane.

$\endgroup$
2
  • $\begingroup$ Good day. It is just a coincidence that the answer to "maximum chromatic number of a loopless planar graph" and "maximum planar complete graph" are both 4. It is interesting! Someone else has pondered about this too. By the way don't forget requirement 3: The fish can see only through 1 glass pane(So, Only adjacent fish can see each other ignore case of transparency). $\endgroup$ Commented Jun 12 at 8:59
  • 2
    $\begingroup$ I believe the four-color theorem does imply that the maximum number is not greater than 4 (and with the given examples in the question, it proves it is then exactly for). Assuming a partition of the aquarium works for n>4 fish, you can color this partition with 4 colors, so at least two fish will be colored the same, but this is not possible since they share an edge. $\endgroup$ Commented Jun 13 at 9:35

Your Answer

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

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