Cake
  • Log In
  • Sign Up
    • I think in order for the 5 official solutions for two circles to be valid, by definition each circle must be of a different radius. Therefore, each additional circle must also be of a different radius:

      [1", 2", 3", ...]

      I fear that not even that would be sufficient to allow for all possible configurations down the line. Have a look at some of the images starting at around 4:10 of the following video.

      (Spoiler alert: the following YouTube video talks about a very similar problem, just with touching circles disallowed)

      Even with just four circles, it is apparently necessary to draw one circle bigger than the whole page, while another one is tiny. The expert in the video calls these configurations "delicate", but I look at them and have to assume that something is wrong with the original problem itself if it leads to random solutions like these. It's just not beautiful enough for my taste. :)

      Duplicates. Am I wrong in thinking that each setup or scenario would have one less number of variations than the previous setup? Due to duplicates.

      Can you clarify what exactly you mean by the term "setup"? Is it the same what I called a configuration, or is it something different?

      By the way, it's fun to see that this conversation has quickly led to a point where we need to define strict terminology. :D

    • Thanks guys, you have totally killed my productivity this afternoon ;).

      The more I think about this the more I wonder whether the problem is framed correctly. I think the complicating problem is that we keep talking about different sizes of circles, but radii is a continuous length, so I'm wondering if the solution itself is not going to be possible to compute.

      Maybe the problem needs to be simplified a bit?

    • Okay, let’s dive into terms.

      Can you clarify what exactly you mean by the term "setup"? Is it the same what I called a configuration, or is it something different?

      Two circles have 5 possibilities or 5 configurations or 5 variations. I agree with using configurations going forward so that we are all speaking the same language.

      A setup is where you have a unique initial configuration and then two of the circles rotate through as many configurations as possible while the third circle maintains its current position.

      3 circles separated would be a setup. (It would also be a configuration.) You would have 4 configurations of A and C while B stays separated, 4 for B and C while A stays separated, and 4 for A and B while C stays separated. For a total of 13 configurations.

      A setup of 4 circles separated would add 12 more configurations for D and A while B and C stay separated, D and B while A and C stay separated, and D and C while A and B stayed separated.

      You then need to add all the configurations of

      A, B, C not separated while D remains separated, which is 12 (I think)

      B, C, D while A remains separated, 12 more

      C, D, A while B remains separated, 12

      and D, A, B while C remains separated, 12 more.

      So for the setup of 4 circles you would have 13 plus 12 (for 2 circles separated) plus 48 (for 1 circle separated).

      That totals to 61, or 60 configurations plus the setup of 4 circles separated.

      3 ⭕️ separated is 12+1 configurations

      4 ⭕️ separated is 60+1 configurations

      How many configurations would there be for a setup of 5 circles separated?

    • A setup is where you have a unique initial configuration and then two of the circles rotate through as many configurations as possible while the third circle maintains its current position.

      3 circles separated would be a setup. (It would also be a configuration.) You would have 4 configurations of A and C while B stays separated, 4 for B and C while A stays separated, and 4 for A and B while C stays separated. For a total of 13 configurations.

      I think an important point to consider here is that we've named these circles A, B and C for convenience, but they are unnamed (and thus interchangeable) in the original problem.

      If, from the original configuration of all three circles being separate, you change A and B to be intersecting, the result will be the same as if you had changed A and C, or B and C, to intersect. The original problem only cares about the resulting configuration of "two circles intersecting, the third one separate from all others", not about the way we got there.

      This means that, at least for three circles, we should only need to care about the number of occurrences of each two-circle configuration. but not about the circles' "identities". In consequence, there should be 35 different three-circle configurations:

      5*4*3 / 3*2*1 = 10, where all two-circle configurations are different
      5*4 = 20, where one two-circle configuration appears twice
      5, where the same two-circle configuration is used three times.

      Some of these might be geometrically impossible, so we probably should check all of them by hand(?).

      To complicate things further, the "identity" of individual circles becomes important again with n>3, because different permutations of any set of six two-circle configurations can lead to different results.

    • This means that, at least for three circles, we should only need to care about the number of occurrences of each two-circle configuration. but not about the circles' "identities". In consequence, there should be 35 different three-circle configurations:

      5*4*3 / 3*2*1 = 10, where all two-circle configurations are different
      5*4 = 20, where one two-circle configuration appears twice
      5, where the same two-circle configuration is used three times.

      Some of these might be geometrically impossible, so we probably should check all of them by hand(?).

      I found 33 solutions depicted in the below image. Two of the 35 fields are empty, they correspond to the following configurations which I think are impossible:

      35: Touching outside - Touching outside - Contained
      45: Touching outside - Touching inside - Contained

      I assume that this is a complete list - or can you find any others?

    • This is an incredible piece of work, @Factotum . Completely blows my mind at your thoroughness and organization approach. Big round of

      👏👏👏👏

      I’ve gone over all of your drawings and have been trying to determine if it’s a complete set. I think you nailed it. There may be small A intersecting medium B and both inside big C that’s not included, but I could be completely wrong here.

      I’ll admit that I am a bit lost with your math below. Can you help me out? I’m a tad rusty on combinatorics, to be honest, but interested to understand.

      5*4*3 / 3*2*1 = 10, where all two-circle configurations are different
      5*4 = 20, where one two-circle configuration appears twice
      5, where the same two-circle configuration is used three times.

    • Thanks, @apm. :)

      I’ve gone over all of your drawings and have been trying to determine if it’s a complete set. I think you nailed it. There may be small A intersecting medium B and both inside big C that’s not included, but I could be completely wrong here.

      I think this is #75 in the lower left corner?

      I’ll admit that I am a bit lost with your math below. Can you help me out? I’m a tad rusty on combinatorics, to be honest, but interested to understand.

      Sure. If we have three circles that interact pairwise, that makes six different interactions (AB, AC, BA, BC, CA, CB) - this is often modeled as drawing two of three balls from an urn without putting them back, with three options for the first ball and two for the second (3*2=6).

      In this case, we're not interested in the order, though, so we need to divide that by the number of possible permutations of each pair: 6/2=3 (basically, we want to treat AB as being the same as BA). This means that, between three circles, there are three "interactions" (or, as we called them earlier, "2-circle configurations").

      Now we want to find out what combinations of interactions are possible. There are five different types of interactions (1.separate, 2.touching outside, 3.intersecting, 4.touching inside, 5.contained). Here, we want to allow duplicates, so we can enumerate 125 possible combinations (5*5*5=125). Again, we're not interested in the order of interactions (e.g. we don't want to deal with CBA if we've already dealt with ABC), so we need to trim down that list a bit.

      Here, it helps to look at three different types of combinations.

      1. All interactions are different. This is similar to the above example of picking three of five balls from an urn (5*4*3), then dividing by the number of permutations of each result (3*2*1). This leads to ten different results.

      2. Two interactions are the same, the third one is different. This is like picking two of five balls (5*4) and then magically duplicating the first ball. Because we're doing this, we mustn't divide by the number of permutations (2*1) in this case - instead, we're considering all twenty different results.

      3. Last but not least, the results where all three interactions are the same. With five different interactions possible, the result here is obviously five as well.

      Altogether, that's 10+20+5 = 35 potential results, of which one seems to be impossible.

      For my images, I did exactly this. Enumerate all 125 possibilities

      1. Separate - Separate - Separate
      2. Separate - Separate - Touching Outside
      3. Separate - Separate - Intersecting
      4. Separate - Separate - Touching Inside
      5. Separate - Separate - Contained
      ...
      125. Contained - Contained - Contained

      Then trim down to unique combinations, then try to draw an image for each. That's where the strange numbering in the upper left corner of each square is coming from.

    • 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 thought the author of the original tweet that started this discussion might enjoy reading our explorations.

      👇

    • 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. :)