From child prodigy to chief scientist

Immediately afterwards, Qian Feng quickly wrote a problem on the blackboard.

Place several "rooks" on an 8x8 chessboard such that:

1. Each square must be controlled by at least one vehicle (vehicles can attack horizontally or vertically);

2. No two vehicles can attack each other.

Find the minimum number of cars needed. Prove your conclusion.

The answer to this problem is not difficult to find. Xu Xiao thought about it for a while and realized that there should be at least 8 cars, and each car should be placed on the main diagonal.

However, proving this conclusion accurately is not as easy as one might imagine.

As Xu Xiao was pondering how to prove it, a student in the front row said:

"It's easy to see using a greedy algorithm that at least 8 cars are needed. To prove it, let's assume we can put k cars, where k is a positive integer less than 8. This would leave 8-k rows and 8-k columns empty..."

Listening to the classmate's proof, Xu Xiao also looked like he suddenly understood.

This student used proof by contradiction. If the assumption is true, then there would be at least one cell that is not controlled by any car, thus contradicting the assumption.

If Xu Xiao were given enough time, he might be able to come up with the same method, but he definitely wouldn't be able to think as quickly.

"Is this the strength of competition students? It's terrifyingly strong."

Even though Xu Xiao was concentrating on thinking, he still seemed to be somewhat behind them.

"What He Muzhou said is very good; this line of thinking is completely correct."

Despite receiving praise from Qian Feng, He Muzhou showed no joy, as if he had long been accustomed to it.

As one of the strongest students in this year's Yucai Math Competition team, He Muzhou has almost secured a spot in the competition, and even has a great chance of entering the provincial team in the future.

Of the questions Qian Feng assigned yesterday, He Muzhou got all of them right, except for one that was very difficult.

Meanwhile, Xu Xiao's mind was still on the previous question.

"Actually, this kind of problem can also be solved using code."

As a programmer in his previous life, solving problems with code was a professional habit for Xu Xiao.

For relatively simple problems like this, using code might seem unnecessary, but the advantage of code is its versatility; even if the problem becomes more complex, similar code can still be used to solve it.

However, computers are not allowed to be used in high school math competitions, which makes Xu Xiao's skill seem somewhat useless.

"Of course, we can continue to promote the chess problem we just discussed, for example, by replacing the rook with a bishop, a knight, or a queen, etc."

"Because these problems involve too much computation, everyone can go back and think about the modeling approach; there's no need to calculate the specific results."

He Muzhou immediately began to think about it. Among these options, the problem of replacing the car with an elephant was relatively easier to consider.

The car moved horizontally and vertically, so we can use the idea of ​​bipartite graph matching to model it. The elephant moves along a diagonal line, which can also be modeled using the idea of ​​bipartite graph, but we need to distinguish between black and white squares.

But if you replace the piece with the queen, the problem immediately becomes completely different.

Because the queen can move horizontally, vertically, and diagonally, the complexity of the problem is increased by more than an order of magnitude.

After thinking for a while, He Muzhou had no choice but to put these issues aside for the time being.

Meanwhile, Xu Xiao had already written down the solutions for each problem on a draft paper.

"The Queens Problem can be approximated using algorithmic thinking. You can write a DFS search program and then optimize it using pruning."

"For horses, we can use graph theory coloring to model them, which is a variant of the four-color theorem. The code shouldn't be too difficult to write."

It was a pity that he didn't have a computer on hand, otherwise Xu Xiao could have calculated all these problems in no time.

Xu Xiao was able to understand most of the following lessons and keep up with Qian Feng's pace.

Although Xu Xiao considers himself to be of average talent, at least when he is focused, he is not falling behind these competition students.

At this moment, Qian Feng wrote a new question on the blackboard.

Let S be a subset of {1, 2, ..., 2005}, and the sum of any two distinct elements in S is not divisible by 9. Find the maximum possible number of elements in S.

"This is a problem from the original competition. Please take a look at the problem first, and then I will explain the solution."

This time, Xu Xiao reacted much faster than before. After listening to the previous lessons, he had gained a certain understanding of the problem-solving techniques for this type of question.

"First, divide these numbers into 9 categories based on their remainders when divided by 9, then calculate the number of elements in each category..."

Before Qian Feng could even begin his presentation, Xu Xiao had already written down the result "893" on the draft paper.

A few seconds after Xu Xiao finished his calculations, He Muzhou arrived at the same result.

Qian Feng didn't give the students much time to think; he immediately began explaining after a minute or two.

Unsurprisingly, Qian Feng's approach was basically the same as Xu Xiao's, and the final calculation results were exactly the same.

…………

After a morning of math competition training, Xu Xiao still felt a bit tired.

The training intensity for math competitions is already quite high, not to mention that Xu Xiao had been in a state of focus the entire morning, and his brain hadn't had much rest.

If this happens again in the afternoon, Xu Xiao will probably have a hard time handling it.

After class, Xu Xiao went to the podium.

"Teacher, may I bother you for a moment?"

"Oh, young man, what's on your mind?"

Qian Feng was quite interested in Xu Xiao. In his previous high school math competition teaching, he had never taught such a young child before.

"I'd like to know what textbooks I need to study to prepare for the math competition?"

"No problem. There's quite a lot of material to learn, so you'd better take some notes."

"Okay, sure."

Xu Xiao took out the notebook she had just used in class, randomly flipped to a page, and prepared to take notes.

"Math competitions are mainly divided into four modules: algebra, number theory, combinatorics and geometry."

"For the algebra section, take a look at 'High School Mathematics Competition Training Course' and 'The Secret of Inequalities' first."

"For number theory, I recommend Elementary Number Theory. Just read the first four chapters..."

Qian Feng recommended more than ten textbooks in a row, but these were only the basic ones.

"If you can master these skills, you should have no problem with the first test, and you should be able to answer one or two questions in the second test as well."

"But if you want to tackle the more difficult questions in the second round, or aim for the provincial team, you'll need to learn even more and more complex things."