The author mentions at one point that he was unable to solve a problem because he didn't memorize the formula for the Euler totient function in order to count the number of numbers relatively prime to 9999.
...but its actually an interesting (and not super difficult) exercise in its own right to figure this out even if you don't know the formula. Encourage you all to give it a shot.
SPOILERS: 9999 = 3^2 * 11 * 101, so first subtract out the multiples of 3 (3333 of them), the multiples of 11 (909 of them), the multiples of 101 (99 of them). Note that we've now double-subtracted multiples of 33 (303 of them), multiples of 303 (33 of them), multiples of 1111 (9 of them) so add these back. Finally subtract 1 to not count 9999 itself.
I guess my point is that the purpose of these problems is not to separate out people who know specific tricks from people who don't—its to separate out people who can reason their way through difficult mathematical problems and people who can't.
The difference for you is that you're doing it as a fun exercise. With contest math, you're drilling these formulas and tricks so you can reproduce them quickly on a timed exam. If you know both of the facts listed in the essay then you can knock off this question in a minute or two.
Trying to come up with everything from scratch could take a lot longer and be very frustrating when you've got other problems waiting for you to solve.
I’m trying to put myself into the shoes of the blog’s author. I just finished my math degree. It wasn’t at an elite school. I enjoy math for recreation though I’ve never been a contender in contest math.
I think I can understand why the author complains about drilling for math contests. I think it’s the same reason high level chess players complain about opening book. Drilling is not fun and it reduces the creative element of solving the actual problems.
The fact that he wasn’t doing it for fun but for college admissions plays a lot into it as well. That kinda pressure can really kill the fun.
Except for the intense speed pressure to create artificial rankings for competition, "drilling" is "practice for understanding".
OP says in the article that he didn't understand what he was doing, but was just trying to imitate people who did to try to appear brilliant. And he claimed that most students in club were like this, due to parenting and teaching that was focused on resume building for ignorant Admissions Offices, instead of focused on learning.
It really isn’t. The essay makes this point as well. The acquaintance of his who was most interested in math dropped out of the contest team. He went on to become a mathematician because he was actually interested in understanding higher math and how things fit together.
Drilling is just practicing computational tricks to be able to execute them by heart. This would be true regardless of the amount of time pressure or lack thereof. I’ve taken many math courses that had exams in this style and I always hated them. I much prefer trying to figure out a proof I’d never seen before. For any real work, those computations would be done by a computer anyway.
You need to memorize things in order to be effective
You need to be able to match patterns to things you've seen before. You need to develop an intuition.
LeBron James much prefers to slam dunks, but he still has to practice the game ad condition.
The totient formula isn't the hard part of the problem.
The test has a very short time limit (for the difficulty of the problems), and has many gruelingly complicated problems,so if you dont have the formulas down cold, you'll burn out during the contest.
Of course, if you don't care about silly speed-mathing contests, you can enjot the problems at a leisurely pace.
What's especially fascinating is that the core of the problem is a generalization of the totient computation, so understanding the inclusion-exclusion construction of totient is very helpful to the problem, while simply memorizing the formula is a misdirection.
OP missing this point shows that he really was doing this for all the wrong reasons. He should have done FIRST or science bowl instead.
Completely agree, I also liked the problem and thought it was conceptual as far as these things go.
Asking for N mod 1000 was another cute twist that was meant to get you thinking about the divisibility properties of the totient function - "hmm, so (p-1) always divides \phi(n) for all prime factors p of n, how convenient..."
That's a cute coincidence that 1000 divides (11-1)(101-1), but I doubt it was intentional. The test writers didn't have much choice unless they chose a different base than 5+5.
For every distinct prime factor p (so, of 9 is a factor, use 3 not 9), only (p-1)/p of the natural numbers ≤ n are relatively prime to it. Pime. This overcpunts nothing, since prime factors are relatively prime to each other. (Proving this requires some analysis of remaimders / modular arithmetic. But working an example shows the pattern).
This gives a formula, phi(n = Sum (p_i ^ e^i)) = n • Product ((p_i -1)/p))
This also shows how OP (and maybe the coach) missed the point of math team.
...but its actually an interesting (and not super difficult) exercise in its own right to figure this out even if you don't know the formula. Encourage you all to give it a shot.
SPOILERS: 9999 = 3^2 * 11 * 101, so first subtract out the multiples of 3 (3333 of them), the multiples of 11 (909 of them), the multiples of 101 (99 of them). Note that we've now double-subtracted multiples of 33 (303 of them), multiples of 303 (33 of them), multiples of 1111 (9 of them) so add these back. Finally subtract 1 to not count 9999 itself.
phi(9999) = 9999 - 3333 - 909 - 101 + 33 + 303 + 9 - 1 = 6000
I guess my point is that the purpose of these problems is not to separate out people who know specific tricks from people who don't—its to separate out people who can reason their way through difficult mathematical problems and people who can't.