• Log In
  • Sign Up
    • Btw, what is the combination for the impossible #35?


      Your explanation made perfect sense, thank you. If there were three balls and only two different types of interactions (say separated and touching) there would be 2*2*2 possible combinations:

      1. Separate - Separate - Separate

      2. Separate - Separate - Touching

      3. Separate - Touching - Separate

      4. Touching - Separate - Separate

      5. Separate - Touching - Touching

      6. Touching - Touching - Separate

      7. Touching - Separate - Touching

      8. Touching - Touching - Touching

      So there would be 4 potential results with only two different types of interactions.

      2 types of interactions, 4 potential results

      3 types of interactions, ?? potential results

      4 types of interactions, ??? potential results

      5 types of interactions, 35 potential results

    • Btw, what is the combination for the impossible #35?

      That combination is Touching outside - Touching outside - Contained. The problem with this is that one of these interactions between two circles constrains others involving the same circle.

      For example, if we start by drawing two circles touching, then we would need to draw the third circle so that it touches one on the outside, but is contained within (or "contains", this is not a symmetrical property) the other.

      There seems to be only one problem like this with three circles - but if we think about four or even more circles, these problems will surely pop up more often because we will be more and more constrained by having to draw all of them in the 2D plane. It would be great if we had the means to rule out some of the potential 4-circle candidates automatically, for example if they contain this impossible 3-circle configuration as a subset.

      So there would be 4 potential results with only two different types of interactions.

      2 types of interactions, 4 potential results

      3 types of interactions, ?? potential results

      4 types of interactions, ??? potential results

      5 types of interactions, 35 potential results

      This is very interesting. I calculated the number of potential results for 3 and 4, and the whole list seems to be 4, 10, 20, 35. Just pasting these numbers into a Google search, I found that these are the first few tetrahedral numbers:

      Now, what we actually want to do is not to increase the number of interaction types (that is a constant 5), but the number of circles involved. Still, the observation that having three circles (or, more likely, three two-circle interactions between them) and a variable number of interaction types leads to tetrahedral numbers (which themselves are partial sums of triangle numbers) might be a clue about how to deal with four circles.

      Four circles have six two-circle interactions between them, so maybe the number of possible configurations of those will have something to do with partial sums of hexagonal numbers?

      More research necessary! :D

    • According to the above, I thought about the case of having four circles but only two interaction types between them.

      To find out how many potential configurations exist, I think we can veer into graph theory: every circle becomes a vertex in our fully connected graph, and the interaction between each pair of circles becomes a label on the edge connecting the two vertices that correspond to the circles forming this interaction.

      The graph for the case of four circles looks like this - four vertices, and six edges:

      We can then generate all possible graphs by labeling all of the six edges with either of two labels (for the two different interactions we allow). This leads to 2^6=64 different graphs - but not all of them are actually different. Because we don't care about the vertex names, we can swap the positions of vertices (and the corresponding edges with them) - and if the result looks like a graph we already have, we can ignore the new one. In graph theory, that's called isomorphism.

      The good thing is that this works in theory.

      The bad thing is that graph isomorphism is one of very few computational problems where we don't even know how hard it really is - just that it's very hard. ;)

      The other bad thing is that, while thinking about this problem in graph theory terms, it occurred to me that some of the edge labels work well on an undirected edge, while others only work on a directed edge.

      For example, if we state that "circle A is separate from circle B", then the reverse ("B is separate from A") is also true. However, if we state that "circle A includes circle B", then the reverse ("circle B includes circle A") is not true.

      Taking this directedness into account, there might be additional cases for 3 circles that I didn't draw - but at the very least, this will make any problem with n>3 circles a bit more complicated.

    • I received two interesting replies from Christopher Klerk, @Factotum . If I’m understanding correctly, in the second tweet Christopher is saying that he believes that touching inside, contained, contained is an additional configuration.


    • Thanks @apm - and an indirect "Hello!" to Christopher, if he continues to read this thread! :)

      Christopher is correct pointing out at least one missing configuration, and I already found another one. The problem here really is that the asymmetrical interactions ("touching inside" and "contained") can lead to multiple variants being possible where I only considered one to exist.

      This can happen if there (a) is more than one asymmetrical interaction, and (b) the remaining symmetrical interactions aren't all the same.

      In many cases, it looks as if the variants aren't possible to draw - for example "A contains B, B contains C, C touches A on the inside" is a theoretical third variant of the alternative solution Christopher found, but one that's just impossible. Still, there are many potential configurations that still need to be checked.

      (This, by the way, throws the whole "Tetrahedral numbers" tangent out of the window. ;))

    • Hello @ChrisKlerkx - and welcome to Cake! :)

      48 - I really missed a lot! I will have to study your images in more detail later, but looks great so far. Enumerating by number of intersection points is a nice idea. :)