0 like 0 dislike
0 like 0 dislike
Olympiad level counting

10 Answers

0 like 0 dislike
0 like 0 dislike
So, maybe this is too programming-oriented, but the obvious way to do the computation, with access to a computer, is to count how many subsets there are of each residue mod 5, and update that progressively as you increase the value of n. You can say that there is one subset of the empty set that's 0 mod 5, and no subsets mod anything else. List these as a list of residues, 1 of 0, 0 of 1, 0 of 2, 0 of 3, and 0 of 4, which I will represent with the (space-separated) ordered tuple 0 0 0 0 1. Adding 1 to the set will give a subset with residue 1, or 0 0 0 1 1; adding 2 to the set will give subsets with residues 2 and 3, or 0 1 1 1 1; and in general, adding a new number with residue k takes us from tuple of residues T to tuple of residues T + rot_(k mod 5)(T). You could run this program with a computer no problem, you could write it in Python and have the answer in a fraction of a second after having gotten the program right.

These tuples are clearly secretly polynomials in the ring Z[x]/(x^5-1), and the T + rot_(k)(T) operation is actually multiplication of T by (x^k + 1). I guess this is the same leap of faith as the generating function in this problem, but it seems so very natural to write out the problem like this first and then look at this expression "shift by some amount, with wraparound, and add" and turn it into operations in the ring Z[x]/(x^5 - 1).

So the problem becomes "what is the units place value of (2(x+1)(x^2+1)(x^3+1)(x^4+1))^400 mod (x^5 - 1)?" And so we can evaluate the inside of that expression really fast, and we get 2 (4 + 3x + 3x^2 + 3x^3 + 3x^4) which is _extremely_ convenient for us, because this is actually 2 (1 + 3(1+x+x^(2)+x^(3)+x^(4))) = 2(1+3Z) where Z is the fifth cyclotomic polynomial. Well, of course Z is a zero divisor of our ring, and we find out that Z^2 = 5 Z (rotated copies of Z are equal to Z, and there's five of them). So we're reducing this polynomial mod Z^2 = 5 Z and then evaluating it at Z = 1, sure, great, but that's not a convenient form. But we can just evaluate a polynomial f(Z) at Z = 5 and at Z = 0, and (f(Z) % (Z^(2)-5Z)) % Z - 1) = (f(5) + 4 f(0))/5. If f_0 is the constant term, and f_1 is the Z coefficient, and f_2 the Z^2 coefficient, and so on, we are looking for f_0 + f_1 + 5 f_2 + 25 f_3 + ..., which is 1/5 f(5) + 4/5 f(0).

And since f = 2(1+3Z)^400, we can perform the evaluation before the exponentiation, to get the answer, 2^400(16^400+4)/5 = 2^2000/5 + 2^402/5, a lot of excess but not proportionally a lot more. And we know that the polynomial we get, working backwards, is 2^(400) (16^400-1)/5 Z + 2^(400), so we not only have a nice solution for the n = 5k for some k, but we can perform these multiplications for a relatively short representation of the very large solution for arbitrary n. I do have though that the sixth roots of unity don't multiply out to such a nice polynomial since six is not prime.

Does this zero divisor in the ring I'm talking about give a _natural_ connection to the roots of unity being considered here? Because the generating function for n = 4 is the fifth cyclotomic and has this convenient form?
by
0 like 0 dislike
0 like 0 dislike
I found it easier to come up with a combinatorial solution to this problem, though it's probably secretly the same solution.

The intuition (at least for me) is that, since there is *roughly* a 1/5 chance that a random subset has a sum that is 0 mod 5, we will try to find a bijection f on P(2000) such that (1) all of the orbits have size 1 or 5, (2) on every orbit of size 5, S, f(S), f^(2)(S), f^(3)(S), f^(4)(S) all have different sums mod 5, and (3) it is easy to count the number of fixed points with any particular sum mod 5.

Once you realize that this is all you need, it is not too hard to find one, although it may not be particularly beautiful. Here is one example: Let S be in P(2000). Divide {1, ... 2000} into consecutive blocks of size 5. Find the smallest block, if one exists, such that there are neither 0 nor 5 elements of S in that block. Then rotate the elements in that block by 1 (i.e. apply the cycle (5k 5k+1 5k+2 5k+3 5k+4)). This is clearly a bijection, it satisfies (1) and (2), and it is easy to see that the only fixed points are the sets where all the blocks have 0 or 5 elements. These all have sum 0 mod 5 and there are 2^(400) of them. 1/5 of the remaining subsets also have sum is 0 mod 5. So the total is (1/5)(32^(400) - 2^400) + 2^(400).
0 like 0 dislike
0 like 0 dislike
The video gives a rather big spoiler at the beginning, if you want to try the puzzles sans spoiler, it is:

> What is the number of subsets of {1 ... 2000} whose sum is divisible by 5?

I ended up not using the technique suggested by the spoiler but it definitely helped me think in the right direction. Now am going to watch the rest of the video and see how to solve with the intended technique.

Edit: clarified
by
0 like 0 dislike
0 like 0 dislike
Honestly the complex numbers are a bit of a red herring here. All the relevant properties we use here are purely algebraic. We only really need the algebraic closure of the rationals to make this argument work. This makes it a bit more natural that a discrete problem can be solved with them, as the rationals are obviously relevant to discrete questions. In fact, I believe (I haven't double checked) you could just use the integers with a square and fifth root of unity adjoined to make it even more discrete.
by
0 like 0 dislike
0 like 0 dislike
I watched this video and loved it, and realized there's a reason I never moved beyond the AIME.
0 like 0 dislike
0 like 0 dislike
Why cant you remove all multiples of 5, then {1,4,5} equals {1,4}. Therefore you remove more than 20% allready by the multiplication of 5 and all the once that become the same. Then start with all the dual numbers, but once you find out two numbers are multiplication of 5, remove them too, so {1,2,4,5,7} becomes {1,2,4,7} and then {2,7} as {1,4} is the first two numbers that equal a multiplication of 5.

This way you reduce all of the possible combinations to as little amount of numbers unknown to you as of that moment. Your pool of possibilities decreases really fast.
0 like 0 dislike
0 like 0 dislike
Found the solution, admittedly with the hint that it used complex numbers. I can’t tell whether I should feel accomplished or not.
0 like 0 dislike
0 like 0 dislike
Is it possible to filter a single coefficient, i.e. to find the number of ways to write 5 as a sum of distinct numbers?
0 like 0 dislike
0 like 0 dislike
I’ve been watching 3b1b and brithemathguy as I fall asleep recently
0 like 0 dislike
0 like 0 dislike
I mean the video is right but the relationship with Riemann zeta function and prime counting is a little bit clickbait
by

Related questions

0 like 0 dislike
0 like 0 dislike
79 answers
coL_Punisher asked Jun 21
Regretting majoring in math
coL_Punisher asked Jun 21
0 like 0 dislike
0 like 0 dislike
61 answers
_spunkki asked Jun 21
Just ordered a Klein Bottle from Cliff Stoll. He sent me about 2 dozen pictures of him packing it up. Why is he so cute :)
_spunkki asked Jun 21
0 like 0 dislike
0 like 0 dislike
21 answers
Brands_Hatch asked Jun 21
Is set theory dying?
Brands_Hatch asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
a_dalgleish asked Jun 21
Contributing to the right math area, If all areas are equally curious
a_dalgleish asked Jun 21
0 like 0 dislike
0 like 0 dislike
5 answers
BrianDenver7 asked Jun 21
Is there a nice way to recast riemannian geometry in terms of principal bundles?
BrianDenver7 asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!