Vista previa del material en texto
Ariel University Center of Samaria
Department of Computer Science and Mathematics
P.O. Box 3, Ariel 44837, ISRAEL
ד "בס
Department of Computer Science and Mathematics
Solutions.
1. a. It follows from the inequality
!
1
!
12
n
n
k
n
nk
that 0
!
1
lim
!
1
lim
2
n
n
k
n
nk
nn
and
consequently 0
!
1
lim
2
n
nk
n k
.
b. From the inequalities
n
nk
n
n
n
n nntdt
tk
2 2
2 ;2lnln2lnln
11
and
n
nk
n
n
n
n
n
n
nntdt
tk
2 2
12
1 ;
1
12
ln)1ln()12ln(ln
1
11
it follows that
n
nk
n k
2
.2ln
1
lim
2. We split the cube into 8 small cubes which sides are
2
1
such that the
vertices of the little cubes are in the middle points of the edges. By placing 9
points inside, at least two of them will be in the same little cube. The length
of the diagonal in this cube is
2
3
2
1
2
1
2
1
222
will be the biggest distance
between these two points in the little cube.
3. a. It is clear that
)!1(
1
!
1
)!1(
11
)!1(
nnn
n
n
n
,
n
k
n
nk
k
S
1 )!1(
1
1
)!1(
and .1lim
)!1(1
n
n
n
S
n
n
b.
1
1
3
1
32
.
)1ln(
2
2
,
1
,
11
1ln
n
n
dt
t
t
dt
t
dx
t
xt
x
dx
x
Let us use series to
get estimates: ).1(2
1
)1ln(
),(
2
)1ln(
23
3
2
O
t
t
t
t
tO
t
tt
For ]1,0(t we
obtain )1(ln
4
1
)1(ln
2
11)1ln( 1
1
1
1
3
OnnOt
t
dt
t
t
n
n
. Thus
n
nn n
O
n
nn
dx
xn 1
.2
1
)ln
4
1
(2
lim
1
1ln
1
lim
4. If we set ,2 tx then
2
0
2
0 00
2
0
2 .
sinsin
2
1sinsin
2
1sin
2
1
sin dt
t
t
dt
t
t
dt
t
t
dt
t
t
dt
t
t
dxx
Ariel University Center of Samaria
Department of Computer Science and Mathematics
P.O. Box 3, Ariel 44837, ISRAEL
ד "בס
Department of Computer Science and Mathematics
We obtain that
2
0 0
2 .0
11
sinsin dt
tt
tdxx
5. Let us write the derivative to the our function
,...)( 2
210
n
nxaxaxaaxp we obtain 1
21 ...2)(' n
nxnaxaaxp . The
graph of tangent at the point ))(,( 00 xpx is of the form ))((')( 000 xxxpxpy .
Denote by ),( ba the coordinates of the point Q. Substituting them into the
equation of the tangent we get
)...( 0
2
02010
n
nxaxaxaab ))(...2( 0
1
0021 xaxnaxaa
n
n
. If 1n , the
coefficients of n
x0
in the right and left hand sides cannot be equal. It means
that actually we have an algebraic equation of n -th order for finding 0x , and
consequently it is impossible that the number of such the points ))(,( 00 xpx is
greater than n .
6. Let a(x,y,z) be a polynomial which defines sphere A of the form
x
2
+y
2
+z
2
+linear part=0.
Similarly, let b, c, d, be polynomials defining spheres B, C, D.
Difference of two such polynomials is linear, since quadratic part is
cancelled out. If both polynomials are zeroes at certain point, then their
difference is also zero.
Hence difference of two spherical polynomials is a plane, which contains
the circle of their intersection. Hence the equation of 4 planes, mentioned in
the problem, are a-b, b-c, c-d, d-a .
Hence the sum of normals to the planes (whose coordinates are coefficients
of zyx ,, in the equations of those planes) is 0.
If 3 normals are linearly dependent, they lie in one plane and are orthogonal
to the same vector, then the 4
th
normal, which is minus their sum, is also
orthogonal to the same vector. In this case all normals are orthogonal to the
same vector hence the line parallel to this vector will be parallel to all 4
planes.
If 3 normals are linearly independent, then 3 planes have a common point
(x,y,z) and its coordinates satisfy the equations of these 3 planes. It is clear
that the coordinates of this point satisfies also to the equation of the
equation of the 4
th
plane. Hence all 4 planes have a common point.
7. Factorials grow faster than powers, so sin converges.
(a) Suppose it has an element bigger by absolute value than 1. Multiplying
sin matrix by a unit vector of standard basis, you get a vector whose length
is greater than 1.
Ariel University Center of Samaria
Department of Computer Science and Mathematics
P.O. Box 3, Ariel 44837, ISRAEL
ד "בס
Department of Computer Science and Mathematics
Bring A to diagonal form by orthogonal matrix. sin A will be brought to
diagonal form as well. On diagonal of sin A you shall have
1 2sin ,sin ,...,sin N where 1 2, ,..., N are eigenvalues of A.
So, in this coordinate system, length of each vector is not increased when
vector is multiplied by sin A.
But the transfer to another coordinate system was done by orthogonal
matrix, so lengths remain the same.
(b) No. Take matrix
0 1
1 0
I
, then I
2
= minus unit matrix, hence
1 1 1 1
sin 1 ...
3! 5! 7! 9!
I I
.
8. If we are forced to take cells with numbers > 2008, the cell 2008 should
have two pieces on previous stage. It may happen only if one step before the
end we had 1 piece in cell 2008 and two pieces in cell 2007.
This may happen only if 2 steps before the end we had a piece in cell 2008,
a piece in cell 2007, and two pieces in cell 2006. When we continue to
replay the game in reverse order, we see that 2007 steps before the last
move we have one piece in each of the cells 2, 3, 4, …,2008 and two (or
maybe more pieces in cell 1.
Replaying the game in reverse order consists of two types of reverse moves:
1) Eliminating two pieces positioned on cell 1.
2) Moving two pieces at cells n+k, n–k to the middle cell, number n.
The move of the first type is performed if and only if no cell with index > 1
has two or more pieces, and cell 1 has no more than 3 pieces.
Consider situation which occurs 2007 steps before the end of the original
game (or after 2007 moves in reversed replay). We shall prove that in the
cell 1 we have no more than 3 pieces. If we have 4 or more pieces in cell 1,
then we have at least 2011 pieces in cells 1, 2, 3, …, 2008. It means that
when we continue playing reverse game we shall always have 2011 pieces
in those cells and always make moves of the second kind (because always
there will be a cell with 2 pieces among 2, 3, …2008 or there will be 4
pieces in cell 1). So the tape will never be emptied in the reverse replay,
contradiction.
Ariel University Center of Samaria
Department of Computer Science and Mathematics
P.O. Box 3, Ariel 44837, ISRAEL
ד "בס
Department of Computer Science and Mathematics
So, in situation 2007 steps before the end (denote it situation S) we have
one piece in cells 2, 3,…, 2008 and two or three pieces in cell 1.
Now consider energy function = sum over all pieces of the squares of the
indexes of their cells. Each time when we add two pieces in cell 1, energy
grows by 2. Each time we move two pieces from cell n to cells n+k, n–k
energy grows by 2k
2
since (n+k)
2
+ (n–k)
2
–2n
2
= 2k
2
. So, each move
raises the energy by 2 at least. The energy of situation S is 222 2008...322
or 222 2008...323 , the second option is the correct because the energy is
always even. So, the number of steps which can occur before situation S is
at most
12
401720092008
1
2
2008...323 222
.
So the total length of the game, with 2007 more moves after situation S is
2008 2009 4017
2008
12
.
If in each move we choose k = 1 then energy grows by 2 each time, and this
is the precise number of steps. It is easy to see that if we play with k = 1 we
shall sooner or later arrive to situationS, and by energy counting we see that
it will take precisely the predicted number of moves.
9. Replace each zero by –1 (minus one). The problem remains the same
from combinatorial point of view. But now all rows are orthogonal.
Divide all elements of the matrix by 2008 . Now the rows form
orthonormal basis. So matrix is orthogonal. So columns form orthonormal
basis. Hence in the original matrix every two columns coincided precisely in
half of the positions.
10. We shall prove that each odd prime number is good. Take n = p – 1
1 1 1 1 1 1 1 1 1 1
... ... ...
1 2 3 1 1 1 2 2
1 1
... ... ... ...
1 2 2 1
p p p k p k
p p p
p
p p k p k p k p k
When You make common denominator inside the brackets, You will have a
denominator which is not divisible by p, so p will divide the nominator and
won’t cancel out.