Menu Close

One-circle-in-a-plane-can-produce-one-closed-region-at-most-It-produces-one-closed-region-at-least-Two-circles-in-a-plane-can-produce-at-most-three-regions-They-produce-at-least-two-regions




Question Number 4033 by Rasheed Soomro last updated on 27/Dec/15
    One circle in a plane can produce one  closed  region at most(It produces one closed region   at least).Two  circles in a plane  can produce  at most three  regions(They produce at least  two  regions).Three circles can produce seven  closed regions at most(They produce three  closed regions at least).        How many distinct closed regions could be produced  by 4, 5 and n  circles at most?      If n circles can produce f(n) closed regions  at most(Of course they produce n closed  regions at least), can they produce any  number of closed regions between n and f(n)?
$$\:\:\:\:\mathrm{One}\:\mathrm{circle}\:\mathrm{in}\:\mathrm{a}\:\mathrm{plane}\:\mathrm{can}\:\mathrm{produce}\:\mathrm{one}\:\:\mathrm{closed} \\ $$$$\mathrm{region}\:\mathrm{at}\:\mathrm{most}\left(\mathrm{It}\:\mathrm{produces}\:\mathrm{one}\:\mathrm{closed}\:\mathrm{region}\:\right. \\ $$$$\left.\mathrm{at}\:\mathrm{least}\right).\mathrm{Two}\:\:\mathrm{circles}\:\mathrm{in}\:\mathrm{a}\:\mathrm{plane}\:\:\mathrm{can}\:\mathrm{produce} \\ $$$$\mathrm{at}\:\mathrm{most}\:\mathrm{three}\:\:\mathrm{regions}\left(\mathrm{They}\:\mathrm{produce}\:\mathrm{at}\:\mathrm{least}\right. \\ $$$$\left.\mathrm{two}\:\:\mathrm{regions}\right).\mathrm{Three}\:\mathrm{circles}\:\mathrm{can}\:\mathrm{produce}\:\mathrm{seven} \\ $$$$\mathrm{closed}\:\mathrm{regions}\:\mathrm{at}\:\mathrm{most}\left(\mathrm{They}\:\mathrm{produce}\:\mathrm{three}\right. \\ $$$$\left.\mathrm{closed}\:\mathrm{regions}\:\mathrm{at}\:\mathrm{least}\right). \\ $$$$ \\ $$$$\:\:\:\:\mathrm{How}\:\mathrm{many}\:\boldsymbol{\mathrm{distinct}}\:\mathrm{closed}\:\mathrm{regions}\:\mathrm{could}\:\mathrm{be}\:\mathrm{produced} \\ $$$$\mathrm{by}\:\mathrm{4},\:\mathrm{5}\:\mathrm{and}\:\mathrm{n}\:\:\mathrm{circles}\:\mathrm{at}\:\mathrm{most}? \\ $$$$\:\:\:\:\mathrm{If}\:\mathrm{n}\:\mathrm{circles}\:\mathrm{can}\:\mathrm{produce}\:\mathrm{f}\left(\mathrm{n}\right)\:\mathrm{closed}\:\mathrm{regions} \\ $$$$\mathrm{at}\:\mathrm{most}\left(\mathrm{Of}\:\mathrm{course}\:\mathrm{they}\:\mathrm{produce}\:\mathrm{n}\:\mathrm{closed}\right. \\ $$$$\left.\mathrm{regions}\:\mathrm{at}\:\mathrm{least}\right),\:\mathrm{can}\:\mathrm{they}\:\mathrm{produce}\:\mathrm{any} \\ $$$$\mathrm{number}\:\mathrm{of}\:\mathrm{closed}\:\mathrm{regions}\:\mathrm{between}\:\mathrm{n}\:\mathrm{and}\:\mathrm{f}\left(\mathrm{n}\right)? \\ $$
Commented by Rasheed Soomro last updated on 27/Dec/15
For three circles 3,4,5,6 and 7 closed regions  can be made.
$$\mathrm{For}\:\mathrm{three}\:\mathrm{circles}\:\mathrm{3},\mathrm{4},\mathrm{5},\mathrm{6}\:\mathrm{and}\:\mathrm{7}\:\mathrm{closed}\:\mathrm{regions} \\ $$$$\mathrm{can}\:\mathrm{be}\:\mathrm{made}. \\ $$
Commented by Rasheed Soomro last updated on 27/Dec/15
Which area of mathematics does this problem  belong to?
$$\mathrm{Which}\:\mathrm{area}\:\mathrm{of}\:\mathrm{mathematics}\:\mathrm{does}\:\mathrm{this}\:\mathrm{problem} \\ $$$$\mathrm{belong}\:\mathrm{to}? \\ $$
Commented by Yozzii last updated on 27/Dec/15
Commented by Yozzii last updated on 27/Dec/15
I only first met this idea in set theory  but f(n)=2^n −1 is valid only if 0≤n≤3.  4 circles appear to give 13 closed  regions at most.
$${I}\:{only}\:{first}\:{met}\:{this}\:{idea}\:{in}\:{set}\:{theory} \\ $$$${but}\:{f}\left({n}\right)=\mathrm{2}^{{n}} −\mathrm{1}\:{is}\:{valid}\:{only}\:{if}\:\mathrm{0}\leqslant{n}\leqslant\mathrm{3}. \\ $$$$\mathrm{4}\:{circles}\:{appear}\:{to}\:{give}\:\mathrm{13}\:{closed} \\ $$$${regions}\:{at}\:{most}. \\ $$
Commented by Yozzii last updated on 27/Dec/15
Commented by Yozzii last updated on 27/Dec/15
5 circles appear to produce at most  21 closed regions.  n=0: f(0)=0  n=1: f(1)=1  n=2: f(2)=3  n=3: f(3)=7  n=4: f(4)=13  n=5: f(5)=21  n=6: f(6)=31  f(1)−f(0)=1=1×2^0   f(2)−f(1)=2=1×2  f(3)−f(2)=4=2×2  f(4)−f(3)=6=3×2  f(5)−f(4)=8=4×2  f(6)−f(5)=10=5×2  n≥1, f(n+1)−f(n)=2n, f(1)=1  f(n+1)=f(n)+2n  f(n+1)−f(n)=2n  f(n)−f(n−1)=2(n−1)  f(n−1)−f(n−2)=2(n−2)  ⋮  f(4)−f(3)=2×3  f(3)−f(2)=2×2  f(2)−f(1)=2×1  ⇒f(n+1)−f(1)=2Σ_(r=1) ^n r  f(n+1)=f(1)+2×0.5n(n+1)  f(n+1)=1+n(n+1)  ⇒f(n)=1+n(n−1)  f(n)=n^2 −n+1  n≥1
$$\mathrm{5}\:{circles}\:{appear}\:{to}\:{produce}\:{at}\:{most} \\ $$$$\mathrm{21}\:{closed}\:{regions}. \\ $$$${n}=\mathrm{0}:\:{f}\left(\mathrm{0}\right)=\mathrm{0} \\ $$$${n}=\mathrm{1}:\:{f}\left(\mathrm{1}\right)=\mathrm{1} \\ $$$${n}=\mathrm{2}:\:{f}\left(\mathrm{2}\right)=\mathrm{3} \\ $$$${n}=\mathrm{3}:\:{f}\left(\mathrm{3}\right)=\mathrm{7} \\ $$$${n}=\mathrm{4}:\:{f}\left(\mathrm{4}\right)=\mathrm{13} \\ $$$${n}=\mathrm{5}:\:{f}\left(\mathrm{5}\right)=\mathrm{21} \\ $$$${n}=\mathrm{6}:\:{f}\left(\mathrm{6}\right)=\mathrm{31} \\ $$$${f}\left(\mathrm{1}\right)−{f}\left(\mathrm{0}\right)=\mathrm{1}=\mathrm{1}×\mathrm{2}^{\mathrm{0}} \\ $$$${f}\left(\mathrm{2}\right)−{f}\left(\mathrm{1}\right)=\mathrm{2}=\mathrm{1}×\mathrm{2} \\ $$$${f}\left(\mathrm{3}\right)−{f}\left(\mathrm{2}\right)=\mathrm{4}=\mathrm{2}×\mathrm{2} \\ $$$${f}\left(\mathrm{4}\right)−{f}\left(\mathrm{3}\right)=\mathrm{6}=\mathrm{3}×\mathrm{2} \\ $$$${f}\left(\mathrm{5}\right)−{f}\left(\mathrm{4}\right)=\mathrm{8}=\mathrm{4}×\mathrm{2} \\ $$$${f}\left(\mathrm{6}\right)−{f}\left(\mathrm{5}\right)=\mathrm{10}=\mathrm{5}×\mathrm{2} \\ $$$${n}\geqslant\mathrm{1},\:{f}\left({n}+\mathrm{1}\right)−{f}\left({n}\right)=\mathrm{2}{n},\:{f}\left(\mathrm{1}\right)=\mathrm{1} \\ $$$${f}\left({n}+\mathrm{1}\right)={f}\left({n}\right)+\mathrm{2}{n} \\ $$$${f}\left({n}+\mathrm{1}\right)−{f}\left({n}\right)=\mathrm{2}{n} \\ $$$${f}\left({n}\right)−{f}\left({n}−\mathrm{1}\right)=\mathrm{2}\left({n}−\mathrm{1}\right) \\ $$$${f}\left({n}−\mathrm{1}\right)−{f}\left({n}−\mathrm{2}\right)=\mathrm{2}\left({n}−\mathrm{2}\right) \\ $$$$\vdots \\ $$$${f}\left(\mathrm{4}\right)−{f}\left(\mathrm{3}\right)=\mathrm{2}×\mathrm{3} \\ $$$${f}\left(\mathrm{3}\right)−{f}\left(\mathrm{2}\right)=\mathrm{2}×\mathrm{2} \\ $$$${f}\left(\mathrm{2}\right)−{f}\left(\mathrm{1}\right)=\mathrm{2}×\mathrm{1} \\ $$$$\Rightarrow{f}\left({n}+\mathrm{1}\right)−{f}\left(\mathrm{1}\right)=\mathrm{2}\underset{{r}=\mathrm{1}} {\overset{{n}} {\sum}}{r} \\ $$$${f}\left({n}+\mathrm{1}\right)={f}\left(\mathrm{1}\right)+\mathrm{2}×\mathrm{0}.\mathrm{5}{n}\left({n}+\mathrm{1}\right) \\ $$$${f}\left({n}+\mathrm{1}\right)=\mathrm{1}+{n}\left({n}+\mathrm{1}\right) \\ $$$$\Rightarrow{f}\left({n}\right)=\mathrm{1}+{n}\left({n}−\mathrm{1}\right) \\ $$$${f}\left({n}\right)={n}^{\mathrm{2}} −{n}+\mathrm{1}\:\:{n}\geqslant\mathrm{1} \\ $$$$ \\ $$
Commented by prakash jain last updated on 27/Dec/15
n−circle will give maximum 2^n −1 closed region.  ^n C_1 +^n C_2 +..+^n C_n =2^n −1  Each term on LHS^n C_r  is created by number  of ways r circles can intersect. Each of those  intersection form a closed area.  Since all circles can be independently drawn  you can create any number of closed regions  from n to 2^n −1.
$${n}−{circle}\:{will}\:{give}\:\mathrm{maximum}\:\mathrm{2}^{{n}} −\mathrm{1}\:\mathrm{closed}\:\mathrm{region}. \\ $$$$\:^{{n}} {C}_{\mathrm{1}} +^{{n}} {C}_{\mathrm{2}} +..+\:^{{n}} {C}_{{n}} =\mathrm{2}^{{n}} −\mathrm{1} \\ $$$$\mathrm{Each}\:\mathrm{term}\:\mathrm{on}\:\mathrm{LHS}\:^{{n}} {C}_{{r}} \:\mathrm{is}\:\mathrm{created}\:\mathrm{by}\:\mathrm{number} \\ $$$$\mathrm{of}\:\mathrm{ways}\:{r}\:\mathrm{circles}\:\mathrm{can}\:\mathrm{intersect}.\:\mathrm{Each}\:\mathrm{of}\:\mathrm{those} \\ $$$$\mathrm{intersection}\:\mathrm{form}\:\mathrm{a}\:\mathrm{closed}\:\mathrm{area}. \\ $$$$\mathrm{Since}\:\mathrm{all}\:\mathrm{circles}\:\mathrm{can}\:\mathrm{be}\:\mathrm{independently}\:\mathrm{drawn} \\ $$$$\mathrm{you}\:\mathrm{can}\:\mathrm{create}\:\mathrm{any}\:\mathrm{number}\:\mathrm{of}\:\mathrm{closed}\:\mathrm{regions} \\ $$$$\mathrm{from}\:{n}\:\mathrm{to}\:\mathrm{2}^{{n}} −\mathrm{1}. \\ $$
Commented by Rasheed Soomro last updated on 27/Dec/15
But sir Yozzii′s experiment shows that 4 circles   can produce 13 closed regions (See image of  four circles above)while your formula suggests 2^4 −1=15  Is there any mistake in experiment?
$$\mathrm{But}\:\mathrm{sir}\:\mathrm{Yozzii}'\mathrm{s}\:\mathrm{experiment}\:\mathrm{shows}\:\mathrm{that}\:\mathrm{4}\:\mathrm{circles}\: \\ $$$$\mathrm{can}\:\mathrm{produce}\:\mathrm{13}\:\mathrm{closed}\:\mathrm{regions}\:\left(\mathrm{See}\:\mathrm{image}\:\mathrm{of}\right. \\ $$$$\left.\mathrm{four}\:\mathrm{circles}\:\mathrm{above}\right)\mathrm{while}\:\mathrm{your}\:\mathrm{formula}\:\mathrm{suggests}\:\mathrm{2}^{\mathrm{4}} −\mathrm{1}=\mathrm{15} \\ $$$$\mathrm{Is}\:\mathrm{there}\:\mathrm{any}\:\mathrm{mistake}\:\mathrm{in}\:\mathrm{experiment}? \\ $$
Commented by Yozzii last updated on 27/Dec/15
Download the application called GeoGebra.  I used it to experiment. I could certainly  be wrong, so use the app to see for  yourself how you can obtain 15. I  wasn′t successful in obtaining 15  on my own.
$${Download}\:{the}\:{application}\:{called}\:{GeoGebra}. \\ $$$${I}\:{used}\:{it}\:{to}\:{experiment}.\:{I}\:{could}\:{certainly} \\ $$$${be}\:{wrong},\:{so}\:{use}\:{the}\:{app}\:{to}\:{see}\:{for} \\ $$$${yourself}\:{how}\:{you}\:{can}\:{obtain}\:\mathrm{15}.\:{I} \\ $$$${wasn}'{t}\:{successful}\:{in}\:{obtaining}\:\mathrm{15} \\ $$$${on}\:{my}\:{own}. \\ $$
Commented by Rasheed Soomro last updated on 27/Dec/15
  The process should be as  follows.  The second circle must cut the first  circle,the third circle must cut first  and second circle at distinct points.  In this way each next circle must cut  all the previous circles at distinct points,  in order to get maximum number of  closed regions. I think you  have done well.
$$\:\:\mathrm{The}\:\mathrm{process}\:\mathrm{should}\:\mathrm{be}\:\mathrm{as}\:\:\mathrm{follows}. \\ $$$$\mathrm{The}\:\mathrm{second}\:\mathrm{circle}\:\mathrm{must}\:\mathrm{cut}\:\mathrm{the}\:\mathrm{first} \\ $$$$\mathrm{circle},\mathrm{the}\:\mathrm{third}\:\mathrm{circle}\:\mathrm{must}\:\mathrm{cut}\:\mathrm{first} \\ $$$$\mathrm{and}\:\mathrm{second}\:\mathrm{circle}\:\boldsymbol{\mathrm{at}}\:\boldsymbol{\mathrm{distinct}}\:\boldsymbol{\mathrm{points}}. \\ $$$$\mathrm{In}\:\mathrm{this}\:\mathrm{way}\:\boldsymbol{\mathrm{each}}\:\boldsymbol{\mathrm{next}}\:\boldsymbol{\mathrm{circle}}\:\boldsymbol{\mathrm{must}}\:\boldsymbol{\mathrm{cut}} \\ $$$$\boldsymbol{\mathrm{all}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{previous}}\:\boldsymbol{\mathrm{circles}}\:\boldsymbol{\mathrm{at}}\:\boldsymbol{\mathrm{distinct}}\:\boldsymbol{\mathrm{points}}, \\ $$$$\mathrm{in}\:\mathrm{order}\:\mathrm{to}\:\mathrm{get}\:\mathrm{maximum}\:\mathrm{number}\:\mathrm{of} \\ $$$$\mathrm{closed}\:\mathrm{regions}.\:\mathrm{I}\:\mathrm{think}\:\mathrm{you}\:\:\mathrm{have}\:\mathrm{done}\:\mathrm{well}. \\ $$
Commented by prakash jain last updated on 27/Dec/15
I will try experimenting myself.  In a way you are saying a venn diagram  is not possible with 4 sets A, B, C, D to show  all of the following.  individual            4  2 pairs                     6  3 paris                     4  all intersection  1  I will do some more study to recall.  You may be right. I may have forgotten  a few things.
$$\mathrm{I}\:\mathrm{will}\:\mathrm{try}\:\mathrm{experimenting}\:\mathrm{myself}. \\ $$$$\mathrm{In}\:\mathrm{a}\:\mathrm{way}\:\mathrm{you}\:\mathrm{are}\:\mathrm{saying}\:\mathrm{a}\:\mathrm{venn}\:\mathrm{diagram} \\ $$$$\mathrm{is}\:\mathrm{not}\:\mathrm{possible}\:\mathrm{with}\:\mathrm{4}\:\mathrm{sets}\:\mathrm{A},\:\mathrm{B},\:\mathrm{C},\:\mathrm{D}\:\mathrm{to}\:\mathrm{show} \\ $$$$\mathrm{all}\:\mathrm{of}\:\mathrm{the}\:\mathrm{following}. \\ $$$$\mathrm{individual}\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{4} \\ $$$$\mathrm{2}\:\mathrm{pairs}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{6} \\ $$$$\mathrm{3}\:\mathrm{paris}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{4} \\ $$$$\mathrm{all}\:\mathrm{intersection}\:\:\mathrm{1} \\ $$$$\mathrm{I}\:\mathrm{will}\:\mathrm{do}\:\mathrm{some}\:\mathrm{more}\:\mathrm{study}\:\mathrm{to}\:\mathrm{recall}. \\ $$$$\mathrm{You}\:\mathrm{may}\:\mathrm{be}\:\mathrm{right}.\:\mathrm{I}\:\mathrm{may}\:\mathrm{have}\:\mathrm{forgotten} \\ $$$$\mathrm{a}\:\mathrm{few}\:\mathrm{things}. \\ $$
Commented by Yozzii last updated on 27/Dec/15
The diagram outlining all possible  events for 4 sets does not utilise  a circle, as I saw in a book I looked  at recently. Something looking like  a wrench was used, not a circle. That′s why I  doubted employing f(n)=2^n −1.  I think that if a circle were possible  the author wouldn′t have used that  wrench shape to yield all 16 regions.
$${The}\:{diagram}\:{outlining}\:{all}\:{possible} \\ $$$${events}\:{for}\:\mathrm{4}\:{sets}\:{does}\:{not}\:{utilise} \\ $$$${a}\:{circle},\:{as}\:{I}\:{saw}\:{in}\:{a}\:{book}\:{I}\:{looked} \\ $$$${at}\:{recently}.\:{Something}\:{looking}\:{like} \\ $$$${a}\:{wrench}\:{was}\:{used},\:{not}\:{a}\:{circle}.\:{That}'{s}\:{why}\:{I} \\ $$$${doubted}\:{employing}\:{f}\left({n}\right)=\mathrm{2}^{{n}} −\mathrm{1}. \\ $$$${I}\:{think}\:{that}\:{if}\:{a}\:{circle}\:{were}\:{possible} \\ $$$${the}\:{author}\:{wouldn}'{t}\:{have}\:{used}\:{that} \\ $$$${wrench}\:{shape}\:{to}\:{yield}\:{all}\:\mathrm{16}\:{regions}. \\ $$
Commented by prakash jain last updated on 27/Dec/15
You are correct n circle can at most  creat=n^2 −n+2 regions.
$$\mathrm{You}\:\mathrm{are}\:\mathrm{correct}\:{n}\:\mathrm{circle}\:\mathrm{can}\:\mathrm{at}\:\mathrm{most} \\ $$$$\mathrm{creat}={n}^{\mathrm{2}} −{n}+\mathrm{2}\:\mathrm{regions}. \\ $$
Commented by Yozzii last updated on 27/Dec/15
Including external region right?
$${Including}\:{external}\:{region}\:{right}? \\ $$
Commented by prakash jain last updated on 27/Dec/15
Yes.
$$\mathrm{Yes}. \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *