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

Tinku Tara 0 Comments
Pin




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}. \\ $$

Pin

Leave a Reply

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