(K-K), so it's 0.
*grin*[2;0;2;0] and
[2;1;2;0;0], as well as the family
[n-3;2;1;0...0;1;0;0;0]. You might find useful the
following relationships:
a0+a1+...+an=n+1 and
a1+2a2+3a3+...+nan=n+1.
3" with another integer and still get an integer
product, with a similar recurrent relationship. As a function of this
number, this polynomial is closely related to the Tchebyshev
polynomials.
1/2 of the measure
of the set it was integrated on, thus it is 1/2 almost
everywhere - a contradiction, It is also easy to construct such a set
using so called "nonstandard analysis": just fix an infinite number
Z and take all numbers that have 1 in the
Z-th place in their binary representation. This shows
how drastically different nonstandard analysis is: to construct a
non-measurable set, the conventional analysis needs the full power of
Zermelo's AC (Axiom of Choice).
l and m
are diagonals, ac+bd >= lm (equality iff the
quadrilateral is inscribed in a circle) and lm >= S
(equality iff the diagonals are orthogonal).
The easy way is to note that ab+cd >= S and flip
one of the triangles into which the quadrilateral is split by its
diagonal.
n-dimensional ellipsoid is a set
{x|(Ax,x)=1} for some positive operator A.
A circumscribed parallelepiped determines a coordinate system
ei, in which A can be represented
by a (symmetric) matrix. The diagonal is
sqrt(sum((vi,ei)2,
i=1..n)), where
vi=A-1ei/
sqrt((A-1ei,ei)) is the
i-th point tangency of the parallelepiped and the
ellipsoid. This means that the diagonal is
sqrt(Trace(A-1)) and thus is independent on
the coordinate system.
N=1 the answer is 1. When we add one car
which is faster than anything we had before, there is one in
N chance that it will be in front of the rest and this is
the only way the number of packets can be increased. Thus
MN=MN-1+1/N where
MN is the N-the mean. Therefore
MN=1+1/2+1/3+...+1/N (which is approximately
ln(N)).
y axis, while the line perpendicular
to it passing through its intersection with the parabola will be the
x axis.
Note that the property in question was not part of the standard secondary school curriculum in the USSR.
S, the point is A. Choose 4
arbitrary points on S: B, C,
E, and E. Draw the 5-pointed star through
these 5 points. Let F be the intersection of
AD and CE and G be the
intersection of AC and BD. Let
H be the intersection of EB ("shoulders")
and FG ("waist"). Then AH is tangent to
S.
Proof: as usual with ruler-only constructions, we can use
an arbitrary projective transformation to simplify the picture. Move
the tangent t to S at A to be
the line at infinity. Now S is a parabola and a simple
algebraic exercise will show that EB ("shoulders") and
FG ("waist") are parallel, i.e., that they intersect
t at the same point.
There are 2 ideas here:
From Charles Floyd: An alternative to the double negation question for this specific problem is to ask the computer number 1: "is the computer number 2 more likely to tell me the truth than the computer number 3?" and then, if the answer is "yes" buy the computer number 3, and if the answer is "no" buy the computer number 2:
If the first weighting revealed a discrepancy, we have 3 sets of coins, 4 each: light, heavy and genuine. Compare 2 groups: llh and llh. If they are the same, we compare the two remaining h's with each other and the heavier is counterfeit. If one of them, say the first one, is heavier, we have to choose between the h from the first group and the two l's from the second group, so we compare the two l's: is they are the same, the h is counterfeit, otherwise the lighter of them is counterfeit.
Note that each weighting gives us 1 trit of information, so 3 weightings should allow us to distinguish between 27 variants. Indeed, if we knew whether the counterfeit coin is lighter or heavier, we could have detected it among 27 coins. The way the problem us stated though, we could only distinguish between 24 variants (1 out of 12 coins times 1 out of 2 heavies/lighter variants).
Let the line be l, points A and
B and the line AB intersects the line
l at the point K, while the circle
intersects the line l at points X and
Y. Then, XK*KY = AK*KB = constant therefore
XY = XK+KY is minimal when XK = KY, i.e.,
the center of the circle is the intersection of the midpoint
perpendicular to AB and the perpendicular to
l at K.
FM+F+CG+M+FM is 17 minutes.
This problem is related to the private key encryption when the private keys commute.
Assuming the locks are "padlocks", there is another solution: lock an empty box, send it to the recipient, he adds his lock so that it goes through one half of a latch and sends it back, you open the box (it is locked only with your lock), put the diamond in and lock it, putting your lock through the other latch and your recipient's lock (so that the box is locked with the the chain of two locks), then send it to the recipient, who opens the his lock and thus unlocks the box.
A and B meet, we see that the lines
AC and BC must coincide (similarly,
AD=BD), thus all 4 slugs remain on the same
line at all times.
Another solution (by Tanya Khovanova) is to consider the 3-dimensional space-time, where the trajectories (world lines) of the slugs are straight lines. The condition that two slugs meet means that the corresponding world lines intersect, which implies that all 4 lines lie in the same plane, thus they all intersect (since their projections on the spatial dimensions intersect).
n coins each, the result can be
k soldiers looking left and the right-most
l soldiers looking right. It will take at most
N-1 (N being the the number of soldiers)
turns to stabilize, the maximum being achieved in the N-1
cases when some left-most soldiers are looking right and the rest are
looking left. The average number of turns divided by N
seems to be converging to about 0.6 from below.
Since whenever two soldiers look at each other's faces they turn around, the number of soldiers looking left and right is constant, so the number of soldiers who will be finally looking left (right) is the same as the number of soldiers who were looking left (right) initially.
If we encode a left-looking soldier as 1 and a
right-looking soldier as 0, this is a parallel sorting
routine, where at each step the neighboring unordered digits are
transposed.
2g
(g=9.81m/sec2 is the
acceleration of the free fall).
Since the ball was dropped from a significant height, it was moving at
a constant speed when it hit the ground, i.e., the resistance of the
air at that speed was equal to the free fall acceleration.
After bouncing the ball was moving in the opposite direction with the
same speed, so the air resistance was the same but acting in the
opposite direction.
2 and 6.
The smallest number with two permissible product decompositions is
12=2*6=3*4. If the second mathematician had
7=3+4, he would have to be deciding between
3,4 and 2,5. Since 10=2*5 has
only one product decomposition, it is out, so the second mathematician
would have known the answer (3,4) after the first
mathematician answered no the first time. Therefore it could
not have been 7=3+4. If the numbers were larger, the
negative answer of the second mathematician would not have given
enough information to the first.
3.
See the details.
14.
The strategy is to drop the first ball from the K-th
story; if it breaks, you know that the answer is between
1 and K and you have to use at most
K-1 drops to find it out, thus K drops will
be used.
It the first ball does not break when dropped from the
K-th floor, you drop it again from the
(K+K-1)-th floor, then, if it breaks, you find the
critical floor between K+1 and K+K-1 in
K-2 drops, i.e., again, the total number of drops is
K.
Continue until you get above the top floor or you drop the first ball
K times.
Therefore, you have to choose K so that the total number
of floors covered in K steps, which is
K(k+1)/2, is greater that 100 (the total size of the
building).
13*14/2=91 -- too small.
14*15/2=105 -- enough.
Obviously, the only possible strategy is to drop the first ball with some "large" intervals and then drop the last ball with interval 1 inside the "large" interval set by the two last drops of the first ball. If you claim that you can finish in 13 drops, you cannot drop the first ball for the first time from a floor above 13, since then you won't be able to detect the critical floor 13. The next cannot be above 25 etc.
31.
The locker number i is accessed as many times as it has
divisors. E.g., locker number 6 is accessed
4 times - by the first, second, third and sixth kids.
Thus the lockers which will be open are those whose number has an odd
number of divisors, i.e., full squares (since we have an involution on
the set of divisors of i, namely,
j --> i/j
whose fixed point, if any, is the square root of i).
The number of full squares less than 1000 is
(isqrt 1000) which is 31.
5 meters.
The cop can walk one of the corridors to the end and ensure that
the bum is not there. Now he has two corridors -
A and B - and he knows that the bum is
farther than a0=1 in A and
farther than b0=1 in B.
The cop runs x0=b0+1=2 meters
into A and back in x0 seconds.
Now a1 = (x0+1) - x0/2 =
x0/2 + 1 = 2
(the cop inspected x0+1 meters of the
corridor A, but in x0/2 seconds
that he ran back, the bum could reclaim x0/2
meters).
In the corridor B, the bum could make it to the room
in b seconds and run into the "clean" corridor for
another 1 meter, but the cop is already in the room and
he will see the bum, so he can be sure that the bum is still
in B, so b1=1.
Next, the cop runs x1=a1+1=3 meters
into B and back in x1 seconds.
Now b2 = x1/2 + 1 = 5/2 and
a2 = 1.
Thus xn+1 = an+1 + 1 = (xn/2 +
1) + 1 = xn/2 + 2 which converges
to 4, thus the maximum corridor length
is 5.
m, call it M=M(m)=2r(m)
where r(m) is the
ruler function.
To see this, write m in binary, then it ends with a 1 and
some (possibly none) 0s (this 1 and these 0s are exactly the binary
representation of M). -m, written in
Two's Complement,
is the same sequence inverted (i.e., 1 is replaced with 0 and 0 with
1) and 1 added, i.e., it ends with the same number of 0s
as m (which should not be too surprising
since, obviously, M(-m)=M(m)), thus, when you
take m & -m, you get M.
Similar logic works for the left hand side as well.
1/p with
probability p, and the negative value -1/q
with probability q=1-p (thus the mean is 0).
Since we know that the variables are more likely to be positive than
to be negative, we know that p > 1/2 > q, thus
1/p - 1/q < 0.
Therefore, for the sum X+Y to be positive, both variables
must be positive, X=Y=1/p, which happens with
probability p*p, which does not have to be bigger that
1/2 when p > 1/2. E.g., when p=2/3,
P(X+Y>0) = 4/9 < 1/2.
O at
the intersection of their centerlines.I of the section
with the ellipse (it will be tangent to the ellipse at I).
Let foci be A and B. For the triangle
ABI we have the median IO, the bisector
at I (the normal to the tangent at I),
and the line AB (the longer axis).
The circumscribed circle for the triangle ABI must pass
through the point X of the intersection of the
bisector with the shorter axis and though the point J
symmetric to I wrt the shorter axis (because the
circle's center lies on the center perpendicular to the
side AB that is the shorter axis). The circumscribed
circle for the triangle IJX thus intersects the longer
axis at the foci A and B.Z
on the ellipse is the normal to the bisector of the angle
AZB.Z is not on the ellipse, consider all
the sections XY of the ellipse through Z.
The locus of points T between X
and Y such that the distance ZT is the
harmonic average of the distances ZX and ZY
is the circle, that intersects the ellipse at two
points A and B, and the
lines ZA and ZB are tangent to the ellipse.
This is because the
cross-ratio
[X,T,Y,Z]=-1 and if we project Z to
infinity (this preserves cross-ratio), T is projected
to the midpoint between images of X and Y
and the circle above is projected onto the centerline.This is a simple application of the Bayes formula:
Pr(Urn has N White|Sample has M White) =
Pr(Sample has M white|Urn has N White) /
Pr(Sample has M white).
The numerator is 1, the denominator is
sum(k=0,...,N-1;(1-k/N)M)
so
Pr=NM /
sum(k=1,...,N;kM).
The denominator is
N(M+1)/(M+1)
+ NM/2 + ...
so, approximately,
Pr=2(M+1)/(2N+M+1).
Thus, if M=N large, this probability is
approximately 2/3.
Since the ants are indistinguishable for our purposes, their
actual behavior when they bump into each other (turn around) is
equivalent to the ants passing through each other, i.e., we can
assume that they run independently. This means that in at most one
second all ants will be gone.
| Sam Steingold<sds@gnu.org> | |
created: 1998-01-01 |