Sums in an Arithmetic Progression

Let A be any set of 20 distinct integers chosen from the arithmetic progression 1, 4, 7,..., 100. Prove that there must be two distinct integers in A whose sum is 104.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Let A be any set of 19 distinct integers chosen from the arithmetic progression 1, 4, 7,..., 100. Prove that there must be two distinct integers in A whose sum is 104.

Solution

The general term of the progression is in the form 3n + 1. 1 = 3×0 + 1, 100 = 3×33 + 1. There are 34 terms in all. We may split all the terms of the arithmetic progression into 18 subsets: two singletons {1} and {52} and 16 pairs (3n + 4, (33-n)3 + 1}. Of the chosen 19 numbers two are bound to fall into one of the eighteen sets. Since all the numbers are distinct, the singletons are out. Thus two of the chosen 19 numbers form a pair (3n + 4, (33-n)3 + 1}, for some n∈{0, 1, ..., 15}. The terms in a pair sum up to 104.

Reference

  1. 18.S34 Problem Solving Seminar, Fall 2007, MIT Opencourseware

Related material
Read more...

  • 200 points have been cosen on a circle, all with integer number of degrees. Prove that the points there are at least one pair of antipodes, i.e., the points 180° apart.
  • If each point of the plane is colored red or blue then there are two points of the same color at distance 1 from each other.
  • The integers 1, 2, ..., 10 are written on a circle, in any order. Show that there are 3 adjacent numbers whose sum is 17 or greater.
  • Given a planar set of 25 points such that among any three of them there exists a pair at the distance less than 1. Prove that there exists a circle of radius 1 that contains at least 13 of the given points.
  • Prove that among any five points selected inside an equilateral triangle with side equal to 1, there always exists a pair at the distance not greater than .5.
  • Let A be any set of 19 distinct integers chosen from the arithmetic progression 1, 4, 7,..., 100. Prove that there must be two distinct integers in A whose sum is 104.
  • Prove that in any set of 51 points inside a unit square, there are always three points that can be covered by a circle of radius 1/7.
  • Five points are chosen at the nodes of a square lattice (grid). Why is it certain that at least one mid-point of a line joining a pair of chosen points, is also a lattice point?
  • Prove that there exist two powers of 3 whose difference is divisible by 1997.
  • If 9 people are seated in a row of 12 chairs, then some consecutive set of 3 chairs are filled with people.
  • Given any sequence of n integers, positive or negative, not necessarily all different, some consecutive subsequence has the property that the sum of the members of the subsequence is a multiple of n.
  • In every polyhedron there is at least one pair of faces with the same number of sides.

    • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71547809