2
$\begingroup$

A year is a leap year if it is either

(i) a multiple of 4 but not a multiple of 100, or

(ii) a multiple of 400.

For example, 1600 and 1924 were leap years while 2200 will not be. Find the number of leap years between 1000 and 3000 inclusive.

I'm not sure what's the best way to approach the question. These are some ideas I have, but not getting anywhere.

1) Find the number of years between 1000 and 3000 which are divisible by 4. (I'm not sure which is the best way to find the answer for this) $\frac{3000}{4} - \frac{1000}{4} + 1$?

2) Find the number of years between 1000 and 3000 which are divisible by 4 and 100 and subtract from it the answer from 1.

3) Find the number of years between 1000 and 3000 which are divisible by 400.

The answer given is 485.

EDIT: The main problem I had with this question is that I wasn't sure if I was double counting the leap years. For the first condition, where the set of years should be a multiple of 4 but not 100, I didn't see clearly why we should subtract N(1000,3000,100) from N(1000,3000,4).

Let's say the set N(1000,3000,4) contains elements {A,B,C,D,E,F}. The set N(1000,3000,100) could have elements {A,C,X,Y,Z,..}. Why is it okay to subtract then?

EDIT 2: Can I use generalized principle of inclusion and exclusion for this question if I let $P_{1} <=>$ divisible by 4, $P_{2} <=>$ divisible by 100 and $P_{3} <=>$ divisible by 400? I tried but I'm not sure exactly how to find the answer using this.

$ \omega(0) = |S| = 3000-1000+1 = 2001 $

$ \omega(1) = \omega(P_1) + \omega(P_2) + \omega(P_3) = 501 + 21 + 5 = 527 $

$ \omega(2) = \omega(P_1,P_2) + \omega(P_2,P_3) + \omega(P_1,P_3) = 21 + 5 + 5 = 31 $

$ \omega(3) = \omega(P_1,P_2,P_3) = 5 $

$\endgroup$
1
  • 1
    $\begingroup$ You seem to have a complete solution, what's missing? $\endgroup$ – Yuval Filmus Sep 26 '14 at 13:31
1
$\begingroup$

Let $N(a,b,m) = |\{a \leq x \leq b : m \mid x\}|$. As you mention, the number of leap years in the range $\{a,\ldots,b\}$ is $N(a,b,4) - N(a,b,100) + N(a,b,400)$, so it remains to compute $N(a,b,m)$. Let $a'$ be the smallest multiple of $m$ which is at least $a$, and let $b'$ be the largest multiple of $m$ which is at most $b$. Then $N(a,b,m) = N(a',b',m)$. We can come up with the formulas $a' = m\lceil a/m \rceil$ and $b' = m\lfloor b/m \rfloor$. Now it is easy to see that $N(km,lm,m) = l-k+1$. Now you have all the tools to compute the number of leap years in a range $\{a,\ldots,b\}$.

$\endgroup$
6
  • $\begingroup$ Thanks for the clear explanation! I made a edit to the question on the part I'm still slightly unclear about. $\endgroup$ – Faizal Ismaeel Sep 29 '14 at 0:19
  • $\begingroup$ There are four types of years: Type A: not divisible by 4. Type B : divisible by 4 but not by 100. Type C: divisible by 100 but not by 400. Type D: divisible by 400. You want $B+D$. The formula counts $(B+C+D)-(C+D)+D = B+D$. $\endgroup$ – Yuval Filmus Sep 29 '14 at 0:22
  • $\begingroup$ Is it possible to to split the years into 3 types: $P_{1} <=>$ divisible by 4, $P_{2} <=>$ divisible by 100,$P_{3} <=>$ divisible by 400 and use the inclusion exclusion principle? $\endgroup$ – Faizal Ismaeel Sep 29 '14 at 7:37
  • $\begingroup$ This would be completely equivalent to the strategy I'm outlining, but perhaps more confusing, because this case is so degenerate (the properties imply each other in a sequence). $\endgroup$ – Yuval Filmus Sep 29 '14 at 13:20
  • $\begingroup$ I see. I tried using it, but I'm stuck. Kindly see my edit. $\omega(P_1,P_2)$ is the union of the set of numbers divisible by 4 and 100 right? Thanks! $\endgroup$ – Faizal Ismaeel Sep 29 '14 at 16:05

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.