Maximum and Minimum number of regions inside a circle divided by n lines

What is the maximum number of regions within a circle that can be formed by n distinct lines intersecting inside the circle? Express your answer in fraction form. (Use LaTeX syntax, enclose your answer in dollar signs ($): $\frac{1}{2}$)

Answer:

Correct! The answer is $\binom n2+\binom n1 + \binom n0=\binom {n+1}{2} + 1=\frac{n^{2}+n+2}{2}$

Incorrect! Try again.

What is the maximum number of regions within a circle that can be formed by n distinct lines intersecting outside the circle?
Answer:

Correct! The answer is $n+1$

Incorrect! Try again.

What is the minimum number of regions within a circle that can be formed by n distinct lines crossing the circle?
Answer:

Correct! The answer is $n+1$

Incorrect! Try again.

(Based on Mathcounts National 1990 Target Problem 8 and Mathcounts Chapter 1992 Sprint problem 5)
import simplegui import random import math WIDTH=600 HEIGHT=250 CIRCLE_CENTER=(150,120) CIRCLE_RIGHT_CENTER=(150+300,120) CIRCLE_RADIUS=95 messageNumLinesPos=[120,20] messageNumRegionsPos=[120,240] YES_BUTTON_POS_BOTTOM_LEFT=[450,60] YES_BUTTON_POS_BOTTOM_RIGHT=[550,60] YES_BUTTON_POS_TOP_RIGHT=[550,30] YES_BUTTON_POS_TOP_LEFT=[450,30] YES_BUTTON_COORDS=[YES_BUTTON_POS_BOTTOM_LEFT,YES_BUTTON_POS_BOTTOM_RIGHT,YES_BUTTON_POS_TOP_RIGHT,YES_BUTTON_POS_TOP_LEFT] NO_BUTTON_POS_BOTTOM_LEFT=[450,110] NO_BUTTON_POS_BOTTOM_RIGHT=[550,110] NO_BUTTON_POS_TOP_RIGHT=[550,80] NO_BUTTON_POS_TOP_LEFT=[450,80] NO_BUTTON_COORDS=[NO_BUTTON_POS_BOTTOM_LEFT,NO_BUTTON_POS_BOTTOM_RIGHT,NO_BUTTON_POS_TOP_RIGHT,NO_BUTTON_POS_TOP_LEFT] NEXT_BUTTON_POS_BOTTOM_LEFT=[450,250] NEXT_BUTTON_POS_BOTTOM_RIGHT=[550,250] NEXT_BUTTON_POS_TOP_RIGHT=[550,220] NEXT_BUTTON_POS_TOP_LEFT=[450,220] NEXT_BUTTON_COORDS=[NEXT_BUTTON_POS_BOTTOM_LEFT,NEXT_BUTTON_POS_BOTTOM_RIGHT,NEXT_BUTTON_POS_TOP_RIGHT,NEXT_BUTTON_POS_TOP_LEFT] clickedYes = False clickedNo = False scrollup = 0 countScrolls=0 points = [(20,200),(260,80),(20,20),(260,200),(60,240),(270,40)] pointsRight = [(20+300,200),(260+300,80),(20+300,20),(260+300,200),(155+300,145)] pointsIds = [(20,72),(60,35),(140,95),(254,30),(155,158)] messageNumLines="n=1" messageNumRegions = "2 regions" n=1 # Handler for buttons def increasen(): global messageNumLines ,messageNumRegions,n if (n<5): n +=1 messageNumLines = "n=" + str(n) messageNumRegions = str((n**2+n+2)/2) + " regions" def decreasen(): global messageNumLines ,messageNumRegions,n if (n>1): n -=1 messageNumLines = "n=" + str(n) messageNumRegions = str((n**2+n+2)/2) + " regions" def handleCase1(canvas): canvas.draw_line(points[0],points[1],3,"Yellow") m = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b = points[0][1]-m*points[0][0] for i in range(1,2600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m*x+b): canvas.draw_circle((x,y),1,2,"Red") else: canvas.draw_circle((x,y),1,2,"White") def handleCase2(canvas): global messageNumLinesPos,messageNumRegionsPos canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") messageNumLinesPos=[120,20] messageNumRegionsPos=[120,240] #find coefficients of the 2 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] for i in range(1,2600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y<m2*x+b2): canvas.draw_circle((x,y),1,2,"White") elif (y<m1*x+b1) and (y<m2*x+b2): canvas.draw_circle((x,y),1,2,"Cyan") else: canvas.draw_circle((x,y),1,2,"Green") def drawYesNo(canvas,color): canvas.draw_polygon(YES_BUTTON_COORDS,12,color,color) canvas.draw_text("Yes", [YES_BUTTON_POS_BOTTOM_LEFT[0]+(YES_BUTTON_POS_BOTTOM_RIGHT[0]-YES_BUTTON_POS_BOTTOM_LEFT[0])/4,YES_BUTTON_POS_TOP_LEFT[1]+(YES_BUTTON_POS_BOTTOM_LEFT[1]-YES_BUTTON_POS_TOP_LEFT[1])/2],18,"Black") canvas.draw_polygon(NO_BUTTON_COORDS,12,color,color) canvas.draw_text("No", [NO_BUTTON_POS_BOTTOM_LEFT[0]+(NO_BUTTON_POS_BOTTOM_RIGHT[0]-NO_BUTTON_POS_BOTTOM_LEFT[0])/4,NO_BUTTON_POS_TOP_LEFT[1]+(NO_BUTTON_POS_BOTTOM_LEFT[1]-NO_BUTTON_POS_TOP_LEFT[1])/2],18,"Black") def handleCase3a(canvas): canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") #find coefficients of the 2 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] #intersection point xint = (b1-b2)*1.0/(m2-m1) yint = m1*xint + b1 #find 3rd line with common point x3=xint+130 y3=10*yint/xint*x3 m3=-(yint-y3)/130.0 b3=y3-m3*x3 canvas.draw_line([xint,yint],[xint+130,10*yint*1.0/xint*(xint+130)],3,"Cyan") canvas.draw_line([xint,yint],[xint-130,250-10*yint*1.0/xint*(xint+130)],3,"Cyan") for i in range(1,2600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Cyan") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"White") elif (y<m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Green") elif (y<m1*x+b1) and (y<m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Yellow") else: canvas.draw_circle((x,y),1,2,"Fuchsia") global messageNumRegions,messageNumRegionsPos messageNumRegions = "6 regions. Can we do better?" if (messageNumLinesPos[0]>70): messageNumLinesPos[0]-=10 if (messageNumRegionsPos[0]>10): messageNumRegionsPos[0] -= 10 drawYesNo(canvas,"orange") def handleCase3(canvas): #redraw left side handleCase3a(canvas) #delete yes/no buttons drawYesNo(canvas,"black") canvas.draw_circle(CIRCLE_RIGHT_CENTER,CIRCLE_RADIUS,3,"Green") canvas.draw_line(pointsRight[0],pointsRight[1],3,"Yellow") canvas.draw_line(pointsRight[2],pointsRight[3],3,"Red") #find coefficients of the 2 lines m1 = (pointsRight[0][1]-pointsRight[1][1])*1.0/(pointsRight[0][0]-pointsRight[1][0]) b1 = pointsRight[0][1]-m1*pointsRight[0][0] m2 = (pointsRight[2][1]-pointsRight[3][1])*1.0/(pointsRight[2][0]-pointsRight[3][0]) b2 = pointsRight[2][1]-m2*pointsRight[2][0] #intersection point xint = (b1-b2)*1.0/(m2-m1) yint = m1*xint + b1 canvas.draw_line([xint-50,yint],[xint+130-50,10*yint*1.0/xint*(xint+130-50)],3,"Cyan") canvas.draw_line([xint-50,yint],[xint-130-50,250-10*yint*1.0/xint*(xint+130-50)],3,"Cyan") #find 3rd line params x3=xint+130-50 y3=10*yint/xint*x3 m3=-(yint-y3)/130.0 b3=y3-m3*x3 for i in range(1,2600): x = random.randrange(300,600) y = random.randrange(1,250) if (x-150-300)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Cyan") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"White") elif (y<m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Green") elif (y<m1*x+b1) and (y<m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Yellow") elif (y<m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Orange") else: canvas.draw_circle((x,y),1,2,"Fuchsia") canvas.draw_text("Yes! 7 regions", [messageNumRegionsPos[0]+420,messageNumRegionsPos[1]], 28, "Red") def handleCase4(canvas): canvas.draw_circle(CIRCLE_CENTER,CIRCLE_RADIUS,3,"Green") canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") #find coefficients of the 2 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] #intersection point xint = (b1-b2)*1.0/(m2-m1) yint = m1*xint + b1 canvas.draw_line([xint-50,yint],[xint+130-50,10*yint*1.0/xint*(xint+130-50)],3,"Cyan") canvas.draw_line([xint-50,yint],[xint-130-50,250-10*yint*1.0/xint*(xint+130-50)],3,"Cyan") #find 3rd line params x3=xint+130-50 y3=10*yint/xint*x3 m3=-(yint-y3)/130.0 b3=y3-m3*x3 #4th line canvas.draw_line(points[4],points[5],3,"Brown") m4 = (points[4][1]-points[5][1])*1.0/(points[4][0]-points[5][0]) b4 = points[4][1]-m4*points[4][0] for i in range(1,2600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Grey") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Cyan") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Blue") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"White") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Purple") elif (y<m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Green") elif (y<m1*x+b1) and (y<m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Yellow") elif (y<m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Orange") else: canvas.draw_circle((x,y),1,2,"Fuchsia") global messageNumLinesPos,messageNumRegionsPos messageNumLinesPos=[130,20] messageNumRegionsPos=[130,240] canvas.draw_text("When we add a line, ", [300,20-scrollup], 28, "Red") canvas.draw_text("the new line should never ", [300,48-scrollup], 28, "Red") canvas.draw_text("go through an existing ", [300,76-scrollup], 28, "Red") canvas.draw_text("intersection point. ", [300,104-scrollup], 28, "Red") canvas.draw_text("If it does, it will only add",[300,132-scrollup],28,"Red") canvas.draw_text("2 news regions. ",[300,160-scrollup],28,"Red") canvas.draw_text("Instead the new line should ",[300,188-scrollup],28,"Green") canvas.draw_text("intersect every previous ",[300,216-scrollup],28,"Green") canvas.draw_text("line at a point where no",[300,244-scrollup],28,"Green") canvas.draw_text("two lines have yet ",[300,272-scrollup],28,"Green") canvas.draw_text("intersected.",[300,300-scrollup],28,"Green") canvas.draw_text("Thus the nth line will have",[300,328-scrollup],28,"Green") canvas.draw_text("n-1 intersections. Each of ",[300,356-scrollup],28,"Green") canvas.draw_text("these split an existing ",[300,382-scrollup],28,"Green") canvas.draw_text("region into 2, therefore ",[300,410-scrollup],28,"Green") canvas.draw_text("creating n new regions.",[300,438-scrollup],28,"Green") def handleCases(canvas): if n==1: handleCase1(canvas) elif n==2: handleCase2(canvas) elif n==3 and not clickedYes and not clickedNo: handleCase3a(canvas) elif n==3 and (clickedYes or clickedNo): handleCase3(canvas) elif n==4: handleCase4(canvas) def mclick(pos): global clickedYes,clickedNo #Yes button click if n==3 and pos[0]>YES_BUTTON_POS_BOTTOM_LEFT[0] and pos[0]<YES_BUTTON_POS_BOTTOM_RIGHT[0] and pos[1]>YES_BUTTON_POS_TOP_LEFT[1] and pos[1]<YES_BUTTON_POS_BOTTOM_LEFT[1]: clickedYes=True #No button click elif n==3 and pos[0]>NO_BUTTON_POS_BOTTOM_LEFT[0] and pos[0]<NO_BUTTON_POS_BOTTOM_RIGHT[0] and pos[1]>NO_BUTTON_POS_TOP_LEFT[1] and pos[1]<NO_BUTTON_POS_BOTTOM_LEFT[1]: clickedNo = True #Next button elif n==5 and pos[0]>NEXT_BUTTON_POS_BOTTOM_LEFT[0] and pos[0]<NEXT_BUTTON_POS_BOTTOM_RIGHT[0] and pos[1]>NEXT_BUTTON_POS_TOP_LEFT[1] and pos[1]<NEXT_BUTTON_POS_BOTTOM_LEFT[1]: clickedYes = True def timer_handler(): global scrollup, countScrolls if n==4 and countScrolls<18: scrollup +=28 countScrolls +=1 elif n==4 and countScrolls==18: countScrolls=0 scrollup=0 scrollup -= 28*9 else: countScrolls=0 scrollup=0 def sweepLine(canvas): pass def draw(canvas): if n>4: messageNumLines1 = "For n lines, the maximum number of " messageNumLines2 = "regions is therefore given by the sum " messageNumLines3 = "2+2+3+4+5+...+n-1+n. " messageNumLines4 = "Can you figure how what does this" messageNumLines5 = "sum add up to?" messageNumLines6 = "Alternatively imagine we divide the " messageNumLines7 = "circle using n lines into the max number" messageNumLines8 = "of regions. Imagine a line that lies " messageNumLines9 = "initially outside the circle. Because" messageNumLines10 = "this line intersects the n lines at " messageNumLines11 = "n points it intersects n+1 regions. " messageNumLines12 = "Now move this line across all the " messageNumLines13 = "intersections of the n lines (inside" messageNumLines14 = "the circle). Since each of the n lines" messageNumLines15 = "intersects every other line there are" messageNumLines16 = "n choose 2 intersections. Each time " messageNumLines17 = "the sweeping line crosses one of these" messageNumLines18 = "intersections in enters a new region." messageNumLines19 = "Therefore there are (n choose 2) + " messageNumLines20 = "(n choose 1) + (n choose 0) maximum " messageNumLines21 = "regions. Interestingly this is equal" messageNumLines22 = "to (n+1) choose 2 +1. Why?" canvas.draw_text(messageNumLines1,[10,20],18,"Red") canvas.draw_text(messageNumLines2,[10,40],18,"Red") canvas.draw_text(messageNumLines3,[10,60],18,"Red") canvas.draw_text(messageNumLines4,[10,80],18,"Red") canvas.draw_text(messageNumLines5,[10,100],18,"Red") canvas.draw_text(messageNumLines6,[10,120],18,"Green") canvas.draw_text(messageNumLines7,[10,140],18,"Green") canvas.draw_text(messageNumLines8,[10,160],18,"Green") canvas.draw_text(messageNumLines9,[10,180],18,"Green") canvas.draw_text(messageNumLines10,[10,200],18,"Green") canvas.draw_text(messageNumLines11,[10,220],18,"Green") canvas.draw_text(messageNumLines12,[10,240],18,"Green") canvas.draw_text(messageNumLines13,[300,20],18,"Green") canvas.draw_text(messageNumLines14,[300,40],18,"Green") canvas.draw_text(messageNumLines15,[300,60],18,"Green") canvas.draw_text(messageNumLines16,[300,80],18,"Green") canvas.draw_text(messageNumLines17,[300,100],18,"Green") canvas.draw_text(messageNumLines18,[300,120],18,"Green") canvas.draw_text(messageNumLines19,[300,140],18,"Green") canvas.draw_text(messageNumLines20,[300,160],18,"Green") canvas.draw_text(messageNumLines21,[300,180],18,"Green") canvas.draw_text(messageNumLines22,[300,200],18,"Green") #canvas.draw_polygon(NEXT_BUTTON_COORDS,12,"orange","orange") #canvas.draw_text("Next",[NEXT_BUTTON_POS_BOTTOM_LEFT[0]+(NEXT_BUTTON_POS_BOTTOM_RIGHT[0]-NEXT_BUTTON_POS_BOTTOM_LEFT[0])/4,NEXT_BUTTON_POS_TOP_LEFT[1]+(NEXT_BUTTON_POS_BOTTOM_LEFT[1]-NEXT_BUTTON_POS_TOP_LEFT[1])/2],18,"Black") #if clickedYes: # sweepLine(canvas) else: canvas.draw_text(messageNumLines,messageNumLinesPos, 28, "Red") canvas.draw_circle(CIRCLE_CENTER,CIRCLE_RADIUS,3,"Green") handleCases(canvas) canvas.draw_text(messageNumRegions, messageNumRegionsPos, 28, "Red") # Create a frame and assign callbacks to event handlers frame = simplegui.create_frame("How many regions?", WIDTH, HEIGHT) frame.add_button("From n=1 to n=4", increasen) frame.add_button("From n=4 to n=1", decreasen) frame.set_mouseclick_handler(mclick) frame.set_draw_handler(draw) timer = simplegui.create_timer(1000,timer_handler) timer.start() # Start the frame animation frame.start()
import simplegui import random import math WIDTH=600 HEIGHT=250 CIRCLE_CENTER=(150,120) CIRCLE_RIGHT_CENTER=(150+300,120) CIRCLE_RADIUS=95 messageNumLinesPos=[120,20] messageNumRegionsPos=[120,240] messageNumLines="n=1" messageNumRegions = "2 regions" n=1 points = [(20,220),(320,80),(20,80),(320,110),(20,200),(320,200),(20,20),(320,100)] # Handler for buttons def increasen(): global messageNumLines ,messageNumRegions,n if (n<5): n +=1 messageNumLines = "n=" + str(n) messageNumRegions = str((n+1)) + " regions" def decreasen(): global messageNumLines ,messageNumRegions,n if (n>1): n -=1 messageNumLines = "n=" + str(n) messageNumRegions = str((n+1)) + " regions" def handleCase1(canvas): canvas.draw_line(points[0],points[1],3,"Yellow") m = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b = points[0][1]-m*points[0][0] for i in range(1,600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m*x+b): canvas.draw_circle((x,y),1,2,"Red") else: canvas.draw_circle((x,y),1,2,"White") def handleCase2(canvas): global messageNumLinesPos,messageNumRegionsPos canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") messageNumLinesPos=[120,20] messageNumRegionsPos=[120,240] #find coefficients of the 2 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] for i in range(1,600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y<m2*x+b2): canvas.draw_circle((x,y),1,2,"White") elif (y<m1*x+b1) and (y<m2*x+b2): canvas.draw_circle((x,y),1,2,"Cyan") else: canvas.draw_circle((x,y),1,2,"Green") def handleCase3(canvas): canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") canvas.draw_line(points[4],points[5],3,"Cyan") #find coefficients of the 3 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] m3 = (points[4][1]-points[5][1])*1.0/(points[4][0]-points[5][0]) b3 = points[4][1]-m2*points[4][0] for i in range(1,600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Cyan") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"White") elif (y<m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Green") elif (y<m1*x+b1) and (y<m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Yellow") else: canvas.draw_circle((x,y),1,2,"Fuchsia") def handleCase4(canvas): canvas.draw_line(points[0],points[1],3,"Yellow") canvas.draw_line(points[2],points[3],3,"Red") canvas.draw_line(points[4],points[5],3,"Cyan") canvas.draw_line(points[6],points[7],3,"Brown") #find coefficients of the 4 lines m1 = (points[0][1]-points[1][1])*1.0/(points[0][0]-points[1][0]) b1 = points[0][1]-m1*points[0][0] m2 = (points[2][1]-points[3][1])*1.0/(points[2][0]-points[3][0]) b2 = points[2][1]-m2*points[2][0] m3 = (points[4][1]-points[5][1])*1.0/(points[4][0]-points[5][0]) b3 = points[4][1]-m2*points[4][0] m4 = (points[6][1]-points[7][1])*1.0/(points[6][0]-points[7][0]) b4 = points[6][1]-m2*points[6][0] for i in range(1,600): x = random.randrange(1,300) y = random.randrange(1,250) if (x-150)**2+(y-120)**2<95**2: if (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Red") elif (y>m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Grey") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Cyan") elif (y>m1*x+b1) and (y>m2*x+b2) and (y>m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Blue") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"White") elif (y>m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y>m4*x+b4): canvas.draw_circle((x,y),1,2,"Purple") elif (y<m1*x+b1) and (y<m2*x+b2) and (y<m3*x+b3) and (y<m4*x+b4): canvas.draw_circle((x,y),1,2,"Green") elif (y<m1*x+b1) and (y<m2*x+b2) and (y>m3*x+b3): canvas.draw_circle((x,y),1,2,"Yellow") elif (y<m1*x+b1) and (y>m2*x+b2) and (y<m3*x+b3): canvas.draw_circle((x,y),1,2,"Orange") else: canvas.draw_circle((x,y),1,2,"Fuchsia") def handleCases(canvas): if n==1: handleCase1(canvas) elif n==2: handleCase2(canvas) elif n==3: handleCase3(canvas) elif n==4: handleCase4(canvas) def draw(canvas): if n>4: messageNumLines1 = "Notice that every time we add one extra" messageNumLines2 = "line, the best we can do is cut one " messageNumLines3 = "existing region into 2. We can not create" messageNumLines4 = "more than one new region because that" messageNumLines5 = "would involve the new line intersecting " messageNumLines6 = "an existing line inside the circle. " messageNumLines7 = "But all intersections between the lines " messageNumLines8 = "occur outside the circle." messageNumLines9 = "Therefore the maximum number of regions" messageNumLines10 = "we can create with n lines intersecting" messageNumLines11 = "outside the circle is n+1." canvas.draw_text(messageNumLines1,[10,20],18,"Green") canvas.draw_text(messageNumLines2,[10,40],18,"Green") canvas.draw_text(messageNumLines3,[10,60],18,"Green") canvas.draw_text(messageNumLines4,[10,80],18,"Green") canvas.draw_text(messageNumLines5,[10,100],18,"Green") canvas.draw_text(messageNumLines6,[10,120],18,"Green") canvas.draw_text(messageNumLines7,[10,140],18,"Green") canvas.draw_text(messageNumLines8,[10,160],18,"Green") canvas.draw_text(messageNumLines9,[10,180],18,"Green") canvas.draw_text(messageNumLines10,[10,200],18,"Green") canvas.draw_text(messageNumLines11,[10,220],18,"Green") else: canvas.draw_text(messageNumLines,messageNumLinesPos, 28, "Red") canvas.draw_circle(CIRCLE_CENTER,CIRCLE_RADIUS,3,"Green") handleCases(canvas) canvas.draw_text(messageNumRegions, messageNumRegionsPos, 28, "Red") # Create a frame and assign callbacks to event handlers frame = simplegui.create_frame("How many regions?", WIDTH, HEIGHT) frame.add_button("From n=1 to n=4", increasen) frame.add_button("From n=4 to n=1", decreasen) frame.set_draw_handler(draw) # Start the frame animation frame.start()
import simplegui import random import math WIDTH=600 HEIGHT=250 def draw(canvas): messageNumLines1 = "The minimum number of regions we" messageNumLines2 = "can divide the circle by n lines " messageNumLines3 = "will occur when none of the n lines" messageNumLines4 = "intersect inside the circle." messageNumLines5 = "If the n lines are parallel " messageNumLines6 = "they will create n+1 regions inside the " messageNumLines7 = "circle. If a few intersect outside the " messageNumLines8 = "circle will that change the number of " messageNumLines9 = "regions they divide the circle?" canvas.draw_text(messageNumLines1,[10,20],18,"Green") canvas.draw_text(messageNumLines2,[10,40],18,"Green") canvas.draw_text(messageNumLines3,[10,60],18,"Green") canvas.draw_text(messageNumLines4,[10,80],18,"Green") canvas.draw_text(messageNumLines5,[10,100],18,"Green") canvas.draw_text(messageNumLines6,[10,120],18,"Green") canvas.draw_text(messageNumLines7,[10,140],18,"Green") canvas.draw_text(messageNumLines8,[10,160],18,"Green") canvas.draw_text(messageNumLines9,[10,180],18,"Green") # Create a frame and assign callbacks to event handlers frame = simplegui.create_frame("How many regions?", WIDTH, HEIGHT) frame.set_draw_handler(draw) # Start the frame animation frame.start()

Maximum number of lines drawn out of n points

There are n distinct points in a plane. No three of the points are collinear. Find the maximum number of distinct lines that can be drawn if these points are connected. Express your answer in fraction form. (Use LaTeX syntax, enclose your answer in dollar signs ($): $\frac{1}{2}$)

Answer:

(Based on Mathcounts National 1990 Sprint Problem 29)

Correct! The answer is $\binom n2=\frac{n(n-1)}{2}$

Incorrect! Try again.

import simplegui points = [(20,80),(60,40),(140,100),(250,25),(155,145)] pointsIds = [(20,72),(60,35),(140,95),(254,30),(155,158)] messageNumPoints = "n=3" messageNumLines="3 lines" n=3 # Handler for buttons def increasen(): global messageNumPoints ,messageNumLines,n if (n<6): n +=1 messageNumPoints = "n=" + str(n) messageNumLines = str(n*(n-1)/2) + " lines" def decreasen(): global messageNumPoints ,messageNumLines,n if (n>3): n -=1 messageNumPoints = "n=" + str(n) messageNumLines = str(n*(n-1)/2) + " lines" def draw(canvas): if n>5: messageNumLines1 = "For a general n, point A can connect " messageNumLines2 = "to at most n-1 points thus forming n-1 " messageNumLines3 = "lines. Point B can connect to at most " messageNumLines4 = "n-2 points forming n-2 lines..." messageNumLines5 = "So the answer is n-1+n-2+...+1 lines." messageNumLines6 = "Alternatively to draw a line we need to " messageNumLines7 = " pick 2 points out of the n points. " messageNumLines8 = "We have n choices for the first point and " messageNumLines9 = "n-1 choices for the second point. " messageNumLines10 = " Since each such pair is counted twice " messageNumLines11 = " we divide by 2." canvas.draw_text(messageNumLines1,[10,20],18,"Red") canvas.draw_text(messageNumLines2,[10,40],18,"Red") canvas.draw_text(messageNumLines3,[10,60],18,"Red") canvas.draw_text(messageNumLines4,[10,80],18,"Red") canvas.draw_text(messageNumLines5,[10,100],18,"Red") canvas.draw_text(messageNumLines6,[10,120],18,"Green") canvas.draw_text(messageNumLines7,[10,140],18,"Green") canvas.draw_text(messageNumLines8,[10,160],18,"Green") canvas.draw_text(messageNumLines9,[10,180],18,"Green") canvas.draw_text(messageNumLines10,[10,200],18,"Green") canvas.draw_text(messageNumLines11,[10,220],18,"Green") else: canvas.draw_text(messageNumPoints, [120,20], 28, "Red") canvas.draw_text("A", pointsIds[0], 10, "White") canvas.draw_text("B", pointsIds[1], 10, "White") canvas.draw_text("C", pointsIds[2], 10, "White") if n>3: canvas.draw_text("D", pointsIds[3], 10, "White") if n>4: canvas.draw_text("E", pointsIds[4], 10, "White") canvas.draw_circle(points[0],3,2,"Green","Green") canvas.draw_circle(points[1],3,2,"Red","Red") canvas.draw_circle(points[2],3,2,"Blue","Blue") if n>3: canvas.draw_circle(points[3],3,2,"Orange","Orange") if n>4: canvas.draw_circle(points[4],3,2,"White","White") canvas.draw_line(points[0],points[1],2,"Yellow") canvas.draw_line(points[0],points[2],2,"Yellow") canvas.draw_line(points[1],points[2],2,"Cyan") if n>3: canvas.draw_line(points[0],points[3],2,"Yellow") canvas.draw_line(points[1],points[3],2,"Cyan") canvas.draw_line(points[2],points[3],2,"Red") if n>4: canvas.draw_line(points[0],points[4],2,"Yellow") canvas.draw_line(points[1],points[4],2,"Cyan") canvas.draw_line(points[2],points[4],2,"Red") canvas.draw_line(points[3],points[4],2,"Green") canvas.draw_text(messageNumLines, [120,220], 28, "Red") # Create a frame and assign callbacks to event handlers frame = simplegui.create_frame("How many lines?", 300, 250) frame.add_button("From n=3 to n=5", increasen) frame.add_button("From n=5 to n=3", decreasen) frame.set_draw_handler(draw) # Start the frame animation frame.start()