A mysterious Chinese contest problem.
Вставка
- Опубліковано 1 жов 2024
- We solve a nice math contest problem of unknown origin. Our techniques involve generating functions for certain types of integer partitions.
Please Subscribe: www.youtube.co...
Merch: teespring.com/...
Personal Website: www.michael-pen...
Randolph College Math: www.randolphcol...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchga...
Google Scholar profile: scholar.google...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu...
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/s...
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
There are two much shorter solutions which can be explained in a minute.
1) There is a clear bijection between polynomials P satisfying these and pairs of polynomials (Q, R) such that they have coefficients from {0,1} set (possibly zero polynomials) and Q(2)+2R(2)=n. However each nonnegative integer has exactly one representation as value of such polynomials (called binary representation ;p). R(2) can take any of the values {0,1,...,floor(n/2)} and Q(2) is determined by R(2), so the answer is floor(n/2)+1.
2) Second solution is based on "dynamic programming style" recursion and was already explained in previous comments. It just says that f(n)=f(floor(n/2)) + f(floor(n/2)-1), where f(n) is the answer for n and trivial induction proves f(n)=floor(n/2)+1. This recursive relation stems from considerations of constant term whose parity must be the same as parity of n
8:27 Probably to avoid confusion with g and 9
21:01 这是个好地方，可以停一下
Hello folks, hi Michael. Take time for you, be gentle with you. Have a great day.
Consider the system of equations
2yz+zx−5xy = 2
yz−zx+2xy = 1
yz−2zx+6xy = 3
Find the possible values of x, y and z.
thank you for your service
yz=3, zx=6, xy=2
yz*zx*xy=3*6*2
(xyz)²=36
xyz=6/-6
(x,y,z)={(2,1,3),(-2,-1,-3)}
Let yz = u, zx = w, xy = v. Then we can solve for u,v, and w. We get:
Yz= 3
Zx = 2
Xy= 6
Z = +-1 and from there the others follow
(Cursive Q is best q.)
That looks like a STEP question
The solution can also be written as b(n) = 1 + floor(n/2). This takes care of the even and odd cases altogether.
I thought of this way to write it: ( n + 2 - (n mod 2) ) / 2
@@megauser8512 another way: (n+1+[n is even])/2
Where the brackets are the Iverson bracket.
½n + ¼cos(n π) + ¾
Fun fact: this problem appeard also in the second round of Polish Math Olympiad 6 years ago
That's true, it was proposed by me xddd
I started crossing my q’s like that as well when I started working as a TA in undergrad. Was 100% to easily distinguish it from a 9. It was part of the feedback we got during training, though I already crossed my 7s and z’s.
Your method is amazing and generalizable. I learned a lot!
However, there is a much, much simpler way to solve this. Let the solution of the problem to be b(n). You can write P(2) to be C + 2 (another polynomial(2)), and the C goes from 0 to 3. If n is even the you choose C to be 0 or 2, when n is odd, you choose C to be 1 or 3. The b(2n) = b(n) + b(n-1), b(2n+1) = b(n) + b(n-1). Now that we have a recursive definition of b(n), we can do mathematical induction to prove b(n) = 1 + floor(n/2).
In computer science, such problem won't have a closed form answer and is typically solved by dynamic programming (DP).
I think, it can be solved much easier. P(2) = a0 + 2*a1 + 4*a2 + ... = n. Case of even n (n = 2k): a0 must be 0 or 2; for a0 = 0 we have 2k = 2*a1 + 4 * a2 + ... => k = a1 + 2*a2 + ...: k is equal to the same sort of P(2); for a0 = 2 we have k-1 = a1 + 2*a2 + ... This implies that b(2k) = b(k) + b(k-1). Similarly, for odd values b(2k + 1) = b(k) + b(k-1). For 0 & 1 b is obviously 1 (P(x)=2). Then we write a few next values: 2, 2, 3, 3, 4, 4, 5, 5... Then we notice the pattern and prove it by induction.
Ohh that is a nice solution. I had a completely different approach:
Notice that if the coefficients a_k are from {0,1} the answer is simply 1 since P(2) would be the unique representation of n in base 2. Now let E(x) and O(x) be such that E(x^2) + x*O(x^2) = P(x), that is if P(x) = sum a_k x^k then E(x) = a_(2k) x^k and O(x) = a_(2k+1) x^k. Then we have P(2)=E(4)+2*O(4). Notice that the coefficients of O and E are from {0,1,2,3} so E(4) and O(4) are the unique representation of two numbers a,b in base 4. So the number of polynomials P is equal to the numbers of a,b such that n=a+2b. Since we can set a:= n- 2b (n is fix) we just count the number of possible b, such that n>=2b and this is just all the bs from {0,1,..., floor(n/2)} so the answer is floor(n/2)+1
Very nice! I was trying to find a way to use the base 2 and 4 representations but I couldn't find a way.
I got the recursion:
u(n) = 0 if n < 0 or n is not an integer
u(0) = 1
u(n) = u(n/2) + u((n-1)/2) + u((n-2)/2) + u((n-3)/2)
I noticed that P(2) for just coefficients 0,1 is just a binary representation of a number. You can include 2,3 by encoding:
n = a + b
a and b are binary numbers
if the dth coefficient is {0,1,2,3} then the dth binary digits of a,b are as follows
0: a_d = 0 b_d+1 = 0
1: a_d = 1 b_d+1 = 0
2: a_d = 0 b_d+1 = 1
3: a_d = 1 b_d+1 = 1
So the question reduces to how many ways can you split a number into 2 numbers.
When n is odd, b is always even and a is always odd. Note that whenever n is odd, the 0th coefficient must be 1 or 3, leaving a_d = 1
When n is even, b and a are both always even. Note that whenever n is even, the 0th coefficient must be 0 or 2, leaving a_d = 0.
This removes half of the possible splits.
For example, for n = 10, 1+9 is not valid because b_0 = 0 always. Only 0+10, 2+8, 4+6 and reflections are possible.
"1996 IN CHINA"
Aye commander we goin in
If I was doing this, I'd rewrite to ceil((n+1)/2) instead, but it's the same thing
21:38 I'm disappointed you didn't write this as floor(n/2+1).
Interesting. Here goes my solution, that i think is a bit simpler than that presented here (sorry for my gramatical errors) : Lets define A_n = {P(x) is in Z4[x], P(2)=n}. Notice that every polynomial in Z4[x] can be writen, in a unic way, as
P(x)=x P1(x^2) +P2(x^2)
with P1 and P2 in Z4[x]. Let be n_1= P1(4) and n_2 =P2(4). Notice that, because each natural can be writen in just one way in base 4, that P1 and P2 are the only polynomials in Z4[x] that are equal to n1 and n2, respectively, when evaluated in 4, so we have that the problem of finding the size of A_n is equivalent to the problem of finding the number of partitions of n as
n=2*n1+n2
We have that a generating function for A_n is
G(x)=1/((1-x)*(1-x^2))
We have then, when finding the coeficients of G(x), that
A_n = (2 n + 3 + (-1)^n)/4
Which, when setting n = 2n' and n = 2n' +1, gives the same result as yours.
A faster way to finish is to find the number of ways to pick n1, which is floor(n/2)+1, then n2 is given for free.
That seems to be basically the same idea as I got: a(0) + 2 a(1) + 4 a(2) + 8 a(3) + 16 a(4) + 32 a(5) = [..., a(4), a(2), a(0)] + 2 [..., a(5), a(3), a(1)], where [..., d2, d1, d0] is the non-negative number with digits ..., d2, d1, d0 when represented in base 4. The two [...] correspond to your n2 and n1 respectively. So we shall have n = 2 n1 + n2, where n1, n2 >= 0. Now we have something easier to count.
You did it with a bit more formalism, but that's the way I solved it as well.
That is really cool. I'm not used to generating functions. Really nice tool.
Hi,
For fun:
5 "and so on, and so forth", 1 "and them so on and so forth",
4 "all the way up to",
2 "so, I'll go ahead and",including 1 "so, I'll go ahead and",
6 "I'm going to go ahead and", or may be "I'll may be go ahead and" for some of them,
3 "let's go ahead and",
1 "we can go ahead and",
2 "great",including 1 "ok, great",
2 "ok, nice",
1 "so no what I want to do",
1 "what I want to notice",
and the final "and that's a good place to stop".
My solution:
1. Write the polynomial as P(x) = \sum_{n>=0}{l_n * x^n}, where the {l_n} are 0, 1, 2, or 3.
2. Note how P(2) = \sum_{n>=0}{l_{2n} * 2^{2n}+ l_{2n+1} * 2^{2n+1}} = \sum_{n>=0}{l_{2n} * 4^n} + 2 * \sum_{n>=0}{l_{2n+1} * 4^n}.
3. Now the two sums can just be read as non-negative integers in base-4, hence there is a bijection between the set of non-negative integers and the set of {l_{2n}} (and {l_{2n+1}}).
4. This reduces the problem to finding the number of non-negative integer pairs (N,M) satisfying n = 2N + M. It is then trivial to show that the answer is ceil((n+1)/2).
EDIT: messed up the answer.
Found in a few minutes: Let f(n) be the number of polynomials P(x) with coefficients in {0,1,2,3} such that P(2) = n. This is just a (redundant) binary representation with digits {0,1,2,3}. Obviously, for parity reasons, f(2n+1) = f(2n), i.e. just increase the last digit of a representative of 2n to obtain 2n+1. And by induction on the last digit, f(2n) = f(n) + f(n−1), f(n) corresponding to last digit = 0 and f(n−1) corresponding to last digit = 2. The first n values suggest f(2n+1) = f(2n) = n+1; then f(2n) = f(n) + f(n−1) is easily checked: if n = 2k+u with u ∈ {0,1}, then f(n) + f(n−1) = k+1 + k+u = n+1 = f(2n).
I've been done similar question but with slightly different settings. But I'm sure this problem has same basic idea with the past similar question i've been done.
Realize that the polynomial P(2) forms a "binary number" since we can express each polynomial as series of power of two. Now the problem is how we can set the coefficient which can only valued 0,1,2,3 to 0,1 so that it can forms "the binary number we know" (since if the coefficient still valued 0,1,2,3 it is the base-4 number rather than binary/base 2 number)
To solve the problem, we can set ai = bi + 2ci where bi and ci = 0 or 1. Hence the polynomial can be decomposed into two different polynomial , lets say P(x)=B(x)+2C(x) where B(x) coefficients are bi and C(x) coefficients are ci.
Thus by the definition of binary number B(2) and C(2) are exactly the binary number we know in math. Hence the number of P(2)=n is the number of different configuration of sum of the two binary number B(2) and 2C(2) (which is unique for each different configuration)
The rest of solution is just ordinary combinatorial calculations.
Ye I started crossing my qs after playing DDLC.
Yuri Best girl
this problem would be so much easier if the polynomial was evaluated at 4 instead of 2 xD but this method of generating functions is really a nice way of proving that the representation of integers in any natural number basis is unique
I got a completely different solution using recurrence. If we denote number of such polynomials for a given n as f(n), then f(n)=z(n)+j(n)+d(n)+t(n) where z(n) is number of such polynomials that start with a_0 equal to 0, j(n) is s.t. starts with 1, d(n) -- 2, t(n) -- starts with 3. Then we can express each one of these as some formula of f(n) using the parity of n. That gives us the recursion of f(2n)=f(2n+1)=f(n)+f(n-1). The answer can be guessed and is proved easily with induction, being f(2n)=f(2n+1)=n+1
It was from looking at the generating formula - the number of even numbered between 0 and n/2 i think - (because you are allowed to add a number of 2s and then have to use 1s to complete - and there is only one way once a number of twos have been chosen (one way i of you are still less than or at n) - then you have an even number plus a number that form n and so how many even numbers are there? Floor(n/2)+1 so that’s the value. I always liked the fact that combinatorics allowed for different ways of arguing the result.
You had polish raid They dislike your solution because you used generating functions and for them solution with generating functions is not "normal"
but i like your solution
At the end solution can be presented with elementary functions without piecewise definition
This nine dislikes probably come from other polish viewers
6:28-7:00 me every time i get presented a problem
This was also in Romania TST for IMO 1994.
That way of writing "q" was commonly to make it clearly distinguishable from printed g when mixed with cursive.
I write my q like this as well, and never noticed until now that you do the same! I do this because 1. my handwriting is terrible so it'd otherwise be hard to distinguish from p and g, and 2. because it looks really cool
Finally china
More integrals, fourier series, etc.
14:15 In that infinite product, how do the last two numbers of the numerator cancel out? If you check for big numbers, you clearly see they keep increasing....
For any particular value of n, the last 2 numbers (if we go far enough out) will be too large to contribute to the coefficient of q^n. We can apply this reasoning for every term b(n)q^n.
Used different approach (apparently similar to others here) :
notice n=sum(a(i) 2^i) is also = a(0)+2(sum(a(i) 2^i)=a(0)+2m and m is written the same way as n
if n is even, then n=0+2x or n=2+2y
so p(n) = p(x)+p(y) = p(n/2)+p(p/2-1)
if n is odd, then n=1+2x or n=3+2y
so p(n) = p((n-1)/2)+p((n-3)/2)
after trying some values, we notice n jumps by one every even number.
claim: p(n) = floor(n/2)+1
which can be easily verified by induction using above two equalities.
My shot on this. Use binary notation of coefficients as a_i = c_i + 2d_i. Then we write p(2) as sum(c_i*2^i) + 2*sum (d_i*2^i). The sums are unique representations of integer nonnegative numbers. Thus, one can write n = c + 2*d as equivalent task for some nonnegative integers c,d.
Since, numbers are nonnegative there is finite set of partitions.
If n is even, c has to be even, too. Thus we have c= 2*k. And n/2 = k + d. There are n/2 + 1 variants.
If n is odd, we have c=2*k+1 and
(n-1)/2 = k + d. There are (n+1)/2 variants in this case.
Once you’re at 15:37, you can note that the form will be b(n)=A+B*n+C*(-1)^n, and you can plug in b(0)=1, b(1)=1, b(2)=2 to find B=1/2, A=3/4, and C=-1/4 which is the same answer that Michael got.
any integer number has a binary representation which can be thought of a polynomial evaluated at 2 with coefficients {0,1}, thus the problem reduces to counting the ways to partition n as sum of an integer and an even number , namely, n=n1+2*n2 (so that the coefficients the polynomial after addition is from {0,1,2,3}). The corresponding generating function is 1/(1-q)*1/(1-q^2). one can also use the residue theorem from complex analysis to arrive at the same final result (as an alternative way to partial fractional expansion for the generating function).
Oh well, I proposed this problem on Polish Mathematical Olympiad when it was used on its second stage 6 years ago, too bad it was featured in China years ago xd
This was definitely a tricky one. That generating function would imo have required past experience with a problem similar to this.
Let A be a subset of R
We can partitioned A into sequence of interval (In)n>=0 ?
You can try one of math Problem in Chinese college entrance examination.
Generating functions are just a masterpiece of an idea.
What a solid problem! Great stuff
Really enjoyed this video! I don't have a lot of experience with generating functions so this solutions was enlightening.
Same here. Very neat tool.
2nd comment!!!
Will you continue the series on partitions?
Love your channel a lot. Thanks
Sir make videos on indian Olympiad
6:37 taking a huge sniff of chalk dust
I have a question about the telescoping part. You didn't prove that the numerator tends to 1 in the limit, it is only true if |q|
Good point. The fact is, in many of these integer partition arguments involving generating functions, the "q" is considered a formal variable -- it doesn't take any values ever.
@@MichaelPennMath Completely irrelevant to the original comment, but the telescoping product isn't infinite because you have a finite number of parts (1, 2, ..., 2^m) and so, you would have numerator left overs.
Generating functions!!!
You are awesome ❣️
two-tuple lol
And please start a series for math contests too sir....
For my math Olympiad practice , I cone to this channel...
14:09 is wrong. Why would it be an infinite telescoping product if you have a finite number of parts (ie 1,2,..., 2^m)?
I don't understand what you mean. n goes to infinity. Why do you say finite number of parts?
@@otakurocklee The generating function in this case is equal to the product of 1 + q^k + q^2k + q^3k, where k is in the set {1, 2, ..., 2^m}. Obviously, that set's cardinality is finite. Therefore, we cannot have an infinite telescoping sum.
@@otakurocklee If you still don't understand, let me explain it in a different way. If it were infinite, that means that since each coefficient of 1+q^k +q^2k + q^3k is 1, then each b(n) is definitely greater than 0. However, that is a contradiction because every integer K > 3+3*2 +3*2^2 + ... + 3*2^m cannot be partitioned under such circumstances, and so b(K) must be 0.
@@georget2063 What is m here? I don't understand where it is coming from. The coefficient of q^k in the generating function gives the number of polynomials such that P(2) = k. If the coefficient of q^k is zero, then that means there are no polynomials such that P(2) = k. That doesn't make sense for any integer k. Any integer can be represented in binary... that gives us at least 1 polynomial with coefficients 0,1. for example 23 = 2^4 +2^2 +2^1 + 2^0, which is 1 polynomial (x^4+x^2+x+1) that satisfies the conditions. Same for any integer. So the coefficient of q^k has to be greater than or equal to 1 for every k.
@@otakurocklee m is the degree of P. Honestly, I don't see how you don't understand. Do agree with me that the greatest number that can be written as a sum of at most 3 powers of 2 in {1, 2, ... 2^m} is 3*(1+2+...+2^m)? If, you do understand then you should also understand that for any K greater than that number, b(K) is 0. But if the telescoping sum were infinite, there would exist G's > 3(1+2... + 2^m) such that b(G) > 0, which can't be. So the product is not infinite.
Shouldn’t this be part of the overkill series? Isn’t it obvious that ANY n can be expressed by an infinite number of those polynomials using only 1 and 0 as coefficients (and using an arbitrarily long “tail” of 0 coefficients) since that will be the same thing as the binary expression of n? 🤔
Or is that cheating? The statement of the problem does not explicitly say that polynomials only differing in infinite tails of zeros is to be viewed as the same polynomial.😏
cool question