Maths Olympiad Prep

Library / /155 of 168

Number theory Difficulty 2.6 Junior Find the answer

The product of NN consecutive four-digit positive integers is divisible by 201022010^{2}. What is the least possible value of NN?

A number or a short expression. Spacing and $ signs are ignored.

Solution

First, we note that 2010=10(201)=2(5)(3)(67)2010=10(201)=2(5)(3)(67) and so 20102=2232526722010^{2}=2^{2} 3^{2} 5^{2} 67^{2}. Consider NN consecutive four-digit positive integers. For the product of these NN integers to be divisible by 201022010^{2}, it must be the case that two different integers are divisible by 67 (which would mean that there are at least 68 integers in the list) or one of the integers is divisible by 67267^{2}. Since we want to minimize NN (and indeed because none of the answer choices is at least 68), we look for a list of integers in which one is divisible by 672=448967^{2}=4489. Since the integers must all be four-digit integers, then the only multiples of 4489 the we must consider are 4489 and 8978. First, we consider a list of NN consecutive integers including 4489. Since the product of these integers must have 2 factors of 5 and no single integer within 10 of 4489 has a factor of 25 , then the list must include two integers that are multiples of 5 . To minimize the number of integers in the list, we try to include 4485 and 4490. Thus our candidate list is 4485,4486,4487,4488,4489,44904485,4486,4487,4488,4489,4490. The product of these integers includes 2 factors of 67 (in 4489), 2 factors of 5 (in 4485 and 4490), 2 factors of 2 (in 4486 and 4488), and 2 factors of 3 (since each of 4485 and 4488 is divisible by 3). Thus, the product of these 6 integers is divisible by 201022010^{2}. Therefore, the shortest possible list including 4489 has length 6. Next, we consider a list of NN consecutive integers including 8978. Here, there is a nearby integer containing 2 factors of 5, namely 8975. So we start with the list 8975,8976,8977,89788975,8976,8977,8978 and check to see if it has the required property. The product of these integers includes 2 factors of 67 (in 8978), 2 factors of 5 (in 8975), and 2 factors of 2 (in 8976). However, the only integer in this list divisible by 3 is 8976 , which has only 1 factor of 3 . To include a second factor of 3 , we must include a second multiple of 3 in the list. Thus, we extend the list by one number to 8979 . Therefore, the product of the numbers in the list 8975,8976,8977,8978,89798975,8976,8977,8978,8979 is a multiple of 201022010^{2}. The length of this list is 5 . Thus, the smallest possible value of NN is 5 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.