Math Puzzle: Integer Points

http://pratikpoddarcse.blogspot.in/2013/04/integer-points.html

by pratikpoddar • 13 years ago

40 36 13 years ago

pratikpoddarcse.blogspot.in

Scaevolus• 13 years ago

I don't understand. Choose points (0,0) (0,1) (1,0) (1,2) (2,1) (2,2). What line contains three points?

Diagram:

_OO

O_O

OO_

e: oh, not a point in the original set, any integer point. thanks!

aeflash• 13 years ago

The line segment described by (0,0) (2,2) goes through the integer point (1,1).

anonymoushn3• 13 years ago

You chose 6 points, and there are 3 line segments among them containing (1,1).

shib71• 13 years ago

I think the question might be better put this way:

Pick 5 random points on an infinite plane. Draw lines between all of them. One of those lines will contain another integer point. Prove this is true for every set of 5 random points.

nilkn• 13 years ago

There are four pairs of values modulo two, so if you have five points some two of them must be the same modulo two. Say these points are A and B. Then A + B = (even, even), and so (A + B) / 2 has integer coordinates.

tantalor2• 13 years ago

That was tough to follow, let me restate,

Let the two points be (x1, y1) and (x2, y2) such that x1 % 2 == x2 % 2 and y1 % 2 == y2 % 2, i.e., have the same parity.

Then x1 + x2 = 2 * x3 (is even) and y1 + y2 = 2 * y3 (is even), and (x3, y3) is an integer point.

Given five points, two such points must exist because of the pigeon hole principle.

olivier1664• 13 years ago

So that means that there will be at least on line which the center is an integer point.

jonsen4• 13 years ago

There are four possible coordinate parities

  (even, even),  (even, odd),  (odd, even),  (odd, odd)

Among five points two must have the same parity.

Between two points of same parity the difference has the parity (even, even).

As (even, even) is divisible by two there's an integer midpoint.

nazgulnarsil3• 13 years ago

true, you can always make one of the 4 lines have a slope that is even/even. the point composed of x/2,y/2 will lie on this line.

nazgulnarsil3• 13 years ago

back of the napkin: take the first 4 points to be a unit box with the lower left point at the origin. You can draw any of 4 lines to the 5th point (x,y). These 4 lines will have slopes x:y, x-1:y, x:y-1, x-1,y-1. You can always arrive at a slope ratio that is evenly divisible through some combination of -1 and reducing the ratio to simplest form. An evenly divisible slope ratio will pass through another point.

example: 5th point (11,4). Choose line with slope 10:4. Divisible by 2, this line passes through the point (5,2). A ratio divisible by 3 would pass through 2 additional points etc.

anonymoushn3• 13 years ago

A real proof would work for an arbitrary first four points (with any segment between two not containing a lattice point), but I think nikln already provided this :)

nazgulnarsil3• 13 years ago

doh, forgot to do the last and most important step, generalizing.

cjg• 13 years ago

Why would 4 of the points form a square?

eridius2• 13 years ago

This seems rather trivial.

Take two arbitrary points, named A and B, where Ax < Bx (if Ax == Bx, this becomes absurdly simple).

Calculate the delta ∂ between the points, such that ∂x = Bx - Ax and ∂y = By - Ay

Define a third point C such that Cx = Bx + ∂x and Cy = By + ∂y.

C is integral, and is colinear with A and B.

chengsun• 13 years ago

C does not lie on the line segment AB.

eridius2• 13 years ago

Oh my, I didn't notice the word "segment" there. That does change the problem.

nemo16182• 13 years ago

Technically, the problem doesn't specify that the points have to be distinct...

tantalor2• 13 years ago

Yeah that bothered me too. If all the points are (0, 0), does that satisfy the conditions? Does the line segment (0, 0) to (0, 0) "contain" an integer point?

nemo16182• 13 years ago

While we're all solving puzzles, can anyone help me with this one?

No doubt you've doodled this shape in your graph paper before: http://i.imgur.com/oY29sBc.png

What function does this slope approximate? It almost a circle, but not quite.

anonymoushn3• 13 years ago

This is a quadratic Bézier curve http://en.wikipedia.org/wiki/B%C3%A9zier_curve

jacobolus• 13 years ago

Or in other words, it’s a section of a parabola. (As it happens, it’s a parabola tilted 45°, but still.)

fahadkhan4• 13 years ago

sqrt(x)+sqrt(y)=C

chnuschper• 13 years ago

It's y=(sqrt(x) - 1)^2

Consider the function l(t) which gives the appropriate line function f(x) for the line going through (t,0). The function we are looking for can then be defined as c(x) := max(l(t)(x), t in (0;1]). Just solve for t and pop it into l(t), et voila.

jules• 13 years ago

Sorry, I accidentally down-voted you when I tried to up-vote you. This answer is absolutely correct. Here is my very similar derivation:

All lines go through (t,0) and (0,1-t). Now take two such lines, one with constant t and another with constant s and find their intersection. We have:

    y = 1-t - (1-t)/t * x
    y = 1-s - (1-s)/s * x

So:

    1-t - (1-t)/t * x = 1-s - (1-s)/s
    s-t = (s-t)/(st) * x

So:

    x = st

The points on the curve will be generated by the intersection of two almost adjacent lines (this is easy to see geometrically), so we take s =~ t. Then we have:

    x = t^2
    y = (1-t)^2

So we have:

    y = (1 - sqrt(x))^2

Or, my favorite form:

    sqrt(x) + sqrt(y) = 1

nimnam• 13 years ago

choose two integers x and y. These represent the first point on a plain. Only adjacent points can be added i.e. any point can only be 1 integer away from this origin point otherwise there will exist an integer point between the origin point the chosen point. so now we have (x, y), (x+1, y), (x, y+1), and (x+1, y+1). Adding a fifth point anywhere on the graph will make it such that an integer point will exists between two of the selected points.

fahadkhan4• 13 years ago

It doesn't hold. Pick (0,1), (0,2), (0,3), (0,4), (0,5) on the plane z = 0

jonsen4• 13 years ago

Well, you have five integer points on the same line.

fahadkhan4• 13 years ago

"Suppose we arbitrarily choose 5 integer points in a plane.

Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point."

I am not sure what you mean. I have 'arbitrarily' picked 5 integer points on a plane. Yes, they happen to lie on line. All their line segments contain only these integer points.

Perhaps you mean that is line not on "a plane"? In that case (0,0), (0,1), (0,2), (0,3), (0,1) is another counter example.

fahadkhan4• 13 years ago

Or is my assumption "more" means an integer point not in the set of five selected wrong?

thejteam• 13 years ago

If I am remembering correctly, this was on the ARML(American Regions Math League) competition "power question" roughly, say 16-17 years ago. The answers given here from nilkn and the children comments are correct.

graycat• 13 years ago

Okay, we have a solution for the plane. The plane is in two dimensions. Now, for any positive integer n, generalize the problem to n dimensions.

So, now the problem is, for any positive integer n, given any 2^n + 1 n-tuples of integers, at least two of these n-tuples if added have all even components.

mycsc• 13 years ago

LOL. For any two integer points P(i, j), Q(l, m). We have the equation of a line:

y - j = ((m - j) / (l - i)) * (x - i)

Choose x = k * (l - i) + i y = k*(m - j) + j Since i, j, l, m, k are all integers we obtain another integer point. No need 5 points... I may misunderstand the question. :(

counterexample• 13 years ago

I don't see any obvious problem with this counterexample: (0,5), (3,0), (4,6), (7,1), (9,4)

http://farm9.staticflickr.com/8114/8661127874_f9269f0ee5_b.j...

Is there something I'm missing?

jonsen4• 13 years ago

(3,0) ... (6,2) ... (9,4)

So comprehensive testing is what you are missing :-)

Math Puzzle: Integer Points

Related Stories