Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On rainbow arithmetic progressions. | On rainbow arithmetic progressions Maria Axenovich Department of Mathematics Iowa State University USA axenovic@ Dmitri Fon-Der-Flaass Department of Mathematics University of Illinois at Urbana-Champaign USA and Institute of Mathematics Novosibirsk Russia flaass@ Submitted Jun 23 2003 Accepted Dec 2 2003 Published Jan 2 2004 MR Subject Classifications 11B25 11B75 Abstract Consider natural numbers 1 n colored in three colors. We prove that if each color appears on at least n 4 6 numbers then there is a three-term arithmetic progression whose elements are colored in distinct colors. This variation on the theme of Van der Waerden s theorem proves the conjecture of Jungic et al. 1 Introduction In this paper we investigate the colorings of sets of natural numbers. We say that a subset is monochromatic if all its elements have the same colors and we say that it is rainbow is all its elements have distinct colors. A famous result of van der Waerden 3 can be reformulated the following way. Theorem 1. For each pair of positive integers k and r there exists a positive integer M such that in any coloring of integers 1 M into r colors there is a monochromatic arithmetic progression of length k. This theorem was generalized by the following very strong statement of Szemeredi 2 . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R1 1 Theorem 2. For every natural number k and positive real number S there exists a natural number N such that every subset of 1 N of cardinality at least SN contains an arithmetic progression of length k. One can ask a dual question. Assume again that 1 n is colored into r colors. Can we find an arithmetic progression of length k so that all its elements are colored in distinct colors Next we call such colored arithmetic progressions rainbow AP k . In general the answer to this question is No for r log3n 1J. The following coloring c of 1 n given in 1 demonstrates this fact. Let c i max ợ i is divisible by 3q . This coloring .