• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 20:40
CEST 02:40
KST 09:40
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL22] Finals Preview: Sweet Victory!9[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11[ASL22] Ro16 Preview: Holy Diver5
Community News
[$1250] International ShieldBattery League36Weekly Cups (October 5-11): Farewell to 5.0.164Rollback Netcode in Brood War1375.0.17 Patch Notes - October 7, 202624Weekly Cups Results (Sep 28-Oct 4)0
StarCraft 2
General
Server Blocker No more sc2 streamers on team liquid? SCII needs to put more weight on strategy and tact Stellar Fest 2 Replay Pack Terran AddOns placement
Tourneys
WORTEX Challenger Series — Open SC2 LAN in Budapes RSL goes to London! 2026 Offline Finals Nov 21-22 Sparkling Tuna Cup - Weekly Open Tournament Stellar Fest TWO the Moon (Dec 16-20) Master Swan Open (Global Bronze-Master 2)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps [A] Nemrods 1/4 players [M] (2) Sweltering Sands [M] (2) Frigid Storage
External Content
Mutation # 548 Shining Bright The PondCast: SC2 News & Results Mutation # 547 Temple Of Terror Mutation # 546 Catch the Train
Brood War
General
BW General Discussion Rollback Netcode in Brood War Mineral gathering rate (boosted) for each patch Ziemie's Starcraft 1 Prequel Campaign NaDa's Body
Tourneys
[ASL22] Grand Finals [$1250] International ShieldBattery League [Megathread] Daily Proleagues 2v2v2v2 Tournament
Strategy
Cliff Jump Revisited (1 in a 1000 strategy) Simple Questions, Simple Answers Replay Review Process - What do you do?
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Dawn of War IV Warcraft III: The Frozen Throne General RTS Discussion Thread
Dota 2
Dota 2 Champions League Season 3 Begins April 25!
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Things Aren’t Peaceful in Palestine Artificial Intelligence Thread European Politico-economics QA Mega-thread Russo-Ukrainian War Thread
Fan Clubs
Serral Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece
Sports
TeamLiquid Health and Fitness Initiative For 2023 MLB/Baseball 2023 Football (Soccer) Thread
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Recent Gifted Posts
Blogs
How Much Genes Contribute to…
TrAiDoS
ShieldBattery on Mac
Kraekkling
[ASL22] Ro4 Day1 Ticket Giv…
bITt.mAN
38 yo Retired SWE loo…
PurE)Rabbit-SF
Customize Sidebar...

Website Feedback

Closed Threads



Active: 11135 users

A Counting Problem

Blogs > blankspace
Post a Reply
blankspace
Profile Blog Joined June 2010
United States292 Posts
April 10 2011 12:45 GMT
#1
Draw n points on the circumference on a circle. Then connect all lines between all points on the circle. What is the maximum number of regions that the circle may be divided into?

Example: For the case n=3, you have a triangle inscribed in the center of the circle. The number of regions is thus 4. For the case n=4, you have a square with diagonals drawn, so that gets you 8.

I will tell you though that the answer is not 2^(n-1), but it is not complicated.

Hello friends
Oracle
Profile Blog Joined May 2007
Canada411 Posts
Last Edited: 2011-04-10 13:47:40
April 10 2011 13:15 GMT
#2
I think the answer is the (amount of faces of an n-complete graph) + n

I'll get back to you once i figure out the first part


EDIT: I dont think this is possible with my knowledge of graph theory, since # faces is ill-defined for non-planar graphs, and everything K_5 and above is nonplanar... and im stuck
Av4st
Profile Joined September 2008
Canada92 Posts
Last Edited: 2011-04-10 13:53:09
April 10 2011 13:42 GMT
#3
oops -- within the circle.. hmm
Oracle
Profile Blog Joined May 2007
Canada411 Posts
April 10 2011 13:45 GMT
#4
On April 10 2011 22:42 getty wrote:
+ Show Spoiler +
1 + 2^(n-1)


for n = 5 you have

[image loading]

which has 11 faces. Plus the 5 imaginary ones on the outside, so 16 total.

2^4 + 1 = 17
blankspace
Profile Blog Joined June 2010
United States292 Posts
April 10 2011 13:48 GMT
#5
I don't know if there is a good graph theory solution, but my solution for this does not use any. You need to find a clever way to count the regions.

Also note that the number of regions for n=7 is 57 so looking for some sort of 2^something formula is not going to work.
Hello friends
Marradron
Profile Blog Joined January 2009
Netherlands1586 Posts
Last Edited: 2011-04-10 14:00:13
April 10 2011 13:56 GMT
#6
http://mathworld.wolfram.com/CompleteGraph.html

n(n-1) /2 + n

Gotta check if its right

nvm these are edges or something not correct.
Oracle
Profile Blog Joined May 2007
Canada411 Posts
April 10 2011 14:04 GMT
#7
# VERTICES | # EDGES | # FACES
3 | 3 | 1 + 3 = 4
4 | 6 | 4 + 4 = 8
5 | 10 | 11 + 5 = 16
6 | 15 | 24 + 6 = 30
7 | 21 | 50 + 7 = 57

For anyone else attempting a graph-theory approach
Complete
Profile Joined October 2009
United States1864 Posts
Last Edited: 2011-04-10 15:23:17
April 10 2011 15:20 GMT
#8
n/m..
Complete
Profile Joined October 2009
United States1864 Posts
Last Edited: 2011-04-10 15:44:34
April 10 2011 15:43 GMT
#9
+ Show Spoiler +
(x^4-6x^3+23x^2-18x+24)/24
blankspace
Profile Blog Joined June 2010
United States292 Posts
April 10 2011 15:50 GMT
#10
@complete
+ Show Spoiler +
I think that is the correct answer, though you should realize that you can express it in a more elegant form (namely as the sum of binomial coefficients. What is your reasoning/how did you get the answer? Did you assume it was a polynomial and interpolated?
Hello friends
n.DieJokes
Profile Blog Joined November 2008
United States3443 Posts
April 10 2011 16:17 GMT
#11
It looks to me like he graphed the first couple of n's and then used software to fit the data but thats just a guess
MyLove + Your Love= Supa Love
LaLuSh
Profile Blog Joined April 2003
Sweden2358 Posts
Last Edited: 2011-04-10 18:01:54
April 10 2011 17:54 GMT
#12
+ Show Spoiler +
C(n, 4) + C(n, 2) + 1

Number of lines drawn between n points can be expressed as a series (n-1)+(n-2)+...(n-(n-1))

Or more practical as binomial coefficient: C(n,2). Expressing number of possibilities to connect 2 points in an n point circle by a line.

C(n,4) gives the number of possible intersects between any 4 of the n points in the circle.

Adding them together and the extra region in the center (+1), gives you the total.

+ Show Spoiler +
Watched the spoilers for help....
blankspace
Profile Blog Joined June 2010
United States292 Posts
April 10 2011 18:22 GMT
#13
@LaluSh

+ Show Spoiler +
That is the correct answer Can you justify why your answer is correct though? As in why should counting these intersections give you the number of regions?
Hello friends
JodoYodo
Profile Blog Joined May 2009
Canada1772 Posts
Last Edited: 2011-04-10 18:31:40
April 10 2011 18:31 GMT
#14
+ Show Spoiler +
Every time a line intersects another line, you bisect two regions into four regions
Dance dance dance 'till we run this town!
Please log in or register to reply.
Live Events Refresh
Next event in 10h 20m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 195
StarCraft: Brood War
Rain 2855
Artosis 605
ProTech120
Light 8
Dota 2
NeuroSwarm182
League of Legends
Doublelift5141
JimRising 234
Counter-Strike
Fnx 1322
Super Smash Bros
hungrybox97
Other Games
summit1g7661
shahzam555
FrodaN548
C9.Mang0344
PiGStarcraft287
Maynarde99
Organizations
Other Games
gamesdonequick794
[ Show 11 non-featured ]
StarCraft 2
• Hupsaiya 132
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Scarra1041
Other Games
• imaqtpie1183
Upcoming Events
IntoTheTV X SOOP
10h 20m
PiGosaur Cup
23h 20m
The PondCast
1d 9h
Kung Fu Cup
1d 10h
IntoTheTV X SOOP
2 days
FEL
4 days
Patches Events
4 days
FEL
5 days
Sparkling Tuna Cup
5 days
Replay Cast
5 days
[ Show More ]
WardiTV Weekly
6 days
Liquipedia Results

Completed

ASL Season 22
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
IPSL Winter 2026-27
KCM Race Survival 2026 Season 4
Acropolis #5 - GSC
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026
Esports World Cup 2026

Upcoming

BSL Season 23
SC4ALL II: Brood War
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
eXTREMESLAND 2026
PGL Major Singapore 2026
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
Stake Ranked Episode 5
PGL Masters Bucharest 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.