Quickies
Timothy Y. Chow
1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
g(x^12) is divided by g(x)?
2. Evaluate (1 - 1/2^2)(1 - 1/3^2)(1 - 1/4^2) ... (1 - 1/10^2).
3. A woman, her brother, her son and her daughter (all related by birth)
are all chess players. The worst player's twin (who is one of the
four players) and the best player are of the opposite sex. The worst
player and the best player are the same age. Who is the worst player?
4. In a tennis tournament, n of the participants are women and 2n are men.
Each player plays every other player exactly once. The ratio of games
won by women to games won by men is 7/5. There were no ties. The
value of n is
(a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
5. Let f be a function, defined for all nonzero real numbers, that
satisfies f(x) + 2f(1/x) = 3x for all nonzero x. How many solutions
are there to the equation f(x) = f(-x)?
Number 4 in particular admits a solution involving very little
computation---much simpler than the published solution.
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
Joseph William DeVincentis
> These are all taken from old AHSME papers (but paraphrased).
>
> 1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
> g(x^12) is divided by g(x)?
I don't want to mess with this one right now. I'm sure it probably has
something to do with the fact that g(x)=(x^6-1)/(x-1), but I don't see
how to do it other than the brute force approach.
>
> 2. Evaluate (1 - 1/2^2)(1 - 1/3^2)(1 - 1/4^2) ... (1 - 1/10^2).
Each term (1 - 1/n^2) = (n^2 - 1)/n^2 = (n+1)*(n-1)/n^2.
Thus we have 1*3/2^2 * 2*4/3^2 * 3*5/4^2 * ... * 9*11/10^2.
Collecting all the numerators and denominators:
1 * 2 * 3^2 * 4^2 * 5^2 * ... * 9^2 * 10 * 11
---------------------------------------------
2^2 * 3^2 * ... * 10^2
All the threes through nines cancel out, as do one of the twos and
one of the tens, and we are left with 11/20.
>
> 3. A woman, her brother, her son and her daughter (all related by birth)
> are all chess players. The worst player's twin (who is one of the
> four players) and the best player are of the opposite sex. The worst
> player and the best player are the same age. Who is the worst player?
Three players (the best player, the worst player, and the worst player's
twin (who is not the best player)) are the same age. Obviously the woman
is older than her children, so she is the one not listed. Of the remaining
three, the son and daughter must be the twins, one of whom is the worst player.
The best player is the brother. So the worst player's twin is female, and
the worst player must be the son.
>
> 4. In a tennis tournament, n of the participants are women and 2n are men.
> Each player plays every other player exactly once. The ratio of games
> won by women to games won by men is 7/5. There were no ties. The
> value of n is
> (a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
There are 3n players and 3n*(3n-1)/2 games. The number of games is divisible
by 12 (7/5 ratio). Plugging in the given values for n, there would
be 6*5/2, 12*11/2, 18*17/2, or 21*20/2 games, none of which is divisible
by 12. So the answer is (e), none of the above.
>
> 5. Let f be a function, defined for all nonzero real numbers, that
> satisfies f(x) + 2f(1/x) = 3x for all nonzero x. How many solutions
> are there to the equation f(x) = f(-x)?
Plug in 1/x for x in the given condition to get f(1/x) + 2f(x) = 3/x.
Subtract this equation twice from the given condition to get
-3f(x) = 3x - 6/x, so f(x) = 2/x - x is the only function that works.
2/x - x = -2/x + x ==> 4/x = 2x ==> 4 = 2x^2.
So x = positive or negative square root of two satifies f(x)=f(-x).
There are two solutions.
--
\ Joseph De Vincentis jw...@owlnet.rice.edu /
\ Go Rice! Trevor Cobb for Heisman in 1992!!! /
\ The 1991-1992 NCAA Basketball Champions, the RICE OWLS! /
`------------------------------------------------------------'
Dan Tilque
SPOILERS for 3 & 4 follow.
>3. A woman, her brother, her son and her daughter (all related by birth)
> are all chess players. The worst player's twin (who is one of the
> four players) and the best player are of the opposite sex. The worst
> player and the best player are the same age. Who is the worst player?
The worst player and best player are the same sex and the same age.
Since this can't be the woman and her daughter, it must be her brother
and son. But the worst player has a twin so he can't be her brother.
The worst player is her son.
>4. In a tennis tournament, n of the participants are women and 2n are men.
> Each player plays every other player exactly once. The ratio of games
> won by women to games won by men is 7/5. There were no ties. The
> value of n is
> (a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
(e) none of the above
To satify the ratio 7/5, the total number of games must be a multiple
of 12. In a round-robin tournament, the total number of games is
always a triangular number. If T(y) is the yth triangular number, then
for k players, T(k-1) games are played.
So we look at T(5), T(11), T(17) and T(20) (k-1's corresponding to the
possible answers given) to see if they divisible by 12. They are 16,
66, 136 and 210, none of which are divided by 12. (Three would be an
answer, though.)
>Number 4 in particular admits a solution involving very little
>computation---much simpler than the published solution.
How much computation did the published solution have?
---
Dan Tilque -- da...@logos.WR.TEK.COM
T.M. Speight
These are all taken from old AHSME papers (but paraphrased).
1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
g(x^12) is divided by g(x)?
0.
I think there's an easier way to show this, but what I came up with
was the following:
Put f(x) = 1-x^6 = g(x)-xg(x)
Then f(x)+x^6f(x) = 1+x^12
and so g(x^12) = (1+x^24+x^48)(1+x^6).f(x)
= (1+x^24+x^48)(1+x^6)(1-x).g(x)
i.e. no remainder
2. Evaluate (1 - 1/2^2)(1 - 1/3^2)(1 - 1/4^2) ... (1 - 1/10^2).
11/20
Using the operator P to denote prod_{n=2}^{10}, we have
P(1-1/n^2) = P([n^2-1]/n^2)
= P([n-1][n+1]) / P(n^2)
= P(n-1)P(n+1) / [P(n)]^2
= (10-1)!(10+1)!/2 / 10!^2
= 9!/10! * 11!/10! * 1/2
= 11/20
It is readily seen that, as the number of terms taken tends to +infty,
the product tends to 1/2.
3. A woman, her brother, her son and her daughter (all related by birth)
are all chess players. The worst player's twin (who is one of the
four players) and the best player are of the opposite sex. The worst
player and the best player are the same age. Who is the worst player?
The woman's son.
The son and daughter are the twins, necessarily the same age as the
brother. The woman and her brother could not be the twins, as then one
of her chiildren must be the same age as her.
4. In a tennis tournament, n of the participants are women and 2n are men.
Each player plays every other player exactly once. The ratio of games
won by women to games won by men is 7/5. There were no ties. The
value of n is
(a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
(e) none of the above
There are 3n C 2 games [where C is the combinatorial function
n C r = n! / (n-r)!r! ], i.e. (3n)! / (3n-2)!2!
= 1/2 * (3n) * (3n-1)
From the ratio given, we can deduce that this number should be a
multiple of 7+5 = 12. What we actually get is:
a) 15
b) 66
c) 153
d) 210
Therefore, the answer must be (e).
Alternative answer for smart alecs:
Once it is realised that there is an infinite number of solutions,
none of the unique answers are correct (nobody sets questions like
that). Therefore, the answer must be (e)
5. Let f be a function, defined for all nonzero real numbers, that
satisfies f(x) + 2f(1/x) = 3x for all nonzero x. How many solutions
are there to the equation f(x) = f(-x)?
None.
f(x)=f(-x) => f(1/x)=f(-1/x)=f(1/-x)
Therefore, f(x) + 2f(1/x) = f(-x) + 2f(1/-x) = -3x
But f(x) + 2f(1/x) = 3x
So 3x = -3x
And x != 0 => no solutions
Number 4 in particular admits a solution involving very little
computation---much simpler than the published solution.
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
^^^^^^^^^
Give that man a Z88!
(or other laptop)
90...@uk.ac.cam.eng
(T.M. Speight
at CUED )
Timothy Y. Chow
< 1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
< g(x^12) is divided by g(x)?
[stuff deleted]
<Put f(x) = 1-x^6 = g(x)-xg(x)
<
<Then f(x)+x^6f(x) = 1+x^12
Oops...that should be 1-x^12.
<and so g(x^12) = (1+x^24+x^48)(1+x^6).f(x)
< = (1+x^24+x^48)(1+x^6)(1-x).g(x)
<
<i.e. no remainder
So this doesn't follow. The given solution basically did a "brute-force"
but here's an easier approach.
Use the division algorithm to find polynomials q(x) and r(x) such that
g(x^12) = q(x)*g(x) + r(x) with deg(r) < 5. Let w be any sixth root of
unity other than 1; then 6 = g(1) = g(w^12) = q(w)*g(w) + r(w) = r(w).
Thus the polyomial r(x) - 6 has at least five zeroes, but deg(r) < 5 so
we must have r(x) - 6 identically or r(x) = 6 identically.
< 4. In a tennis tournament, n of the participants are women and 2n are men.
< Each player plays every other player exactly once. The ratio of games
< won by women to games won by men is 7/5. There were no ties. The
< value of n is
< (a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
[Solution deleted]
The solution given here is correct, and is basically the same one I came up
with. (I note that several others also gave pretty much the same solution.)
The published solution let M be the number of games won by men, W the number
of games won by women, calculated the number of games played by men against
men, men against women, and women against women, then slogged through six or
seven lines of obscure algebraic manipulation.
<Alternative answer for smart alecs:
<Once it is realised that there is an infinite number of solutions,
<none of the unique answers are correct (nobody sets questions like
<that). Therefore, the answer must be (e)
Change "The value of n is" to "The value of n could be." Recall my caveat
that the problems were paraphrased.
< 5. Let f be a function, defined for all nonzero real numbers, that
< satisfies f(x) + 2f(1/x) = 3x for all nonzero x. How many solutions
< are there to the equation f(x) = f(-x)?
<
< None.
<f(x)=f(-x) => f(1/x)=f(-1/x)=f(1/-x)
You're confusing the EQUATION f(x) = f(-x) with the claim that f(x) = f(-x)
for ALL x. The correct solution has already been posted by someone else.
Timothy Y. Chow
<Use the division algorithm to find polynomials q(x) and r(x) such that
<g(x^12) = q(x)*g(x) + r(x) with deg(r) < 5. Let w be any sixth root of
<unity other than 1; then 6 = g(1) = g(w^12) = q(w)*g(w) + r(w) = r(w).
<Thus the polyomial r(x) - 6 has at least five zeroes, but deg(r) < 5 so
<we must have r(x) - 6 identically or r(x) = 6 identically.
Oops...of course that should read, "we must have r(x) - 6 = 0
identically or r(x) = 6 identically."
Matthew P Wiener
> 1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
> g(x^12) is divided by g(x)?
The brute force method looks k001 in ASCII:
1000000000001000000000001000000000001000000000001000000000001
111111
-----0000001000000000001000000000001000000000001000000000001
------
1000001000000000001000000000001000000000001000000000001
111111
-----1000000000001000000000001000000000001000000000001
------
2000000000001000000000001000000000001000000000001
...
3000000000001000000000001000000000001
...
4000000000001000000000001
...
5000000000001
...
6
In non-ASCII, this is just arguing, since x^12=g(x)*QUOTIENT+1,
we have x^60+...=x^12*x^48+...=g(x)*QUOTIENT+x^48+x^48+...=
g(x)*QUOTIENT+x^36+x^36+x^36+...=...=g(x)*QUOTIENT+6, where
"QUOTIENT" changes as needed.
--
-Matthew P Wiener (wee...@libra.wistar.upenn.edu)
Gary Ansok
> 4. In a tennis tournament, n of the participants are women and 2n are men.
> Each player plays every other player exactly once. The ratio of games
> won by women to games won by men is 7/5. There were no ties. The
> value of n is
> (a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
>
> (e) none of the above
>
>Alternative answer for smart alecs:
>Once it is realised that there is an infinite number of solutions,
>none of the unique answers are correct (nobody sets questions like
>that). Therefore, the answer must be (e)
Actually, the alternative answer doesn't work in this case, because
there *isn't* an infinite number of solutions (unless you admit
fractional games and/or players, of course). At first glance, it
would seem that if n is a solution, then 2n must also be a solution.
But this doesn't work, because the total number of games played doesn't
scale that way. In addition, as n gets large, the fraction of games
played between two men (and which therefore must be won by men) tends
towards 4/9 -- therefore, the women can win a maximum of 5/9 of the
games for large n. Since 5/9 < 7/12, there is an upper limit on n.
It doesn't take much calculation to show that the maximum value of
n which will allow the women to win at least 7/12 of the games is 3,
and a little trial-and-error shows that 3 is a solution and the only
solution.
Gary Ansok
an...@stsci.edu
Sharma Kunapalli
>From: tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
g(x^12) is divided by g(x)?
Spoiler follows:
g(x) = (x^6 - 1)/(x-1)
g(x^12)/g(x) = (x^72 - 1)(x-1)
--------------------
(x^12 - 1)(x^6 - 1)
x^72 - 1 (x^12 - 1 + 1)^6 - 1
-------- = ---------------------- = A^5 + 6C1 A^4 + 6C2 A^3 + 6C3 A^2 + 6C4 A^1 + 6C5 -------Eqn(1)
x^12 - 1 x^12 - 1
Where A = x^12 - 1 = (x^6-1)(x^6+1)
So Each term of Eqn(1) is divisible by x^6 - 1 except the last (6C5).
So the remainder is 6C5 (x-1) = 6(x-1). QED.
Sharma
--
The opinions expressed here are solely mine. My company has nothing
to do with these.
David G Radcliffe
In article <1992Jan17.1...@galois.mit.edu>,
tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
g(x^12) is divided by g(x)?
In article <1992Jan20....@Warren.MENTORG.COM>,
sha...@scsfs11.Warren.MENTORG.COM (Sharma Kunapalli) writes:
[I have taken the liberty of reformatting the calculation
below so that it fits on an 80 column screen. -- dgr]
g(x) = (x^6 - 1)/(x-1)
(x^72 - 1)(x-1)
g(x^12)/g(x) = -------------------
(x^12 - 1)(x^6 - 1)
x^72 - 1 (x^12 - 1 + 1)^6 - 1
-------- = -------------------- = A^5 + 6C1 A^4 + 6C2 A^3 +
x^12 - 1 x^12 - 1 6C3 A^2 + 6C4 A^1 + 6C5 -----Eqn(1)
Where A = x^12 - 1 = (x^6-1)(x^6+1)
So Each term of Eqn(1) is divisible by x^6 - 1 except the last (6C5).
So the remainder is 6C5 (x-1) = 6(x-1). QED.
- - - - - - - - - -
Your reasoning is correct until the final line. The correct conclusion
is that each term of Eqn(1) is divisible by g(x) except the last.
Therefore, the remainder is 6.
If the remainder of P/Q is R, it does not follow that the remainder
of PS/Q is RS.
I wanted to point out this mistake, because it might not be evident
to all readers. Aside from this, the argument is very well done.
--
David Radcliffe
INTERNET: radc...@csd4.csd.uwm.edu
BITNET: radcliff%csd4.csd.uwm.edu@interbit
David G Radcliffe
Sharma Kunapalli wrote:
. . . .
>
> So Each term of Eqn(1) is divisible by x^6 - 1 except the last (6C5).
>
> So the remainder is 6C5 (x-1) = 6(x-1). QED.
>
This was a mistake, but not for the "reason" I indicated below:
>If the remainder of P/Q is R, it does not follow that the remainder
>of PS/Q is RS.
Let me try to sort it out again. We know that
g(x^12) (x^72 - 1) (x - 1)
------- = --------------------
g(x) (x^12 - 1) (x^6 - 1)
but we cannot equate their remainders, since the divisors are different.
The remainder of the right side is 6(x-1), while the remainder of the
right side is 6.
Liewen Huang
>In article Message-ID: <1992Jan17.1...@galois.mit.edu>
>>From: tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>
>1. Let g(x) = x^5 + x^4 + x^3 + x^2 + x + 1. What is the remainder when
> g(x^12) is divided by g(x)?
>
>Spoiler follows:
>
>g(x) = (x^6 - 1)/(x-1)
>g(x^12)/g(x) = (x^72 - 1)(x-1)
> --------------------
> (x^12 - 1)(x^6 - 1)
>
>x^72 - 1 (x^12 - 1 + 1)^6 - 1
>-------- = ---------------------- = A^5 + 6C1 A^4 + 6C2 A^3 + 6C3 A^2 + 6C4 A^1 + 6C5 -------Eqn(1)
>x^12 - 1 x^12 - 1
>
>Where A = x^12 - 1 = (x^6-1)(x^6+1)
>
>So Each term of Eqn(1) is divisible by x^6 - 1 except the last (6C5).
>
>So the remainder is 6C5 (x-1) = 6(x-1). QED.
>
and actually you did in the last step. The answer is 6.
Here is my way to solve it:
We all know x^n-1=(x-1)*[x^(n-1)+x^(n-2)+x^(n-3)+...+x^2+x+1]
where n is positive integer.
So (x^6)^n-1=(x^6-1)[(x^6)^(n-1)+(x^6)^(n-2)+...+(x^6)^2+(x^6)+1]
=(x-1)*g(x)*[(x^6)^(n-1)+(x^6)^(n-2)+...+(x^6)+1]
So any (x^6)^n get remainder 1 when divided by g(x), that means each term
(x^60, x^48, x^36, x^24, x^12, 1) got remainder 1, and to make the total
remainder 6.
---------------------------------------------------------------------------
Liewen Huang | "Hello."
lie...@sci.ccny.cuny.edu | -Liewen Huang
---------------------------------------------------------------------------
dla...@vax.oxford.ac.uk
>
> < 4. In a tennis tournament, n of the participants are women and 2n are men.
> < Each player plays every other player exactly once. The ratio of games
> < won by women to games won by men is 7/5. There were no ties. The
> < value of n is
> < (a) 2 (b) 4 (c) 6 (d) 7 (e) none of the above
>
> [Solution deleted]
> The solution given here is correct, and is basically the same one I came up
> with. (I note that several others also gave pretty much the same solution.)
> The published solution let M be the number of games won by men, W the number
> of games won by women, calculated the number of games played by men against
> men, men against women, and women against women, then slogged through six or
> seven lines of obscure algebraic manipulation.
>
> <Alternative answer for smart alecs:
> <Once it is realised that there is an infinite number of solutions,
> <none of the unique answers are correct (nobody sets questions like
> <that). Therefore, the answer must be (e)
>
> Change "The value of n is" to "The value of n could be." Recall my caveat
> that the problems were paraphrased.
>
No, there IS only one solution. To see this, check that as n increases,
so does the proportion of games played by men against men. When n = 3,
this proportion is 15/36 = 5/12 exactly.
As in other replies, n can't be 1 or 2 (3 and 15 games respectively),
so the unique answer is n=3 (and all the mixed games are won by women).
RobH