26
$\begingroup$

A few days ago, a peer jokingly posed a puzzle. In essence, the puzzle states that there are some cats, each cat is in a corner, and each cat sees 3 other cats. The puzzle then asks how many cats there are in total. The obvious solution is that there are $4$ cats... However, I have long thought about extensions of the problem. I have found polyhedra that allow for $2n$ "cats", where $n$ is an integer, the "cats" are the vertices, and the edges serve as "hallways" through which cats can see each other.

This naturally made me curious if the problem is possible with an odd number of vertices. I immediately tried to attack the problem and could not solve it... I even failed to attack a restricted form of the problem, requiring a convex polyhedron with an odd number of vertices with each vertex having 3 connected edges. An example of a failing example would be a square pyramid (as one of the vertices has $4$ edges). However, this definition actually discounts the puzzle's intended solution... If we use my "hallway" interpretation of the problem then the "hallways" between cats in opposite corners form an "X" in the center of the square, creating an additional vertex with four connected edges.

Realizing how much harder I had made the puzzle, I decided to pursue the restricted case in two dimensions (which the intended solution lies in). Though I conjecture that an odd number of "cats" is impossible in both two and three dimensions, I thought it would be easier to show in two dimensions, especially for closed, planar graphs. However, I have come up short with a proof here as well.

I realize that my language here is very vague... I lack a decent introduction into topology, and thus my language is incomplete. Should more details be needed I would be glad to elaborate. Nevertheless, I think the most basic form of my question is as such: does there exist a generalization of the cat puzzle to odd numbers of cats in two dimensions? In three dimensions? I conjecture this impossible.

$\endgroup$
  • 14
    $\begingroup$ Are blind cats allowed? $\endgroup$ – wim Oct 3 '16 at 16:48
  • 1
    $\begingroup$ @wim at the start of the puzzle? No. Upon sitting there all day and not coming up with a solution for odd numbers of cats? Every cat has had its eyes torn out XD in all seriousness, no. Other than the "hallways" (which was a simple way for me to take a subset of the problem which I correctly presumed graph theory would have a proof of) I want to keep the problem as true to the riddle as possible. Given, that begs the question of what defines a corner (even if it's just right angles, there is a solution for even cats, so no problem there), how many dimensions do the cats live in, and so forth. $\endgroup$ – Brevan Ellefsen Oct 3 '16 at 18:58
  • 1
    $\begingroup$ I think you have assumed two additional conditions, but you should make them explicit: (1) all "corners" are convex angles and all convex angles are corners, and (2) each corner has a cat (you have only specified that all cats are in corners). $\endgroup$ – A. I. Breveleri Oct 4 '16 at 11:45
  • $\begingroup$ This is my new favorite math puzzle. It has such a concise and elegant proof, but recognizing that the handshake lemma applies requires one very beautiful and challenging step. $\endgroup$ – Kevin Oct 4 '16 at 18:46
  • $\begingroup$ I don't quite get a problem. Isn't a triangle room a 2-D case of a puzzle with an odd numer of cats...? $\endgroup$ – CiaPan Oct 5 '16 at 6:32
26
$\begingroup$

If we assume that "can see" is symmetric (no one-way mirrors, no cats prevented from turning their heads accordingly, etc.), then the situation describes a graph with $n$ vertices (the cats) and a number $e$ of edges, where each vertex has degree $3$. By the hand-shaking lemma, i.e., by counting the vertex-edge-incidences in two different ways. we find $3n=2e$, hence $n$ must be even.

$\endgroup$
  • $\begingroup$ I really like your answer. However, it begs the question: is there a way to account for solutions such as the one intended to be the solution to the puzzle (referring to four cats in the four corners of a room). In this case you can either view there are being only two edges per cat or there being a point of intersection in the middle of the room (caused by the X shape formed from cats in opposite corners). If you were to extrude this you would get a square pyramid which I did explicitly say I was excluding from my restricted form of the problem (which you beautifully explain!) but... $\endgroup$ – Brevan Ellefsen Oct 3 '16 at 18:53
  • 6
    $\begingroup$ If the cats at the corners of, say, a square can all see each other, then their visibility relation corresponds to the complete graph on four vertices - which is the skeleton of a tetrahedron, and definitely has four vertices and six edges (not five vertices and eight edges). The fact that we've decided to "flatten" the graph down from three dimensions to two does not make the point where the diagonals overlap into a true vertex, nor does it artificially break the diagonals into halves. $\endgroup$ – Robin Saunders Oct 4 '16 at 1:34
  • 4
    $\begingroup$ @BrevanEllefsen Whatever additional geometric restrictions you want to apply - all I imposed was that A can see B implies B can see A. $\endgroup$ – Hagen von Eitzen Oct 4 '16 at 14:43
  • 1
    $\begingroup$ @BrevanEllefsen As David said, a graph is "really" just the information about which vertices are connected to which. Choices about how the graph is "embedded" as points and lines in an ordinary geometric space are incidental (unless we've explicitly said that we're interested in that). As a Londoner, the most immediate practical example that comes to mind is the Tube map. There, some lines cross without intersecting. In reality, one line passes over the other. This is because the graph is not planar: it can't be embedded in a plane - such as the map itself - without crossings. $\endgroup$ – Robin Saunders Oct 4 '16 at 16:00
  • 1
    $\begingroup$ But, as with the cats, the graph really represents something more abstract: which stations (cats) are connected (visible) to which others. The fact that the graph can't be physically embedded in the plane without crossings is a distraction. $\endgroup$ – Robin Saunders Oct 4 '16 at 16:00
51
$\begingroup$

You can't have an odd number of cats, not because of geometry, but something more fundamental: the handshaking lemma. Basically, if two cats seeing each other is mutual, then the number of cats that see an odd number of other cats must be even.

$\endgroup$
  • $\begingroup$ Wonderful and concise answer. Nevertheless, this begs the question: since requiring three edges per vertex invalidates the intended solution to the problem, are there any solutions with odd numbers of cats we have excluded? In the intended solution to the problem this creates an additional vertex in the center of the room with four connected edges, clearly not in line with the "three vertices per vertex" rule. I elaborated underneath Hagen von Eitzen's post to more clearly define what it would mean to "see" another "cat" if you desire more details concerning what am I asking. $\endgroup$ – Brevan Ellefsen Oct 4 '16 at 1:00
  • $\begingroup$ Regardless though, thank you for your answer! $\endgroup$ – Brevan Ellefsen Oct 4 '16 at 1:00
  • 1
    $\begingroup$ @BrevanEllefsen the "additional vertex" in the intended solution is not really a vertex, it's just two edges crossing each other. (This is allowed in graph theory.) The graph has four vertices, each connected to the other three. It is $K_4$, the complete graph of order 4. $\endgroup$ – Nathaniel Oct 4 '16 at 5:06
  • 1
    $\begingroup$ Brevan, you should learn about graphs and in particular visibility graphs might be interesting to you. The visibility graph of the vertices of a convex polygon is the complete graph, e.g. the visibility graph of the vertices of the square is the complete graph on 4 vertices. The "diagonals" do not create new vertex, this is just an artefact of drawing a non-planar graph in the plane. Imagine one diagonal going over the other diagonal if that helps. $\endgroup$ – Sasho Nikolov Oct 4 '16 at 8:27
4
$\begingroup$

This is a special case of theorem from graph theory: Given an undirected graph $G$, if $d(g)$ is the degree of each node, then $\sum_{g\in G} d(g)=2E$, where $E$ is the number of edges in the graph.

In this case, you have $d(g)=3$ for each cat $g$, so you'd want $3|G|=2E$, which means that $|G|$, the number of cats, must be even.

Basically, if $C$ is the number of cats, then $3C$ counts the each pair of cats that can see each other twice, so $3C$ must be even, so $C$ must be even.

This also means that if every cat can see exactly an odd number of cats, then the total number of cats must be even.

$\endgroup$
  • $\begingroup$ Just a picky remark: formally, this is somewhat strange. You start by saying "graph G". Typically a graph is defined as (V, E) where E is a subset of VxV. But in the rest of your answer you use G as if it was the set of nodes/cats. I.e you use G as if it was the set of vertices rather than the graph itself... $\endgroup$ – dingalapadum Oct 4 '16 at 23:00
  • $\begingroup$ @dingalapadum This is common in my favorite school of thought which discards pedantry whenever it is unnecessary. Groups and rings are treated as sets of their elements, why not graphs as sets of their vertices, with the edges being implicit baggage? $\endgroup$ – Matt Samuel Oct 5 '16 at 10:58
  • $\begingroup$ Yeah, I chose to assume $|G|$ was just notation for the number of nodes of $G$. No real risk of confusion, except for when read by a computer :) $\endgroup$ – Thomas Andrews Oct 5 '16 at 13:29
  • $\begingroup$ @MattSamuel 'why not graphs as sets of their vertices, with the edges being implicit baggage?' Because for a given set of vertices there are 2^(n \choose 2) possible graphs. Which one do you mean? If it was implicitly clear, then why would we have the concept of a graph in the first place? IMO a graph induces structure on a set. OTOH sets lack preciesly that structre. The situation is similar for groups and rings - why the heck would we have introduced these concepts, if all we needed is the underlaying set? There is a difference between simplifying and oversimplifying... $\endgroup$ – dingalapadum Oct 5 '16 at 21:04
  • $\begingroup$ Actually, it wasn't so much about the $|G|$ part. I mean, I've seen $|G|$ being defined as $|V|$. I rather find the $g \in G$ funny (yes, from the context it is clear what you mean - as I said in the beginning, it's just a formal thing). I thought the change is not really invasive, would make it more formally correct and most importantly would simply conform more to the usual notation found in literature (for instance here: en.wikipedia.org/wiki/Degree_(graph_theory)). If you really think this is more readable, so be it. $\endgroup$ – dingalapadum Oct 6 '16 at 7:07
3
$\begingroup$

How about if there was a Triangle of cats. Each cat is a vertex. There are mirrors between the cats, so each cat can see itself.

Graphic Demonstration

Summary: In conclusion, I state that it is possible to see three cats in a triangle of three cats if you use mirrors.

$\endgroup$
  • $\begingroup$ I thought of the same. The problem is that I didn't want to include mirrors in the problem! A perfectly valid solution otherwise though :) $\endgroup$ – Brevan Ellefsen Oct 3 '16 at 18:49
  • 2
    $\begingroup$ "Three other cats". A cat seeing themselves does not count as seeing an other cat. $\endgroup$ – Nij Oct 4 '16 at 1:39
  • $\begingroup$ @Nij true. However, I already know you can solve the problem with mirrors for any odd numbers of cats greater than 3, so the fact that Zopesconk's solution does not totally abide by the puzzle can be forgiven :) $\endgroup$ – Brevan Ellefsen Oct 4 '16 at 3:47
  • $\begingroup$ @Nij: It seems that cats may not have self-recognition and treat their reflections as other cats $\endgroup$ – Henry Oct 5 '16 at 10:45
  • $\begingroup$ @Henry I'm well aware of the phenomenon, as the two at home both demonstrated, to my entertainment. But then I think you're getting into a philosophical distinction - is the subject of perception of cat the same as the object from which the perception of cat originates? $\endgroup$ – Nij Oct 5 '16 at 10:51
3
$\begingroup$

No-one's asked what happens if cats being able to see each other isn't mutual: if the "visibility relation" isn't symmetric. In that case, the relation corresponds to a directed graph where every node has in-degree 3. Since every edge going into a given vertex must also come out of some vertex, the sum of the out-degrees must equal the sum of the in-degrees, and if the number of cats is finite then it follows that each cat can be seen by an average of three cats. But other than that, there are no restrictions; it could be that all cats can see the same three cats (including those three cats themselves, perhaps via mirrors).

$\endgroup$
  • $\begingroup$ Interesting! I appreciate you taking the time to note this. As I note in the comments on most of the answers, the mutual definition is but one very restricted interpretation of the original problem, and I desire greatly to see solutions for other interpretations. Thank you so much for your time! $\endgroup$ – Brevan Ellefsen Oct 4 '16 at 1:52
  • 2
    $\begingroup$ You can think of this answer as showing why the "very restricted" interpretation is also the most interesting one. With too little restriction, you can't say anything at all! $\endgroup$ – Robin Saunders Oct 4 '16 at 2:07
  • 1
    $\begingroup$ This was my immediate thought, with a specific example. Imagine a circular hallway, with cats uniformly spaced in the center of the hallway, each looking the same angular direction (so all clockwise or all anti-clockwise). Now, we can change the radius of the circle and the width of the hallway so each cat sees three cats in front of it, but not the fourth one. From there, it should be possible to approximate the circle using a polygon, such that there's one cat in each corner of the exterior wall, and to do so in such a way that the cats still see three other cats. $\endgroup$ – MichaelS Oct 5 '16 at 3:27
  • 1
    $\begingroup$ An interesting question to consider is whether the resulting graph can be connected; the answer depends on the group but also on the choice of generators. For example, most finite simple groups (the "building blocks" of finite groups, like the prime numbers are for integers) can be represented with three generators. There's an interesting slideshow related to this here: www2.warwick.ac.uk/fac/sci/maths/research/events/seminars/areas/… - it's aimed at postgraduates, but contains lots of relevant keywords for you to read about further. $\endgroup$ – Robin Saunders Oct 5 '16 at 15:20
  • 1
    $\begingroup$ Finally, here's a more beginner-friendly, less intense introduction by the legendary Terry Tao: terrytao.wordpress.com/2010/07/10/… $\endgroup$ – Robin Saunders Oct 5 '16 at 15:33
1
$\begingroup$

Building onto Robin Saunders' idea, it is definitely possible that cat A can see cat B but cat B can't see cat A. It's just like kids playing hide and seek closing their eyes - "if you can't see them they can't see you right?"

Since cats are not infinitesimally small, nor are they made up of just their eyes and they don't have $360^\circ$ FOV, we can very easily restrict their vision with something like an anti-scratch cone, now of course the question leaves a lot of room for discussion due to how little information there are regarding the restrictions, and how closely one would like to interpret the question to reality is another thing, but I personally really like this type of questions where there are no true answers, nor bounded by no-fun mathematical theories.

A very easy 3 way triangle would look like:

3  →  3
 ↖ ▼ ↙
   3

where '3' are 3 cats and the arrows are the direction they are looking at.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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