• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 07:13
CET 13:13
KST 21:13
  • 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
RSL Revival - 2025 Season Finals Preview7RSL Season 3 - Playoffs Preview0RSL Season 3 - RO16 Groups C & D Preview0RSL Season 3 - RO16 Groups A & B Preview2TL.net Map Contest #21: Winners12
Community News
Weekly Cups (Dec 1-7): Clem doubles, Solar gets over the hump1Weekly Cups (Nov 24-30): MaxPax, Clem, herO win2BGE Stara Zagora 2026 announced15[BSL21] Ro.16 Group Stage (C->B->A->D)4Weekly Cups (Nov 17-23): Solar, MaxPax, Clem win3
StarCraft 2
General
RSL Revival - 2025 Season Finals Preview Weekly Cups (Dec 1-7): Clem doubles, Solar gets over the hump Chinese SC2 server to reopen; live all-star event in Hangzhou Maestros of the Game: Live Finals Preview (RO4) BGE Stara Zagora 2026 announced
Tourneys
RSL Offline Finals Info - Dec 13 and 14! Tenacious Turtle Tussle 2025 RSL Offline Finals Dates + Ticket Sales! Sparkling Tuna Cup - Weekly Open Tournament StarCraft2.fi 15th Anniversary Cup
Strategy
Custom Maps
Map Editor closed ?
External Content
Mutation # 503 Fowl Play Mutation # 502 Negative Reinforcement Mutation # 501 Price of Progress Mutation # 500 Fright night
Brood War
General
BGH Auto Balance -> http://bghmmr.eu/ [BSL21] RO8 Bracket & Prediction Contest BW General Discussion FlaSh on: Biggest Problem With SnOw's Playstyle Let's talk about Metropolis
Tourneys
[ASL20] Grand Finals [BSL21] RO8 - Day 2 - Sunday 21:00 CET [BSL21] RO8 - Day 1 - Saturday 21:00 CET Small VOD Thread 2.0
Strategy
Simple Questions, Simple Answers Game Theory for Starcraft Fighting Spirit mining rates Current Meta
Other Games
General Games
Dawn of War IV Path of Exile Stormgate/Frost Giant Megathread Awesome Games Done Quick 2026! Nintendo Switch Thread
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Deck construction bug Heroes of StarCraft mini-set
TL Mafia
Mafia Game Mode Feedback/Ideas Survivor II: The Amazon Sengoku Mafia TL Mafia Community Thread
Community
General
Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread US Politics Mega-thread YouTube Thread European Politico-economics QA Mega-thread
Fan Clubs
White-Ra Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece Movie Discussion!
Sports
2024 - 2026 Football Thread Formula 1 Discussion
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
TL+ Announced Where to ask questions and add stream?
Blogs
How Sleep Deprivation Affect…
TrAiDoS
I decided to write a webnov…
DjKniteX
James Bond movies ranking - pa…
Topin
Thanks for the RSL
Hildegard
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1570 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 47m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
trigger 8
StarCraft: Brood War
Britney 35520
Calm 4237
Horang2 1420
Hyuk 1417
Bisu 1244
Jaedong 879
Stork 395
EffOrt 353
actioN 320
Last 260
[ Show more ]
Sharp 226
firebathero 220
ZerO 151
Killer 111
Hyun 101
Pusan 89
sorry 70
ToSsGirL 62
Aegong 43
Mong 33
scan(afreeca) 28
Movie 17
ajuk12(nOOB) 13
Oya187 13
Dota 2
singsing3989
Dendi989
XcaliburYe466
League of Legends
C9.Mang0365
Counter-Strike
x6flipin491
Super Smash Bros
Westballz24
Heroes of the Storm
Khaldor273
Other Games
summit1g8695
FrodaN1737
B2W.Neo1272
XaKoH 174
Fuzer 74
Mew2King51
KnowMe14
ZerO(Twitch)13
Organizations
StarCraft 2
ComeBackTV 377
StarCraft: Brood War
CasterMuse 30
lovetv 7
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 13 non-featured ]
StarCraft 2
• Berry_CruncH183
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota2113
Other Games
• Scarra633
Upcoming Events
WardiTV 2025
47m
herO vs ShoWTimE
SHIN vs herO
Clem vs herO
SHIN vs Clem
SHIN vs ShoWTimE
Clem vs ShoWTimE
IPSL
4h 47m
Sziky vs JDConan
BSL 21
7h 47m
Tech vs Cross
Bonyth vs eOnzErG
Replay Cast
20h 47m
Wardi Open
23h 47m
Monday Night Weeklies
1d 4h
Sparkling Tuna Cup
1d 21h
Replay Cast
3 days
The PondCast
3 days
CranKy Ducklings
5 days
[ Show More ]
SC Evo League
6 days
BSL 21
6 days
Sparkling Tuna Cup
6 days
Liquipedia Results

Completed

Acropolis #4 - TS3
RSL Revival: Season 3
Kuram Kup

Ongoing

C-Race Season 1
IPSL Winter 2025-26
KCM Race Survival 2025 Season 4
YSL S2
BSL Season 21
Slon Tour Season 2
WardiTV 2025
META Madness #9
SL Budapest Major 2025
ESL Impact League Season 8
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
Thunderpick World Champ.
CS Asia Championships 2025
ESL Pro League S22

Upcoming

CSL 2025 WINTER (S19)
BSL 21 Non-Korean Championship
Acropolis #4
IPSL Spring 2026
Bellum Gens Elite Stara Zagora 2026
HSC XXVIII
Big Gabe Cup #3
PGL Cluj-Napoca 2026
IEM Kraków 2026
BLAST Bounty Winter 2026
BLAST Bounty Winter Qual
eXTREMESLAND 2025
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 © 2025 TLnet. All Rights Reserved.