Meet Math Challenges with Confidence

Let us discuss an interesting combinatory problem. Here is the question.

A local high school math club has 12 students in it. Each week, 6 of the students go on a field trip.

(a) Jeffrey, a student in the math club, has been on a trip with each other student in the math club. Determine the minimum number of trips that Jeffrey could have gone on.

(b) If each pair of students have been on at least one field trip together, determine the minimum number of field trips that could have happened.

Any clue on how to work with this problem?

Firstly, this is a combinatorial problem. The questions are looking for a number — a naive way is to make a schedule and count for the number.

However if we arbitrarily make a schedule, even in the best effort, can we guarantee that the minimum number of trips is reached in our scheduling (both for Jeffery, and for the total number of trips). No. The minimum can not be reached that easily.

A better way is to show there is a minimum n; for less than n trips, the restricting condition becomes impossible. Take the case for Jeffery (referring to question (a)). Suppose Jeffery has been in two trips. In the first trip, he was with five students A1, A2, A3, A4, A5; in his second trip, he was with B1, B2, B3, B4, B5 (assume only Jeffery took both these trips). Concludingly, he has been with ten other students. Adding himself, we counted 11 students. But recall there are 12 students, so there is a C who has not been in any of these two Jefferey’s trips. Therefore, 3 is the minimum number of trips if, Jeffery has been together with any of the other 11 students for at least one trip – 3rd trip is necessary for Jeffery to be with C together

The question (b) has a more involved nature. First point to consider: in what way can count to ensure any two students have been together in at least one field trip? Arguing for the minimum, we know too less trips will not generate an arrangement ensuring the condition: any two students are together at least once; however, if we do reach the minimum number of trips, would that condition be satisfied? — that is the second point to consider. If we want to guarantee the condition satisfied, then the obvious way is to actually make a schedule so as to check that condition — in this example, we need to show that in some n trips, any two of the 12 students have been in a field trip together. So the clues are provided for your — dear reader; would you like to carry it further?

We leave to our readers to complete this question. ** Reference solutions will be posted soon. **

Take a look at the following question.

Determine all integers a for which \frac{a}{1011-a} is an even integer.

Hint: Let \frac{a}{1011-a} = 2d . Solve for a in terms of d.

(In the usual sense — if seeking for real roots, Diaphantus equations has infinitely many roots; but is has finite many roots if only the integer roots are sought.)

Suppose the expression \frac{a}{1011-a} gives an even integer 2d (d is an integer). This leads to

a = 2022 d – 2ad, which is (2d+1)a + (2) \cdot 1011d so a = (2) \frac{1011 d}{2d+1} = (2) \frac{(3)(337)d}{2d+1} -- -- (*)

Note a is integer and d is integer. By inspecting (*): the basic clue is that any prime factor of (2d+1) (in denominator) must be cancelled by the factors in the numerator — so that the quotient a is an integer. Note d and 2d +1 are co-prime; and numbers 3 and 337 are both prime numbers.

Therefore 2d +1 must take one of the following values: \pm1, \pm3, \pm 337, \pm1001 .

Here comes the last step to find the value of a. We leave it to the reader to complete.

By the way, can you see that in all solutions, a must be positive (i.e. a >0)? Yes, that is indeed true; otherwise if a <0, then the quotient will not be an integer — in fact, the absolute value of quotient will be between 0 and 1 (please figure out why).

Suppose there are three sequences {a_n}, {b_n}, and {c_n}, where n=1, 2, 3 … . These sequences are defined recursively, and with inter-dependence; for example, the definition of b_n depends not only on b_n-1, but also on a_n-1 or c_n-1. Suppose we are to work out some inequality relations among a_n, b_n, and c_n. In what way can we make it?

Here is one such question, as follows.

Let p, q be any two distinct positive real numbers such that pq = 5.

Define A_0 = -1 - p - q, B_0 = p+q+pq, C_0 = - pq <0.

For n \geq 1 , define

Show that 1+B_n > (-C_{n-1} +1)^2 >0 for any n \geq 1 .

Let us first calculate B₁. Using the recursive definition, we have that B_1 = (B_0)^2 - 2 A_0 C_0 \\ = (p+q+pq)^2 - 2 (-1-p-q) (-pq) \\ = p^2 + q^2 + p^2 q^2 >=0. Note it is obvious that B₁ is non-negative. Continuing in this way, any B_n shall be non-negative.

Let us set the next immediate goal as 1+B_1 > (-C_0 +1)^2 . Bringing the value of C_0 = -pq , and noting that B_1 = p^2 + q^2 + p^2 q^2 , the goal of proof is equivalent to 1 + p^2 + q^2 + p^2 q^2 > (1-pq)^2; which shall be obvious as p^2 + q^2 > 0 > -2pq .

We list the values of {A₀, B₀, C₀; A₁, B₁, C₁}, in terms of p, q, as follows: (previously, we show how B₁ can be calculated; the read can try to find A₁, C₁, similarly)

A_0 = -1-p-q, B_0 = p+q+pq, C_0 = -pq, \\ A_1 = -1 - p^2 -q^2, B_1 = p^2 + q^2+p^2 q^2, C_1 = -p^2 q^2 .

The quick-minded reader must have found that, when advancing the index by 1, the following schema holds true (where p^*, q^* are two distinct positive real numbers), A_{n-1} = -1-p^*-q^*, C_{n-1} = -p^* q^*, \\B_{n-1} = p^*+q^*+p^*q^*, \\ A_{n} = -1 - (p^*)^2 -(q^*)^2, C_{n} = -{p^*}^2 {q^*}^2, \\ B_{n} = {p^*}^2+{q^*}^2+{p^*}^2 {q^*}^2.

So, a straightforward generalization for the proof of 1+B_1 > (-C_0 +1)^2 , leads to the proof of 1+B_n > (-C_{n-1}+1)^2 .

We have two remarks in sequel.

The following question comes from 2024 CSMC (Canadian Senior Math Contest) – Part B, Question 2. (There are three sub-questions, a, b, and c. We present only a. and c.)

a. The quadratic equation x²-2x-1= 0 has solutions x= r and x = s. Determine integers b and c for which quadratic equation x² + bx + c = 0 has solutions x = 2r + s and x = r + 2s.

c. Suppose that A₁=-6, B₁ = 10 and C₁ = -5. For each positive integer n \geq 2 , let \\ A_n = 2 B_{n-1} – (A_{n-1})^2, \\ B_n = (B_{n-1})^2 – 2 A_{n-1} C_{n-1}, \\ C_n = -(C_{n-1})^2 .

Prove that the polynomial f_{100}(x) = x^3 + A_{100} x^2 + B_{100} x + C_{100} has three distinct positive real roots.

Now we look into how to solve the question above.

Analysis for a.

It shall hold x² + px + q = (x-r) (x-s) if r, s are two roots of the equation. By expanding the right hand side, we obtain x² – (r+s)x + rs. Now comparing it to x² + px + q to find [this is indeed Viete’s Theorem]

r+s = -p, (rs) = q ~---~ -- (*)

Using (*) for the question in 2a), it holds that r+s = -p =2, and (rs) =q = -1; meanwhile we have -b = (2r+s) + (r+2s) = 3(r+s) etc. from which the value of b can be calculated.

Analysis for c.

We intend to show that for any n, equation f_n (x) = x^3 +A_n x^2 +B_n x + C_n has three distinct roots. (This is actually stronger than what the question is asked; yet if this is indeed true, then a clear path can be paved leading all the way to f₁₀₀ (x). )

If one of the three roots (call it x₁) is known (preferably an integer), then we have a linear factor (x – x_1) (by Factor Theorem), and the co-factor (quadratic) can be worked out with polynomial division. For the said quadratic co-factor, we argue it has real distinct roots by checking that the discriminant is positive, and be ensured neither root of the quadratic factor equals x_1 .

Note we find x=1 is a root for f_n(x) (so let x₁ =1.) And f₁(x), f₂(x), … each has three distinct roots. [Details to be worked out]

Next step: The readers are trusted to work out the solution to a. (analysis for a. was already given). For question c., in addition to the analysis given above, there are some gaps need to be filled. Please attempt to work them out by yourself, yet if you get stuck or want to check whether you have done it right, check out the next post. Using Factor Theorem (cont.) – selected details for a CSMC question