4
$\begingroup$

Let:

$$S := \{1,2,3,\dots,1337\}$$

and let $n$ be the smallest positive integer such that the product of any $n$ distinct elements in $S$ is divisible by $1337$. What are the last three digits of $n$?

I'm having a bit of trouble with this problem: the context is that my prof. gave this as a 'extra' exercise to me to do for fun.

Any help would be appreciated, thanks!

$\endgroup$
  • $\begingroup$ I find it interesting that your prof gave it as an exercise, yet only asks for the "last three digits of $n$", as opposed to the value of $n$. This is very similar to a Brilliant problem that I just posed this week, where 1337 is replaced with 2013. $\endgroup$ – Calvin Lin Jun 18 '13 at 0:04
  • $\begingroup$ That is pretty interesting, I didn't think to ask where he got the question from - I'll ask him next time I see him. $\endgroup$ – kvmu Jun 18 '13 at 6:02
3
$\begingroup$

$1337=7\times191$ and there are $190$ numbers with a factor of $7$ before $1337$ and $6$ numbers with a factor of $191$ before $1337$.

Suppose you've chosen all the numbers in the set except those that have a factor of either $7$ or $191$. That'd be $1337$ minus $1$ (for $1337$) minus $6$ (for numbers with factor $191$) minus $190$ (for numbers with factor $7$). $1337-1-6-190=1140$. Now the worst possible condition you can have is that you've chosen all the number that have a factor of $7$ but no number with a factor of $191$ which are $190$ in total. This essentially means that you have all the $7$s in the list but no number of factor $191$ to pair them up with $7$ resulting in some multiple of $1337$. So now you have $1140+190=1330$. Now you need any one of the remaining 7 numbers to get a product divisible by $1337$. So $1330+1=1331$. Therefore the last $3$ digits of $n$ are $331$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Hint: A first step is to factor $1337$. Why does that help?

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ So we factor 1337, to get the (7)(191) - this helps us determine the lower bound for $n$. But the problem requires a certainty that if we pick $n$ numbers from the set, it will definitely be divisible by $1337$. I can also determine that there are 190 numbers before 1337 that is divisible by 7 and 6 numbers before 1337 divisible by 191. For the product to be divisible by 1337, I need to pick one of both of those numbers that are divisible by 7 and 191 (at least). $\endgroup$ – kvmu Jun 17 '13 at 3:37
  • 2
    $\begingroup$ So how many numbers can you take without getting both a 7 and a 191? $\endgroup$ – vadim123 Jun 17 '13 at 3:38
  • 1
    $\begingroup$ @vadim123: an excellent followup. $\endgroup$ – Ross Millikan Jun 17 '13 at 3:39
  • $\begingroup$ @vadim123 Ah - I understand now! Thanks! $\endgroup$ – kvmu Jun 17 '13 at 3:41
  • $\begingroup$ Thanks very much, my pleasure. $\endgroup$ – vadim123 Jun 17 '13 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.