pjbooks Chapter 30: Math Competition Training!
Chapter 30: Math Competition Training!
P.S.: Hey everyone, it's Tuesday today, another crucial day for reviewing recommendations! Please keep reading! Please keep reading! Please keep reading! I'm saying it three times because it's important, thank you!
In May, the weather in Baling was already unbearably hot.
The ceiling fan in the classroom whirred and hummed, blowing out a hot breeze mixed with the smell of chalk dust, making everyone feel drowsy.
Han Chuan's seat was by the window, which was slightly better. More than half a month had passed since he had registered for both the math and physics competitions.
For the past two weeks, his life has been like a birthday cake, sliced into pieces: a piece for the math teacher, a piece for the physics teacher, a piece for Ge Jun, a piece for Zhou Peiyuan...
The bell rang for evening self-study. Han Chuan took his books and walked towards the laboratory building opposite the teaching building.
Monday, Wednesday, and Friday belong to mathematics; Tuesday, Thursday, and Saturday belong to physics.
Today is Wednesday, and he has to go to the laboratory building to attend classes and receive training on competition-related problems with the top students in the elite class who are participating in competitions.
On the second floor of the experimental building, in the math competition classroom, more than a dozen students had already arrived and were now sitting quietly in their seats reading books.
Han Chuan found his seat, took out a competition textbook from his bag, and started reading.
A short while later, Gong Qin, the math competition coach in charge of leading them, walked in holding a thermos.
He didn't speak or teach; instead, he picked up the chalk and wrote two questions on the small blackboard in the classroom.
After finishing writing, Gong Qin threw the chalk on the podium, dusted off his hands, glanced at the students in the classroom, and spoke in a flat tone as if he were talking about what to eat in the cafeteria today.
"Today's training consists of two number theory competition problems."
"You have one evening study session to complete this task. If you can finish it, you can have free time during the second evening study session. If you can't finish it, you can continue working on it during the second session!"
This is his teaching style. Unlike other competition teachers who like to lecture, he prefers to let students understand on their own.
There are rewards and punishments. If you can complete the task, you can move around freely; if you can't, you continue to sit on the bench.
Upon hearing Gong Qin's words, a slight commotion arose among the students participating in the competition, and everyone looked up at the blackboard.
Han Chuan, too, looked up at the two questions on the blackboard.
I. Prove that for any positive integer n, there exists a multiple of n whose digits are all 0 or 1.
II. Proof: For any positive integer n, there always exists a multiple of n whose decimal representation contains odd digits (i.e., only the digits 1, 3, 5, 7, and 9).
After glancing at the question, Han Chuan first picked up his pen and copied the question from the blackboard into his notebook before he began to think about it.
Both of these problems are number theory problems, and number theory is one of the most unreasonable branches of competitive mathematics.
Unlike geometry, which can be solved with auxiliary lines, or algebra, which has fixed formulas to apply, number theory relies on number sense, inspiration, and an almost mystical insight into the structure of numbers.
Sometimes, when you get stuck on a problem, it's not because you lack the knowledge, but because you're not looking at it from the right perspective.
Han Chuan first looked at the first question.
Prove that for any positive integer n, there exists a multiple of n whose digits are all 0 or 1.
After staring at it for a while, Han Chuan's first thought was to find a number consisting of 0s and 1s and make it divisible by n.
But the next moment, he quickly ruled out this approach.
Since n is any positive integer, there is no pattern to follow.
This basic approach of finding the answer through pure calculation is clearly not feasible unless he has a supercomputer.
"Interesting. This proposition seems unremarkable, but it actually appears to be quite difficult."
Looking at the question, Han Chuan muttered something to himself, his eyes showing interest and excitement.
After these days of learning, he now enjoys using his existing knowledge to challenge his limits even more.
If you can solve a problem that you couldn't solve before, the reward will be as joyful as getting an injection of endorphins.
He pondered for a moment, then reread the question.
If constructing multiples doesn't work, how about linking them to congruence?
Thinking it over, he quickly wrote a line of equations on the clean white paper.
Consider the sequence ak = 11...1 {k ones} where k = 1, 2, ..., n+1. The remainders of these (n+1) numbers modulo n can only be 0, 1, ..., n−1.
By the pigeonhole principle, there exist two distinct subscripts i.
[Calculate the difference aj - a i = ....]
Han Chuan pondered as he looked at the equations on the draft paper.
If a number is to be a multiple of n, and all its digits are either 0 or 1, then it can be written as the sum of several powers of 10.
But the problem here becomes: can we find several numbers that are powers of 10 whose sum is exactly divisible by n?
"The remainder of 10 modulo n..."
The phrase flashed through his mind like a match striking light in the darkness, bringing him to his senses.
Pick up the pen, and put pen to paper.
Lines of calculations were quickly written on the draft paper.
「如果考虑数列10^1， 10^2， 10^3……一直到10^(n+1)，这n+1个数分别模n取余数。」
"The remainder modulo n has only n possibilities—from 0 to n-1. If n+1 numbers are put into n boxes, according to the pigeonhole principle, at least two numbers will have the same remainder."
"Take the remainders of n+1 numbers all 1s modulo n as objects, and the possible values of the remainders (0, 1, ..., n−1) as drawers. Then perform divisibility checks on them, and that's it."
The answer was calculated very quickly.
Since gcd(n, 10) = 1, n and 10^i are coprime, therefore n | R. And since every digit of R is 1, R is a multiple of n!
"Done!"
As the pen fell to the ground, Han Chuan grinned.
This question is really misleading; the core difficulty lies in constructing an auxiliary sequence.
If he were to use the general method of constructing multiples to solve the problem, he wouldn't be able to figure it out even if he spent an entire night working on it.
However, if we first construct an auxiliary sequence and then transform the 'existence' problem into a 'repeated remainder' problem, it becomes very easy to prove!
Having solved the first question, Han Chuan quickly turned to the second.
[Proof: For any positive integer n, there always exists a multiple of n whose decimal representation contains only odd digits (i.e., digits from 1, 3, 5, 7, and 9).]
This problem is similar to the conclusion that it consists of only 0s and 1s, but it is restricted to all odd numbers.
Han Chuan tried to solve it using the pigeonhole principle, but quickly encountered difficulties.
Because the difference between two numbers of the form 111…1 will produce a trailing 0, and 0 is an even number.
Clearly, this question is significantly more difficult than the first one.
He vaguely sensed that the approach to the second question should have some kind of symmetry with that of the first question.
If the first question uses powers of 10, the second question might require some kind of variation.
As he pondered, he mentally dissected and reassembled the proposition, attempting to approach it from different angles.
Then...then he got stuck.
Looking at the messy equations on the manuscript paper, Han Chuan rubbed his temples with a headache.
He felt he had completed half of it, and could sense that the answer was not far ahead, but a thin fog separated them, preventing him from seeing the path clearly.
Just then, the math textbook he had brought over and placed on the corner of the table lit up slightly, and a line of text appeared.
It's by Ge Jun; his penmanship is as sharp as a knife.
"You're such a brainless idiot! You even figured out that powers of 10 can construct numbers consisting entirely of zeros, why couldn't you think of a different approach!"
"stupid!"
Clearly, seeing Han Chuan stuck on the second question for so long, the book spirit Ge Da Ye in the textbook couldn't stand it anymore and appeared a line of text: "Educate" him.
.....