In iirc 8th grade, I've placed high in the final round of a Moscow-wide physics competition, incidentally hosted by MSU. My classmate, who placed even higher, and myself have received an invitation to enroll in the MSU-affiliated maths/physics focused school (#2, the schools in Moscow are all numbered semi arbitrarily).
As far as I recall, every time I'd go to one of those competitions bulk of the people in later rounds were from #2 and #57, another math-focused school. The kids from other schools who did well were, I assume, largely scooped up by those targeted schools.
EDIT:
Oh, and the maths/physics/etc. competitions started at neighborhood level, so every school would typically send at least a few kids, and encourage the kids who were better at the subjects to do well. I went to neighborhood biology/history/etc. competitions too, but never did very well. I assume whoever did well in those and went into next rounds could go on to enroll into a different set of specialized schools :)
Also, some parents did enroll their kids straight into those schools, but I dunno how prevalent that is. They are very ability focused, unlike US private schools that I've heard of where money and helicopter parenting seem to be a major factor.
As a side note, my friend did enroll into #2, and I didn't go because was too lazy to commute 40mins one way when my own school was a 3-minute walk (it was a subway trip for him as is, so I'd like to think that was the difference ;)). We've both done well for ourselves but he's definitely much better at math now.
Yep, can confirm, such system existed in other large Soviet cites as well. I also graduated from one such maths and physics oriented school. Compared to regular public schools the education level was much higher, and not only in those subjects. The studying there was extremely intense, 6-day week (which was standard in USSR at that time), long hours, and tons of homework to keep you busy late at nights and weekends (read: Sunday). Best graduates were expected to go further study in MSU or other top universities. The rest of us who went to local universities found themselves bored in the first years of their studies.
Now, living in a western European country I found in a hard way that the key to a better education for your talented kid hides in your bank account.
Don't get me wrong, I in no way support Soviet system, but this was one of the things they did good.
No one taught me this in school, but if you add up the digits (5+7=12) and the result is divisible by 3, then so is the original number. It works recursively.
Induction seems like an odd way to prove this. Do you need to preform induction over all the numbers that are not multiples of three?
The converse claim (every multiple of 3 has a digit sum that is a multiple of 3) is a more natural one for induction, though that's not the most standard proof there either.
If induction is the only tool you have then it’s ok. What you really want is modular arithmetic. If you don’t have modular arithmetic then pricing it directly is hard:
n = Sum(d_k 10^k)
Let S = sum of digits = Sum(d_k)
n - S = Sum(d_k (10^k - 1))
But (10^k - 1) = ((9 + 1)^k - 1) = ((1 + k*9 + (2 choose k)*9^2 + ... + 9^k) - 1)
by binomial expansion so is divisible by 9.
Therefore n - S is divisible by 9, so n is divisible by 9 iff S is.
The same is true when you replace divisibility by 9 with divisibility by 3.
I remember being asked this in an interview for a place at university and I solved it by induction (which was all I had) and was then shown this direct proof.
Odd if you're looking for the simplest way to prove that. Less odd, perhaps, if you're looking for something that can be proved simply using induction, in order to make students do their first proof by induction.
I don't remember precisely what it was we were asked to prove. It may have been the converse.
As dan-robertson mentioned in another branch, you don't even need induction - you can sidestep it by writing X = sum_i x_i 10^i and noticing that all the 10^i are 1 modulo 9 (and therefore modulo 3).
"What is Mathematics" by Courant and Robbins teaches some more divisibility tricks, might be useful sometimes. btw, we learned divisibility by 3 in 5th or 6th grade (not the proof, of course)
> and I didn't go because was too lazy to commute 40mins one way when my own school was a 3-minute walk
Hah, that mirrors my wife’s experience in Riga - she came second and first in national physics competitions for two years, and was twice invited to enroll in a different school - but she stayed put, because she didn’t want to have to change trams twice, rather than a direct trolley bus. She’s happy with her choice.
EDIT: Oh, and the maths/physics/etc. competitions started at neighborhood level, so every school would typically send at least a few kids, and encourage the kids who were better at the subjects to do well. I went to neighborhood biology/history/etc. competitions too, but never did very well. I assume whoever did well in those and went into next rounds could go on to enroll into a different set of specialized schools :) Also, some parents did enroll their kids straight into those schools, but I dunno how prevalent that is. They are very ability focused, unlike US private schools that I've heard of where money and helicopter parenting seem to be a major factor.
As a side note, my friend did enroll into #2, and I didn't go because was too lazy to commute 40mins one way when my own school was a 3-minute walk (it was a subway trip for him as is, so I'd like to think that was the difference ;)). We've both done well for ourselves but he's definitely much better at math now.