When I first announced that I would be doing this feature on a regular basis, Moss asked me a question about whether a person on the game show "Deal or No Deal" should have switched cases at the very end. I noted that it didn't matter whether or not he decided to change and then made a comparison to the famous Monty Hall problem.
I decided this would be a good topic for one of my posts, since it is famous, has an interesting and counter-intuitive solution, and is misunderstood by many people. Even the famous mathematician Paul Erdos (who is widely regarded as the best mathematician of the 20th century) allegedly got this problem wrong the first time he heard it. Part of the confusion is because the problem is ambiguously stated. Depending on the assumptions that are made, the problem can have different solutions.
The Problem
A game show host offers his contestant a chance to choose one of three doors. Behind two of the doors is Nick Punto. Behind the third door is Justin Morneau. After the contestant picks a door, the host reveals a door that contains one of the Puntos. (The ambiguity in the question is in the previous sentance. The assumption is that the host knows what is behind each of the doors and will always reveal a Punto.) The host then offers the contestant a chance to switch doors. Given that the contestant wishes to pick Justin Morneau, should he switch doors? What is the probability of picking Morneau if he switches?
The typical (and incorrect) way that most people approach this problem is like this:
| Door A (Player's Choice) | Door B (Revealed by the host) | Door C (Other unopened door) |
|---|---|---|
| Morneau | Punto | Punto |
| Punto | Morneau | Punto |
| Punto | Punto | Morneau |
We originally started with all three columns, each with equal probability. Since the host has revealed one of the columns, we are left with two columns each still of equal probability. Thus, the probability that we pick Morneau is 1/2 and it doesn't matter if we switch or not.
The above reasoning makes the mistake of assuming that after the host reveals a door, the two remaining cases have equal probability. Unfortunately that is not the case.
There are a number of different ways you can try to explain this, but the actual answer is that if you switch, the probability that you pick Morneau is 2/3. One way is to think about what information has been gained from the host revealing the one door as it pertains to what is behind the door that you picked. When the host reveals one door, all he's telling you is that one of the other two doors contains a Punto. But you already knew that, so he hasn't revealed anything about your door so the probability is still 1/3 that you are right. Since switching is the only other option, it has a probability of 2/3.
Perhaps the simplest way to think about the problem is to make an equivalent statement involving playing cards. You have an Ace of Spades and two other cards. You deal two to a friend and then ask him to reveal a card that is not the Ace of Spades. He then has a 2/3 chance of having the Ace of Spades. Why? Because the chance that he has it hasn't changed since you dealt the cards. If you don't believe me, try the experiment a few times until you understand what is going on.
The formal way to approach this problem is to use conditional probabilities. The assumption is that the host will reveal which ever door contains the Punto if he has a Morneau and will reveal one of the two with a 50% probability. An easy way to view this is to assign numbers to the Punto's so that one door contains Punto #1 and the other contains Punto #2. Then, we may assume that if the host doesn't have a Morneau, he will always reveal Punto #1. Our table above now looks like this:
| Door A (Player's Choice) | Door B (Revealed by the host) | Door C (Other unopened door) |
|---|---|---|
| Morneau | Punto #1 | Punto #2 |
| Punto #2 | Morneau | Punto #1 |
| Punto #1 | Punto #2 | Morneau |
| Morneau | Punto #2 | Punto #1 |
| Punto #1 | Morneau | Punto #2 |
| Punto #2 | Punto #1 | Morneau |
We now see that we have three cases out of 6 that can't happen. The host won't reveal a Morneau, and given the choice between Punto #1 and Punto #2, he will reveal #1. Now, there are 3 options left with equal probability and 2/3 involve Morneau hiding behind door C.
Other Interpretations
The above analysis assumes that the host knows what is behind each of the doors and will never reveal Morneau. Suppose the host is just as clueless as you and will always reveal door B regardless of what is behind it. Well, then we will lose immediately 1/3 of the time when he reveals Morneau. Otherwise, there are 4 cases left each with equal probability so switching and staying each have probability 1/2. Note that our probability of winning without switching is still 1/3 since the host must not reveal Morneau when he opens door B (2/3 probability) and then we must get Morneau in the second part (1/2 probability). This gives a total probability of 2/3*1/2=1/3.
There are other cases to consider as well. For instance, suppose the host really likes revealing door B and will always reveal it unless he knows Morneau is hiding there. In this case, if the host reveals door C instead then we know Morneau is hiding behind door B and switching will get him with probability 1. If not, then we have a 1/2 chance of winning. Note that our overall percentage of winning is still 2/3 if we switch (left as an exercise for the reader).
Suppose that the host still really likes revealing door B, but realizes that this leads to the player always winning when Morneau is behind door B. To counter this, he reveals door B 75% of the time when Morneau is behind door A. In this case, the probability of switching if door B is revealed is (1/3)/(1/3 + 3/4*1/3)=12/21. If the host reveals door C, our chances of winning are (1/3)/(1/3+1/4*1/3)=12/15. These calculations are based on conditional probabilities where the 1/3 on top is the chance that Morneau is behind the given door AND the other door is revealed. The number on the bottom is the total probability that the other door is revealed.
More Doors!
As you might guess, there are many variations of this problem. The more interesting ones however are similar problems where there are more than 3 doors and that the host might reveal more than one of them at a time (or in sequence). For instance, suppose we now have 4 doors (3 Puntos, 1 Morneau). We pick one and then the host reveals 1 and then offers the opportunity to switch from our door to one of the other two. The easiest way to figure out what our probability is if we switch is to realize that the probability that Morneau is behind one of the other 3 doors at the beginning is 3/4. Once we reveal 1 door, the chance that it is behind one of the remaining 2 is still 3/4. Since we have no reason to suspect one door over the other, their probabilities must be equal. So the probability of getting Morneau if we switch is 3/8.
The Moss Question
The question that Moss asked me about Deal or No Deal has already been answered in this post. I will leave it up to you to figure out which of the many examples I gave pertains to that question.
Problems
Both problems are somewhat difficult this week. Since the first one has to do with a game, the second one will be a pure math question.
1. You're playing Let's Make a Deal with 100 doors. The host reveals one door at a time and offers you a chance to switch after revealing each door. Find a strategy that maximizes your chances of winning. Note: Demonstrating that your strategy is indeed optimal is pretty hard, but you should get a good intuition about why your strategy is optimal.
2. Let a_1, a_2, a_3, ... , a_1000, a_1001 be a sequence of integers. Show that there is a consecutive subsequence of integers a_i, a_{i+1}, a_{i+2}, ... , a_{i+k} such that a_i + a_{i+1} + a_{i+2} + ... + a_{i+k} is divisible by 1001. Note: a single integer from the sequence such as a_23 counts as a consecutive subsequence even though it only contains one number.
Rules
- I don’t care if you cheat, but if you do, don’t post the answer.
- Post all solutions/hints in white text (see below for instructions). Please post some dummy text at the beginning so that your solution doesn't show up on the main page.
- Ask questions and state ideas about the problem to generate discussion.
- I will post the solution eventually (assuming I know how to solve it) if nobody else does.
To post the answer in white use the following template below. If you're posting in a gray box, chance "white" to "#f8f8f8"
<font color="white">
before your answer and
</font>
after your answer. You are encouraged to cut and paste that little bit of HTML.
Note to anyone with comment modification privileges: if you see an answer posted and not in all white, please edit the comment to add the whitening HTML.
Re: the first problem
Can you make as many switches as you want? Is he going to open up 98 doors? I'm not understanding.
Yes, he will open doors until there are only 2 left. He opens them one at a time and offers you the opportunity to switch after each one one is opened.
Also, there is still only one Morneau and now there are 99 Puntos.
When it comes to World Series, outside of the Twins wins, I rank 1955, 1960, 1976, 2001, and 2003 among my favorites. I also liked 1957 alot.
If I wait and switch only when there are two left, I should have a 99% chance of winning. The first door had a 1/100 chance of being right. He's opened 98 doors, so 99 times out of 100, the last door should have Morneau. Switch.
If I switch every time, I think that I'm slowly worsening my odds.
This seems pretty easy, but I'm assuming that since this is LMAD, he knows where Morneau is.
Yeah, this is the idea. I'm not sure how to prove it off the top of my head (I have some ideas tho). I'll think about it for a while and get back to you.
In the bottle of a bottle at night
she holds on ever so tightly
A shadow of a melody slightly
Singing so sweet, she go lightly - Josh Davis Band
This may sound like a ridiculous analogy, but I think this just clicked:
Switching doors back and forth is like zig-zagging when you're running from a sniper. In effect, you are dodging the Morneau door, making sure you aren't stuck at it when Monty opens it.
It's a little stretched, but I think it makes sense in my head.
Also, there is still only one Morneau and now there are 99 Puntos.
Stop the madness!! Too many Puntos!!
The 2007 World Series will go down as the greatest World Series played to date between Colorado and Boston.
The 2006 World Series was the best World Series between Detroit and the Cardinals since 1968.
Okay, I'm a little rusty with deriving formulas, obviously. But I know that 500+501 = 1001. I also know that 499+502 = 1001. So, I know that for all odd k, 0 < k <1000, if a_(i+(k-1)/2)=500, then the equation is satisfied.
for k=1, if a(i)=500, then it works.
for k=3, if a(i)=499 then it works, and so forth.
I'm not sure exactly what you're saying here. The idea is that each a_i is some integer. There are no restrictions on what a_i can be, so there's no guarantee that a_i=500 for any i.
Also, we're looking for a consecutive sequence. So for instance, if a_1=2002 then we are done since we can use a_1 has our sequence. If a_7=100, a_8=900, and a_9=1, then the sequence a_7,a_8,a_9 works since a_7+a_8+a_9=1001. On the other hand, if a_4=500, a_5=1, a_6=501, this doesn't form a sequence because none of the consecutive terms sum to a multiple f 1001. We can't just take a_4+a_6 because the terms must be consecutive.
Hopefully this helps somewhat.
When you say that "show that there is a consecutive subsequence of integers", does that mean
1) the designations a_i, a_(i+1), a_(i+2) is consecutive, or
2) the numbers represented by those are consecutive.
I guess what I'm asking, if a_1=8 then does a_2 necessarily have to =9?
The numbers themselves can be what ever they want. We need the subsequence to be in order. See the second and third examples above to clear up an ambiguity.
I counted out his money and it made a pretty penny,
I put it in my pocket, and I took it home to Jenny,
She sighed, and she swore that she never would deceive me,
But the devil takes the women for they never can be easy.
So I can let k=0, and then let a=1001*x where x is any integer, thus insuring a_1 is always divisible by 1001 and there aren't subsequent terms to worry about? Or let any thing where i<1 be =0 so it'll be 1001X+0++0...?
I guess I'm not getting it.
You can't let the numbers be whatever you want. The numbers are arbitrary. For instance, suppose that I give you a sequence of numbers 1, 5, 34534,45, 454545, 11, 98, ...
You need to show me that the sequence has the desired property.
If it helps, think of a small example of the problem where you're looking at a sequence of 3 numbers a1,a2,a3 and you want to show that there is a consecutive subsequence of numbers sum that the sum of them is divisible by 3.
First, I will give you the sequence 1,2,3.
Then, you say that the "sequence" 3 works.
Next, I give you 1,10,1.
Then you say that 1+10+1=12 is divisible by 3.
Next I give you 8,8,7.
Then you say that 8+7=15 is divisible by 3.
Of course, I could keep going on like this. The key is for you to demonstrate that no matter what sequence I give you, you will be able to do this.
Here's an example of a proof for this particular example.
If any of the 3 numbers in our sequence is divisible by 3 then we are done, so assume that none of them are divisible by three.
We will consider the numbers by only looking at their remainder when divided by 3 (i.e. using modular arithmetic).
If all three numbers have the same remainder (either all 1 or all 2), then the sum of all three is a multiple of 3.
If two of them are different, then there is a subsequence where the remainders are either 1,2 or 2,1. In either case, the sum of these two numbers will be a multiple of 3.
QED
Oh, I thought I was creating a sequence to fulfill those requirements. I was always terrible at series and expansions. I quit Physics the day Dr. Petridis put a Taylor Series on the board first day of class that I had no clue what it meant. I switched to history that afternoon.
This solution reminds me of the story of Gauss adding up the first 100 integers in school as a youngster.
I had a math prof in college who used to brag about how smart her son was. Apparently, he figured this out when he was 5, although the way she told the story, it sounded like she basically spoon fed him the answer.
For completeness, Moss knew of the Monty Hall problem (and the solution) when that question was posted. (That had been discussed in an earlier WGOM discussion, some time ago.)
What Moss was really getting at is, is there any information in the Banker's offers on DOND? (Do we know for sure that he does or doesn't know which case has what number??) Moss suggested that some empirical data-gathering might shed some light on whether there is or is not information in the offers.
Yes, I remember you mentioned that the topic had been discussed on here before, which is why I thought it would make a good topic. I didn't mean to imply you weren't familiar with it.
I see what you were asking via the DOND question now. That's something you could test via empirical evidence although there's no guarantee that they won't change strategies based on the fact that people might get the idea what they're doing and gain an advantage. For this reason, I would probably just treat the prizes as being uniformly distributed.
My theory:
Banker's offer = Expected Value of Remaining unopened cases * Factor increasing by round.
Factor looks to increase from about 50% to 110%.
For problem #1, is it 99 Puntos and 1 Morneau? Or is it 100 "prizes" of varying worth??
If the latter, Moss knows the optimal strategy. If the former, Moss has a pretty good guess...
Moss now sees that this was answered above...
The first question you asked is an interesting one too. I haven't thought about before. It seems like the strategy could be quite different then. For instance, if you had 99 Morneaus and 1 Punto, you'd basically want to treat the strategy in the exact opposite manner in order to avoid the shaft.
If you had the same number of each, it could be quite an interesting question also.
Or you could have a variety of different amounts of prize money behind each door (which is the basic general case that you were suggesting).
Actually, thinking about this I'm not sure exactly how it would fit into the context of LMAD if there were a bunch of medium prizes. How does Monty Hall decide which one to open up?
Here's more the problem Moss was considering:
Monty Hall is going to reveal 100 prizes (covering a range of values) in random order. The contestant can choose the most recently revealed prize, or can have Monty continue revealing prizes, but there is no going back to any previously revealed prize.
Without even knowing the "range" of prizes, there is a way to optimize the contestant's strategy here. The odds of getting the top prize are probably a whole lot higher than one would instinctively suspect.
(Hint -- The odds are actually independent of the number of doors, but the contestant needs to know the number of doors in order to optimize the strategy.)
If you want, you can pose that as a future problem for the Nation... Moss was challenged with this one by a calc professor in class one day, derived the strategy that night, and played the game in class the next day. Unfortunately the odds are always against the contestant, and so Moss didn't win. But the prof appreciated the effort, as Moss' strategy was correct.
Oops, Moss mis-spoke slightly. The odds are dependent on the number of doors, but for a reasonably large number of doors the odds approach a quotient that is independent of the number of doors.
As I read further, I found myself getting more and more concerned with the growing number of Puntos in these hypothetical examples. Then by the second comment, we were dealing with 99 of them!
My attempt at the second problem lies below:
I attempted to build a sequence that satisfies the conditions, then showed that it wasn't possible. It's not the most elegant demonstration, but I think it works.
If you have a sequence a_1 through a_j that doesn't contain any consecutive sequence that sums to 0 mod 1001, in order to add another integer, a_{j+1}, one must avoid creating any consecutive sequence that sums to 0 mod 1001.
There are 1001 options for a_{j+1}, 0, 1, 2, ..., 999, 1000 mod 1001. But if a_{j+1} = 0 mod 1001, it becomes its own sequence that is divisible by 1001. Also, if a_{j+1} = 1001-a_j mod 1001, then the sequence [a_j, a_{j+1}] sums to be divisible by 1001. You can also eliminate a_{j+1} = 1001-(a_j+a_{j-1}+....+a{j-k}) mod 1001 for all k < j for the same reason.
None of those eliminated numbers will equal each other because that would require that there be a sequence that sums to 0 mod 1001 (going against our initial assumption). So we have eliminated j+1 possibilities out of the 1001. Filling out the whole sequence, when you try to fill in a_1001, you have eliminated all 1001 possibilities and there is no option to choose which avoids some consecutive sequence that sums 0 mod 1001.
actually, I think a 999-integer sequence is the longest you can have that doesn't contain a consecutive subsequence that sums to 0 mod 1001, but that would have taken me quite a bit more to write it all out, so I didn't bother.
That was fun, can't wait for another one!
Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Morneau! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto!
The argument you have doesn't quite work because there is no guarantee that the sequences a_j+a_{j-1}+....+a{j-k} are distinct. If these are the same for different values of k, then we will certainly have a legal number to assign to a_{j+1} without necessarily generating a consecutive subsequence that sums to a multiple of 1001. You are on the right track though.
Also, there is certainly a 1000 number sequence which does not contain a subsequence which sums to a multiple of 1001. Simply let a_i=1 for every i!
Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Morneau! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto! Punto!
I'm tired of all these m************* Puntos on this m************ math problem!
/S. L. Jackson
there is no guarantee that the sequences a_j+a_{j-1}+....+a{j-k} are distinct. If these are the same for different values of k, then we will certainly have a legal number to assign to a_{j+1} without necessarily generating a consecutive subsequence that sums to a multiple of 1001.
If two subsequences with different values of k sum to the same value mod 1001, there will necessarily be a subsequence that sums to a multiple of 1001.
Say a_{j-k}+ ... +a_j = x mod 1001 and a_{j-m}+ ... +a_j = x mod 1001, where m>k. Then a_{j-m}+ ... +a_{j-k-1} = 0 mod 1001 and the sequence of consecutive terms a_{j-m}, ..., a_{j-k-1} satisfies the condition.
So, when I said that the initial a_1 through a_j contained no subsequences that summed to 0 mod 1001 and picked each subsequent a_{j+k} to satisfy that condition as well, all the sums must necessarily be unique. Then a_1001 will not have any possible value to assign without violating this condition.
Good call on the 1000-integer sequence. I extrapolated some faulty data without thinking it through.
LMAO!!!
This seems like a correct solution to me. I know of a slightly more elegant way to prove it tho.
Now that I don't have my boss lurking over my shoulder I was able to consolidate my thoughts a little bit. This is inspired by my work above, but much more concise:
Assume a_1+a_2+...+a_j != 0 mod 1001 for 1 < = j <= 1001.
Then we have 1001 sums (j = 1, 2, ..., 1000, 1001) and 1000 possible values (1, 2, ..., 999, 1000 mod 1001)
By the Pigeon Hole Principle, there exists k and m such that (a_1+a_2+...+a_k) mod 1001 = (a_1+a_2+...+a_k+a_{k+1}+...+a_m) mod 1001.
By subtracting (a_1+a_2+...+a_k) mod 1001 from both sides we get (a_{k+1}+...+a_m) = 0 mod 1001, which is our subsequence of consecutive entries whose sum is divisible by 1001.
Is that the other solution you mentioned GH? Or is there another way to tackle this?
More on the Pigeon Hole Principle
Yep, that's the one!
For your efforts, here's a math joke. My favorite way of stating the pigeon hole principle:
THE MOST INTERESTING THING ABOUT KING CHARLES I IS THAT HE WAS 5'6" TALL AT THE START OF HIS REIGN, BUT ONLY 4'8" TALL AT THE END OF IT...
BECAUSE OF...
Oliver Cromwell, Lord Protector of England
PURITAN
Born in 1599 and died in 1658
SEPTEMBER
Am I missing something on the first problem? 99 Puntos and one Morneau, and the host never unveils the Morneau until the last move (with only 2 doors remaining)??
1. LMAD with 100 doors. I assume there are 99 Puntos and one Morneau. My goal is to maximize the prob. of getting Morneau.
Each of M doors has a 1/M prior chance of being Morneau. Initially, my set has a 1/M chance of containing Morneau and the Host's set as a (M-1)/M chance. If I never switch, my set's chance is fixed at 1/M and the Host's set's chance is fixed at (M-1)/M, but is distributed over a shrinking number of elements (M-t, where t= 1,2,...,M-1), so that each element has a [(M-1)/M]*[1/(M-t)] chance of being Morneau. Obviously, that per-element chance is maximized when the size of the Host's set is at its minimum.
The share of probability in the Host's set depends on the history of play. If I first switch at stage t*, I get an [(M-1)/M)]*[1/(M-t*)] chance of having Morneau, leaving 1-[[(M-1)/M)]*[1/(M-t*)]] in the Host's set. But this means there is a smaller probability to be spread over the remaining elements in the Host's set after the next elimination than if I had not switched.
The intuition is that I should never switch until the Host's set is minimized, so that the initial (M-1)/M odds are spread over as few elements as possible.
2. Let a_1, a_2, a_3, ... , a_1000, a_1001 be a sequence of integers. Show that there is a consecutive subsequence of integers a_i, a_{i+1}, a_{i+2}, ... , a_{i+k} such that a_i + a_{i+1} + a_{i+2} + ... + a_{i+k} is divisible by 1001. Note: a single integer from the sequence such as a_23 counts as a consecutive subsequence even though it only contains one number.
Obviously, 1001 is divisible by itself. So the one-element subsequence a_i = 1001 fits the bill. So will the two-element sequence 500+501; the 4-element sequence 499+500+501+502; the 8-element sequence 497+498+499+500+501+502+503+504; the 16-element sequence 493+...+508; and so forth.
the sequence 1000+1001+1002 also fits, as does 997+...+1005 and a 27-element sequence 988+...+1014, an 81-element sequence...and so forth.
so what is the general rule? I've got 2, 4, 8, 16, ...-element sequences whose median elements are
500 and 501; 1, 3, 9, 27, ...-element sequences whose median element is 1001. There is a 5-element sequence centered on 2002 (and a 25-element sequence?...125-element sequence?). Ok, I'm stuck as to where to go to generalize.
Was at first
ONLY
MP for Huntingdon
BUT THEN
He led the Ironside Cavalry at Marston Moor in 1644 and won.
Then he founded the New Model Army
And praise be, beat the Cavaliers at Naseby
And the King fled up North like a bat to the Scots. SPOKEN: BUT UNDER THE TERMS OF JOHN PYM'S SOLEMN LEAGUE AND COVENANT, THE SCOTS HANDED KING CHARLES I OVER TO...
Oliver Cromwell, Lord Protector of England
AND HIS WARTS
Born in 1599 and died in 1658
SEPTEMBER
But alas
OY VEY!
Disagreement then broke out
BETWEEN
The Presbyterian Parliament and the Military who meant
To have an Independent bent.
And so...the Second Civil War broke out
And the Roundhead ranks
Faced the Cavaliers at Preston Lancs
And the King lost again, silly thing
I should add that since you put no upper bound on the size of the largest element in the sequence a_1, ..., a_1001, there necessarily will be an infinite number of one-element solutions (all the multiples of 1001), two-element solutions (e.g., 1501+1502; 2502+2503; 3503+3504; etc.) blah blah blah. Right?
Yeah, but there's no requirement (I find to my chagrin) that the integers be consecutive. So, a_1 could be 45, a_2 could be 4566, etc.
Given this, the problem is about adding the remainders of each number in the series when divided by 1001.
Right. The idea here is that you are given an arbitrary sequence. There is no requirement on what a_i is and it totally unrelated to any of the other numbers in the sequence.
The idea is to show that this arbitrary sequence contains a consecutive subsequence which sums to a multiple of 1001. It is not to show that such a sequence exists. It is each to come up with examples of sequences that have this property (as several people have done), it is much harder to show that every sequence has this property.
umm. Ok. hokay. I think I get it. The concept; not the solution.