Cake
  • Log In
  • Sign Up
    • Mathematics is the study of patterns and problem solving. As I went further in my graduate studies, I became more and more intrigued by the patterns aspect of mathematics.

      What’s the next number in the sequence. What’s the 5th number in the sequence?

      These are intriguing questions to solve for any pattern. But the ultimate question to solve is what is the pattern for the millionth or billionth number in the sequence? To answer that question, you have to crack the code or the equation that gives you the answer for any term in the sequence. We call this “any term” the nth term.

      For example, what’s the next number in this sequence?

      5, 7, 9, 11, 13, 15

      If you figured it was 17, you are correct.

      But can you tell me what the 25th number in the sequence is? Or the 100th number?

      Using number theory, you can determine that the 25th term is 53:

      If the 5th term is 13 and the 6th term is 15, then the code is twice the term plus 3. So twice 25 plus 3 is 53.

      Expressed in terms of any number, 2n+3.

      **********

      So how would you unravel the pattern for intersecting circles?

      My thoughts are to start with a smaller problem. Figure out the number of possibilities for three circles, then for four circles. Use manipulatives to more easily visualize the possibilities: coins, bingo chips, circles cut from different colored post-its. Record your data in a table for n=2,3 or 4 and crack the code.

      Please share your thinking for how you solved this—I am more interested in your thinking and your problem solving approaches then in just the answer.

    • So how would you unravel the pattern for intersecting circles?

      My thoughts are to start with a smaller problem. Figure out the number of possibilities for three circles, then for four circles. Use manipulatives to more easily visualize the possibilities: coins, bingo chips, circles cut from different colored post-its. Record your data in a table for n=2,3 or 4 and crack the code.

      Please share your thinking for how you solved this—I am more interested in your thinking and your problem solving approaches then in just the answer.

      I need to stay on the sidelines for this one, because I just saw a video about this exact problem last week.

      Once ideas have been brought up, I'd be interested in discussing this further though, because what I saw in that video was a bit unsatisfying. :)

    • You are taking us through combinatorial math, which determines number of permutations. I love it but have been so out of touch for so long... so I'll just kibitzer this one, if you don't mind me, hahaha..

    • Please share your thinking for how you solved this—I am more interested in your thinking and your problem solving approaches then in just the answer.

      Turns out, the video I saw was about a similar but not the same problem. The video still contains some ideas on how to approach this problem - but I think I've thought about it enough in the last 24 hours to provide my own take on it. :)

      First, I like to check that I've completely understood the problem, and that the hints given are complete as well. In this case, there's a drawing with five pairs of circles, with the following configurations:

      1. Separate
      2. One containing the other
      3. Touching on the outside
      4. Touching on the inside
      5. Intersecting

      I can imagine one of the two circles being fixed, and the other being moved across it - and can't think of any other configuration unless they are a rotated or mirrored variant of an existing one. Apparently, these symmetries are supposed to be ignored, as is the relative sizes of both circles.

      Then, I consider adding a third circle to the mix - and it occurs to me that this can be done in a generative way by taking the existing configurations for two circles and trying to add a third circle in all possible ways.

      I like to think about the simplest possible example first, so instead of solving the problem for 3 circles, I try to create a ruleset that leads to all 2-circle configurations when applying it to the only configuration of one circle. Basically:

      1. Draw a circle A
      2. For all of the five possible ways for a circle to be positioned relative to A, draw that circle B.

      I (obviously) get all the five results we already had, so this ruleset seems to work. How does it need to be rephrased to get from two to three circles?

      1. Instead of having one circle A, we have a set of five configurations for circles A and B, so we change our first rule to "Iterate over all five configurations."

      2. When placing a third circle, we need to check all five configurations relative to A, AND all five configurations relative to B. This means that our second rule needs to become "For all 5*5=25 ways for a circle to be positioned relative to A and B, draw this circle."

      It seems to be possible to apply the same pattern to any number of circles: Take all configurations of n-1 circles, then iterate over all possible positions of the n-th circle relative to all n-1 others to get a new set of configurations.

      At this point, it occurs to me that not all configurations are actually possible. For example, if A and B are in the "separate" configuration, it isn't possible to add a circle C so that A includes C and B includes C. I currently see no way to solve this other than to check each possible configuration manually. I wonder if this could be solved by some clever form of notation, but I don't really see it.

    • apm wrote:

      Please share your thinking for how you solved this—I am more interested in your thinking and your problem solving approaches then in just the answer.

      Dracula wrote:

      How about 60? did I win? 🤑

      apm wrote:

      🤣

    • Well at first (admittedly very cursory review) it appeared as simple combinatoric math. But the problem statement seems is made to be confusing because someone decided to also count when circles do not intersect at all. Nevertheless, I used this calculator & formula:

      I now realize it's nowhere near as facile to devise a "mechanism" that would encompass all possibilities considered. For that matter, excepting the simple states where "all in" or "all out", the rest are very complex..

    • I now realize it's nowhere near as facile to devise a "mechanism" that would encompass all possibilities considered. 

      I agree with you, Drac. Here are just three scenarios ⬇️ that you now have to deal with as a result of adding a third circle C. Each additional circle adds a multiplier effect so that you could go from 5 for two circles to 60(?) for three circles to 400(?) for four circles.

      Perhaps it’s helpful to determine the number of additional setups from two to three circles. By setups, I mean that one setup of C should have 1 to 10 variations. Not sure if I’m explaining it clearly: in (1) below there would be a total of 9 variations: 4 with C interacting with A while B is separated, 4 with C interacting with B while A is separated, and 1 with A, B and C separated.

    • Also, do circles have same radius? What if they were extremely different... i.e. one very small, a second larger one, and third a huge one? Does it or does it not matter? I tend to think it does..

    • Yes, I think this is one of the things that led to very unsatisfying results in the video I saw.

      If all circles have the same size, this rules out something like the "two circles touching, both inside a third circle" of your example image. In fact, it would rule out the whole "inside" configuration because a circle can never be "inside" another circle of the same size.

      On the other hand, enforcing all circles to have the same size might lead to more "sensible" results, but also more boring ones. :)

    • At this point, it occurs to me that not all configurations are actually possible. For example, if A and B are in the "separate" configuration, it isn't possible to add a circle C so that A includes C and B includes C. I currently see no way to solve this other than to check each possible configuration manually. I wonder if this could be solved by some clever form of notation, but I don't really see it.

      Regarding a "clever notation", it occurs to me that my previous attempt at generating all potential configurations of n circles by taking all possible configurations of n-1 circles and adding another one might also lead to duplicates.

      For example starting with

      "two circles intersecting" and then adding a third one that "is separate from both"

      leads to the same configuration as starting with

      "two separate circles" and then adding a third one that "intersects one but is separate from the other".

      To avoid this, we'd need to generate potential solutions in a way that skips duplicates but does not skip those where the same set of individual configurations leads to a different overall solution.

      Can this be done by first finding all different sets of SUM(1..(n-1)) circle-circle configurations ignoring their order, and then find all unique permutations of that set?

    • If all circles have the same size, this rules out something like the "two circles touching, both inside a third circle" of your example image. In fact, it would rule out the whole "inside" configuration because a circle can never be "inside" another circle of the same size.


      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:

      ⭕️ A = 1” radius

      ⭕️ B = 2” radius

      ⭕️ C = 3” radius

      and so on.

      **********

      Side note: It would be extremely helpful for mathematics discussions if we could upload multiple images of our “scratch work” into one post, @Vilen .

      **********

      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.

      So for (1) below, you would have a total of 13 variations: 1 for A, B and C separate; 4 variations of B separate from A and C, 4 variations of A separate from B and C, and 4 variations of C separate from A and B. So would (2) below have one less variation than (1), and (3) would have one less variation than (2), and so on?

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

      **********