Difference between revisions of "2009 UNCO Math Contest II Problems/Problem 6"

Latest revision as of 19:51, 28 August 2025

Problem

Let each of $m$ distinct points on the positive $x$ -axis be joined to each of $n$ distinct points on the positive $y$ -axis. Assume no three segments are concurrent (except at the axes). Obtain with proof a formula for the number of interior intersection points. The diagram shows that the answer is $3$ when $m=3$ and $n=2.$

$[asy] draw((0,0)--(0,3),arrow=Arrow()); draw((0,0)--(4,0),arrow=Arrow()); for(int x=0;x<4;++x){ for(int y=0;y<3;++y){ D((x,0)--(0,y),black); }} dot(IP((2,0)--(0,1),(1,0)--(0,2))); dot(IP((3,0)--(0,1),(1,0)--(0,2))); dot(IP((3,0)--(0,1),(2,0)--(0,2))); [/asy]$

Solution

Solution 1

Notice that choosing two points on the x axis and two points on the y axis, then, after constructing all possible lines, there will be only one point of intersection. So the answer is

$\binom{m}{2} \binom{n}{2}$

Solution 2

Let the points be $x_1 < x_2 \dots < x_m$ and $y_1<y_2 \dots < y_n$ . Let $(x_i,y_j)$ represent the segment formed by joining $(x_i,0), (0,y_j)$ . We first take $(x_1,y_1)$ . No segments intersect this. For $(x_1,y_2)$ , all the segments $(x_i,y_1)$ , $i \in \{2,3 \dots m\}$ will intersect. Thus, we get $(m-1)(1)$ intersections. For $(x_1,y_3)$ , all the segments with $(x_i,y_1),(x_i,y_2), x_i \neq x_1$ will intersect this. Thus we get $(m-1)(2)$ intersections. We keep going like this and finally for $(x_1,y_n)$ , we get $(m-1)(n-1)$ intersections. When we move to $(x_2,y_i)$ , we note that only points to the right intersect, thus we will be doing the same steps with $(m-2)$ instead. From this, we get the total intersections to be $(1 + 2 + \dots + n-1)(m-1) + (1 + 2 + \dots + n-1)(m-2) \dots (1 + 2 + \dots + n-1)(1) = \boxed{\frac{(n-1)(n)}{2} \cdot \frac{(m-1)(m)}{2}}$

@@ Line 24: / Line 24: @@
 == Solution ==
+=== Solution 1 ===
+Notice that choosing two points on the x axis and two points on the y axis, then, after constructing all possible lines, there will be only one point of intersection. So the answer is
+<math>\binom{m}{2} \binom{n}{2}</math>
+=== Solution 2 ===
+Let the points be <math>x_1 < x_2 \dots < x_m</math> and <math>y_1<y_2 \dots < y_n</math>. Let <math>(x_i,y_j)</math> represent the segment formed by joining <math>(x_i,0), (0,y_j)</math>. We first take <math>(x_1,y_1)</math>. No segments intersect this. For <math>(x_1,y_2)</math>, all the segments <math>(x_i,y_1)</math>,  <math>i \in \{2,3 \dots m\}</math> will intersect. Thus, we get <math>(m-1)(1)</math> intersections. For <math>(x_1,y_3)</math>, all the segments with <math>(x_i,y_1),(x_i,y_2), x_i \neq x_1</math> will intersect this. Thus we get <math>(m-1)(2)</math> intersections. We keep going like this and finally for <math>(x_1,y_n)</math>, we get <math>(m-1)(n-1)</math> intersections. When we move to <math>(x_2,y_i)</math>, we note that only points to the right intersect, thus we will be doing the same steps with <math>(m-2)</math> instead. From this, we get the total intersections to be <cmath> (1 + 2 + \dots +  n-1)(m-1) + (1 + 2 + \dots + n-1)(m-2) \dots (1 + 2 + \dots +  n-1)(1) = \boxed{\frac{(n-1)(n)}{2} \cdot \frac{(m-1)(m)}{2}}</cmath>
 == See also ==
-{{UNC Math Contest box|year=2009|n=II|num-b=5|num-a=7}}
+{{UNCO Math Contest box|year=2009|n=II|num-b=5|num-a=7}}
 [[Category:Introductory Combinatorics Problems]]

2009 UNCO Math Contest II (Problems • Answer Key • Resources)
Preceded by Problem 5	Followed by Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNCO Math Contest Problems and Solutions

Page

Toolbox

Search