• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 00:38
CEST 06:38
KST 13:38
  • 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] Ro16 Preview: Holy Diver5[ASL22] Ro16 Preview: Rough Waters10[ASL22] Ro24 Preview: Siren's Call8[ASL22] Ro24 Preview: Summer's End9Serral wins HomeStory Cup 2915
Community News
Weekly Cups (Sep 7-12): SHIN, ByuN, MaxPax double down1StarCraft open world shooter announced at BlizzCon100Weekly Cups (Aug 30-Sep 7): herO thrives amid growing schism10Official StarCraft website teases new content ahead of BlizzCon?179Stellar Fest TWO the Moon (Dec 16-20)9
StarCraft 2
General
SC4ALL II: StarCraft 2 Player Announcement 8/8 Balance hotfix patch 5.0.16b (July 16) The Death of Cheese: From a Professional Cheeser Yamato Cup Series StarCraft open world shooter announced at BlizzCon
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament RSL Revival: Season 6 - Qualifiers and Main Event RSL goes to London! 2026 Offline Finals Nov 21-22 SC2 AI Tournament 2026 Fall KSL Week #92
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
Nexus Wars 2021 GUIDE [M] (2) Industrial Park
External Content
Mutation # 543 Enhanced Defenses The PondCast: SC2 News & Results Mutation # 542 The Ascended Mutation # 541 Binary Choice
Brood War
General
an AI researcher's take on the ladder bot Bot on ladder Syncronization issues and can't find games New 3v3 BGH Ladder (and more) on ShieldBattery! Remastered crash fix suggestions
Tourneys
[ASL22] Ro16 Group D [BSL23] SM: Ret vs TerrOr - bo7 - Sunday 9pm CEST [ASL22] Ro16 Group C [Megathread] Daily Proleagues
Strategy
Replay Review Process - What do you do? Simple Questions, Simple Answers Odyssey Mineral Stack Saturation Game Theory for Starcraft
Other Games
General Games
Warcraft III: The Frozen Throne Nintendo Switch Thread Stormgate/Frost Giant Megathread EVE Corporation Diablo IV
Dota 2
Official 'what is Dota anymore' discussion
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 Russo-Ukrainian War Thread Canadian Politics Mega-thread Post Your Watch!
Fan Clubs
MarineLorD Fan Club The Creator Fan Club The ShoWTimE Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Diablo Animated Series on Netflix
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023 MLB/Baseball 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Northern Ireland Global Starcraft
Blogs
Can Bots Beat Pros?? Starcr…
namkraft
[meme] I finally understa…
LUCKY_NOOB
Virtual Romance, Real-Life C…
TrAiDoS
Regacy Esports:Our Goa…
regacyesports
Dreaming of BW patches (mod…
c3rberUs
Customize Sidebar...

Website Feedback

Closed Threads



Active: 7998 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
Replay Cast
00:00
ISSL Monthly #1 - Day 2
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
WinterStarcraft609
RuFF_SC2 249
StarCraft: Brood War
Larva 228
sSak 70
Icarus 4
Dota 2
NeuroSwarm241
Other Games
summit1g11173
JimRising 626
PiGStarcraft333
C9.Mang0306
XaKoH 194
Mew2King60
Liquid`Ken20
Organizations
Other Games
gamesdonequick1565
[ Show 15 non-featured ]
StarCraft 2
• practicex 18
• davetesta13
• Letter146
• Adnapsc2 1
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• lizZardDota243
League of Legends
• Rush1052
• Stunt354
Upcoming Events
GSL
6h 23m
AI Arena Tournament
12h 23m
Replay Cast
19h 23m
GSL
1d 6h
Shopify Rebellion Sundays
1d 10h
Spirit vs Mixu
BSL
1d 14h
Ret vs TerrOr
Replay Cast
1d 19h
Afreeca Starleague
2 days
Shine vs Rush
WardiTV Weekly
2 days
Monday Night Weeklies
2 days
[ Show More ]
Sparkling Tuna Cup
3 days
Afreeca Starleague
3 days
Light vs EffOrt
PiGosaur Cup
3 days
Kung Fu Cup
4 days
The PondCast
5 days
Replay Cast
5 days
Korean StarCraft League
6 days
Liquipedia Results

Completed

KCM Race Survival 2026 Season 3
Blizzard Classic Cup 2026
Big Dog Cup 2026 Div 1

Ongoing

K-JUNGMAN
ASL Season 22
Super Anchor Qualifying S3
CSL 2026 AUTUMN (S22)
Acropolis #5
Acropolis #5 - GSA
Calamity Invitational
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026
Esports World Cup 2026
BLAST Bounty Summer 2026
BLAST Bounty Summer Qual
Stake Ranked Episode 3
XSE Pro League 2026

Upcoming

Acropolis #5 - GSB
Acropolis #5 - GSC
SC4ALL II: Brood War
HSC XXX
Stellar Fest 2: Lunar Cup
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
Copium Cup
PGL Major Singapore 2026
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
Stake Ranked Episode 5
PGL Masters Bucharest 2026
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
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.