AOH :: PUZZLE14.FAQ
(14/15)
|
Crazy Slots Download
Article 3074 of news.answers:
Xref: news.UVic.CA rec.puzzles:11477 news.answers:3074
Newsgroups: rec.puzzles,news.answers
Path: news.UVic.CA!ubc-cs!destroyer!uunet!questrel!chris
From: uunet!questrel!chris (Chris Cole)
Subject: rec.puzzles FAQ, part 14 of 15
Message-ID: <puzzles-faq-14_717034101@questrel.com>
Followup-To: rec.puzzles
Summary: This posting contains a list of
Frequently Asked Questions (and their answers).
It should be read by anyone who wishes to
post to the rec.puzzles newsgroup.
Sender: chris@questrel.com (Chris Cole)
Reply-To: uunet!questrel!faql-comment
Organization: Questrel, Inc.
References: <puzzles-faq-1_717034101@questrel.com>
Date: Mon, 21 Sep 1992 00:09:53 GMT
Approved: news-answers-request@MIT.Edu
Expires: Sat, 3 Apr 1993 00:08:21 GMT
Lines: 1574
Archive-name: puzzles-faq/part14
Last-modified: 1992/09/20
Version: 3
==> logic/verger.s <==
The puzzler tried to take the test;
Intriguing rhymes he wished to best.
But "Fifty and ten dozens twenty"
made his headache pound aplenty.
When he finally found some leisure,
He took to task this witty treasure.
"The product of the age must be
Twenty-Four Hundred Fifty!"
Knowing that, he took its primes,
permuted them as many times
as needed, til he found amounts
equal to, by all accounts,
twice the Verger's age, so that
He would have that next day's spat.
The reason for the lad's confusion
was due to multiple solution!
Hence he needed one more clue
to give the answer back to you!
Since only one could fit the bill,
and then confirm the priest's age still,
the eldest age of each solution
by one could differ, with no coercion. <=(Sorry)
Else, that last clue's revelation
would not have brought information!
With two, two, five, seven, and seven,
construct three ages, another set of seven.
Two sets of three yield sixty-four,
Examine them, yet one time more.
The eldest age of each would be
forty-nine, and then, fifty!
With lack of proper rhyme and meter,
I've tried to be the first completor
of this poem and a puzzle;
my poetry, you'd try to muzzle!
And lest you think my wit is thrifty,
The answer, of course, must be fifty!
If dispute, you wish to tender,
note my addresss, as the sender!
--
Kevin Nechodom <knechod@stacc.med.utah.edu>
==> logic/weighing/balance.p <==
You are given N balls and a balance scale and told that
one ball is slightly heavier or lighter than the other identical
ones. The scale lets you put the same number of balls on each side
and observe which side (if either) is heavier.
1. What's the minimum # of weighings X (and way of doing them)
that will always find the unique ball and whether it's heavy or light?
2. If you are told the unique ball is, in fact, heavier than the
others, what's the minimum # of weighings Y to find it?
==> logic/weighing/balance.s <==
Martin Gardner gave a neat solution to this problem.
Assume that you are allowed N weighings. Write down the 3^N possible
length N strings of the symbols '0', '1', and '2'. Eliminate the three
such strings that consist of only one symbol repeated N times.
For each string, find the first symbol that is different from the symbol
preceeding it. Consider that pair of symbols. If that pair is not 01,
12, or 20, cross out that string. In other words, we only allow strings
of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).
You will have (3^N-3)/2 strings left. This is how many balls you can
handle in N weighings.
Perform N weighings as follows:
For weighing I, take all the balls that have a 0 in string
position I, and weigh them against all the balls that have
a 2 in string position I.
If the side with the 0's in position I goes down, write down
a 0. If the other side goes down, write down a 2. Otherwise,
write down a 1.
After the N weighings, you have written down an N symbol string. If
your string matches the string on one of the balls, then that is the
odd ball, and it is heavy. If none of them match, than change every
2 to a 0 in your string, and every 0 to a 2. You will then have a
string that matches one of the balls, and that ball is lighter than
the others.
Note that if you only have to identify the odd ball, but don't have to
determine if it is heavy or light, you can handle (3^N-3)/2+1 balls.
Label the extra ball with a string of all 1's, and use the above
method.
Note also that you can handle (3^N-3)/2+1 balls if you *do* have to
determine whether it is heavy or light, provided you have a single reference
ball available, which you know has the correct weight. You do this by
labelling the extra ball with a string of all 2s. This results in it being
placed on the same side of the scales each time, and in that side of the
scales having one more ball than the other each time. So you put the
reference ball on the other side of the scales to the "all 2s" ball on each
weighing.
Proving that this works is straightforward, once you notice that the
method of string construction makes sure that in each position, 1/3
of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a
string occurs, then the string obtained by replacing each 0 with a
2 and each 2 with a 0 does not occur.
==> logic/weighing/box.p <==
You have ten boxes; each contains nine balls. The balls in one box
weigh 0.9 kg; the rest weigh 1.0 kg. You have one weighing on a
scale to find the box containing the light balls. How do you do it?
==> logic/weighing/box.s <==
Number the boxes 0-9. Take 0 balls from box 0, 1 ball from box 1, 2
balls from box 2, etc. Now weight all those balls and follow this
table:
If odd box is Weight is
0 45 kg
1 44.9 kg
2 44.8 kg
3 44.7 kg
4 44.6 kg
5 44.5 kg
6 44.4 kg
7 44.3 kg
8 44.2 kg
9 44.1 kg
==> logic/weighing/gummy.bears.p <==
Real gummy drop bears have a mass of 10 grams, while imitation gummy
drop bears have a mass of 9 grams. Spike has 7 cartons of gummy drop bears,
4 of which contain real gummy drop bears, the others imitation.
Using a scale only once and the minimum number of gummy drop bears, how
can Spike determine which cartons contain real gummy drop bears?
==> logic/weighing/gummy.bears.s <==
Spike used 51 gummy drop bears: from the 7 boxes he took respectively
0, 1, 2, 4, 7, 13, and 24 bears.
The notion is that each box of imitation bears will subtract its
number of bears from the total "ideal" weight of 510 grams (1 gram of
missing weight per bear), so Spike weighs the bears, subtracts the
result from 510 to obtain a number N, and finds the unique combination
of 3 numbers from the above list (since there are 3 "imitation" boxes)
that sum to N.
The trick is for the sums of all triples selected from the set S of
numbers of bears to be unique. To accomplish this, I put numbers into
S one at a time in ascending order, starting with the obvious choice,
0. (Why is this obvious? If I'd started with k > 0, then I could
have improved on the resulting solution by subtracting k from each
number) Each new number obviously had to be greater than any previous,
because otherwise sums are not unique, but also the sums it made when
paired with any previous number had to be distinct from all previous
pairs (otherwise when this pair is combined with a third number you
can't distinguish it from the other pair)--except for the last box,
where we can ignore this point. And most obviously all the new
triples had to be distinct from any old triples; it was easy to find
what the new triples were by adding the newest number to each old sum
of pairs.
Now, in case you're curious, the possible weight deficits and their
unique decompositions are:
3 = 0 + 1 + 2
5 = 0 + 1 + 4
6 = 0 + 2 + 4
7 = 1 + 2 + 4
8 = 0 + 1 + 7
9 = 0 + 2 + 7
10 = 1 + 2 + 7
11 = 0 + 4 + 7
12 = 1 + 4 + 7
13 = 2 + 4 + 7
14 = 0 + 1 + 13
15 = 0 + 2 + 13
16 = 1 + 2 + 13
17 = 0 + 4 + 13
18 = 1 + 4 + 13
19 = 2 + 4 + 13
20 = 0 + 7 + 13
21 = 1 + 7 + 13
22 = 2 + 7 + 13
24 = 4 + 7 + 13
25 = 0 + 1 + 24
26 = 0 + 2 + 24
27 = 1 + 2 + 24
28 = 0 + 4 + 24
29 = 1 + 4 + 24
30 = 2 + 4 + 24
31 = 0 + 7 + 24
32 = 1 + 7 + 24
33 = 2 + 7 + 24
35 = 4 + 7 + 24
37 = 0 + 13 + 24
38 = 1 + 13 + 24
39 = 2 + 13 + 24
41 = 4 + 13 + 24
44 = 7 + 13 + 24
Note that there had to be (7 choose 3) distinct values; they end up
ranging from 3 to 44 inclusive with 7 numbers missing: 4, 23, 34, 36,
40, 42, and 43.
-- David Karr (karr@cs.cornell.edu)
==> logic/weighing/weighings.p <==
Some of the supervisors of Scandalvania's n mints are producing bogus coins.
It would be easy to determine which mints are producing bogus coins but,
alas, the only scale in the known world is located in Nastyville,
which isn't on very friendly terms with Scandalville. In fact, Nastyville's
king will only let you use the scale twice. Your job? You must determine
which of the n mints are producing the bogus coins using only two weighings
and the minimum number of coins (your king is rather parsimonious, to put it
nicely). This is a true scale, i.e. it will tell you the weight of whatever
you put on it. Good coins are known to have a weight of 1 ounce and it is
also known that all the bogus mints (if any) produce coins that are
light or heavy by the same amount.
Some examples: if n=1 then we only need 1 coin, if n=2 then clearly 2
coins suffice, one from each mint.
What are the solutions for n=3,4,5? What can be said for general n?
==> logic/weighing/weighings.s <==
Oh gracious and wise king, I have solved this problem by first
simplifying and then expanding. That is, consider the problem of
being allowed only a single weighing. Stop reading right now if you
want to think about it further.
There are three possible outcomes for each mint (light, OK, heavy)
which may be represented as (-1, 0, +1). Now, let each mint represent
one place in base 3. Thus, the first mint is the ones place, the
second the threes place, the third is the nines place and so on. The
number of coins from each mint must equal the place. That is, we'll
have 1 coin from mint 1, 3 from mint 2, 9 from mint 3, and, in
general, 3^(n-1) from mint n.
By weighing all coins at once, we will get a value between 1 + 3 + 9 +
... and -1 + -3 + -9 + ... In fact, we notice that that value will
be unique for any mint outcomes. Thus, for the one weighing problem,
we need
sum for i=1 to n (3^(i-1))
which evaluates to (3^n - 1)/2
I'm fairly satisfied that this is a minimum for a single weighing.
What does a second weighing give us? Well, we can divide the coins
into two groups and use the same method. That is, if we have 5 mints,
one weighing will be:
1 coin from mint 1 + 3 coins from mint 2 + 9 coins from mint 3
while the other weighing will be:
1 coin from mint 4 + 3 coins from mint 5
It's pretty plain that this gives us a total coinage of:
3^(n/2) - 1 for even n and, after some arithmetic agitation:
2 * 3^((n-1)/2) - 1 for odd n
I think the flaw in this solution is that we don't know ahead of time
the amount by which the coins are off weight. So if you weigh 1 coin
from mint 1 together with 3 coins from mint 2 and the result is heavy
by 3x units, you still don't know whether the bogus coins are from
mint 3 (heavy by x units) or from mint 1 (heavy by 3x units). Note
that we're not given the error amount, only the fact that is is equal
for all bogus coins.
Here is my partial solution:
After considering the above, it would seem that on each of the two
weighings we must include coins from all of the mints (except for the
special cases of small n). So let ai (a sub i) be the number of coins
from mint i on weighing 1 and bi be the number of coins from mint i on
weighing 2. Let the error in the bogus coins have a value x, and let
ci be a the counterfeit function: ci is 0 if mint i is good, 1
otherwise.
Then
Sum ai ci x = delta1 error on weighing 1
Sum bi ci x = delta2 error on weighing 2
Now the ratio of delta1 to delta2 will be rational regardless of the
value of x, since x will factor out; let's call this ratio p over q (p
and q relatively prime). We would like to choose { ai } and { bi }
such that for any set of mints J, which will be a subset of { 1 , 2 ,
... , n }, that
Sum aj ( = Sum ai ci ) is relatively prime to Sum bj.
If this is true then we can determine the error x; it will simply be
delta1/p, which is equal to delta2/q.
If the { ai } have been carefully chosen, we should be able to figure
out the bogus mints from one of the weighings, provided that
all subsets ( { { aj } over all J } ) have unique sums.
This was the strategy proposed above, where is was suggested
that ai = 3 ** (i-1) ; note that you can use base 2 instead
of base 3 since all the errors have the same sign.
Well, for the time being I'm stumped.
This agrees with the analysis I've been fighting with. I actually
came up with a pair of functions that "almost" works. So that the
rest of you can save some time (in case you think the way I did):
Weighing 1: 1 coin from each mint
Weighing 2: 2^(k-1) coins from mint k, for 1...k...n
(total 2^n - 1 coins)
Consider the n mints to be one-bit-each -- bit set -> mint makes bogus
coins. Then we can just state that we're trying to discover "K",
where K is a number whose bit pattern _just_ describes the bogosity of
each mint. OK - now, assuming we know 'x', and we only consider the
*difference* of the weighing from what it should be, for weighing 1,
the devaiation is just the Hamming weight of K -- that is the number
of 1-bits in it -- that is, the number of bogosifying mints. For
weighing 2, the deviation is just K! When the nth bit of K is set,
then that mint contributes just 2^n to the deviation, and so the total
deviation will just be K.
So that set me in search of a lemma: given H(x) is the hamming weight
of x, is f(x) = x / H(x) a 1-1 map integers into rationals? That is,
if x/H(x) = y/H(y) can we conclude that x = y?
The answer (weep) is NO. The lowest pair I could find are 402/603
(both give the ratio 100.5). Boy it sure looked like a good
conjecture for a while! Sigh.
There are two parts to the problem. First let us try to come up with a
solution to finding the answer in 2 weighings - then worry about using the
min. number of coins.
Solutions are for GENERAL n.
Let N = set of all mints, 1 to n. Card(N) = n.
Let P = set of all bogus mints. Let Card(P) = p.
Weighing I: Weigh n coins, 1 from each mint.
Since each "good" coins weighs one ounce, let delta1 be the error in weighing.
Since all bogus coins are identical, let delta1 be abs(error).
If x is the weight by which one bogus coin differs from a good coin,
delta1 = p * x.
Weighing II: The coins to be weighed are composed thusly.
Let a1 be the number of coins from mint 1, a2 # from mint2 .. and an from
mint n. All ai's are distinct integers.
Let A = Set of all ai's.
Let delta2 = (abs.) error in weighing 2 = x * k
where k is the number of coins that are bogus in weighing two.
Or more formally
k = sigma(ai)
(over all i in P)
Assuming p is not zero (from Weighing I - in that case go back and get beheaded
for giving the king BAAAAAD advice),
Let ratio = delta1/delta2 = p/k.
Let IR = delta2/delta1 = k/p = inverse-ratio (for later proof).
Let S(i) be the bag of all numbers generated by summing i distinct elements
from A. Clearly there will be nCi (that n comb. i) elements in S(i).
[A bag is a set that can have the same element occur more than once.]
So S(1) = A
and S(n) will have one element that is the sum of all the elements of A.
Let R(i) = {x : For-all y in S(i), x = i/y} expressed as p/q (no common
factors).
(R is a bag too).
Let R-A = Bag-Union(R(i) for 1>= i >=n). (can include same element twice)
Choose A, such that all elements of R-A are DISTINCT, i.e. Bag(R-A) = Set(R-A).
Let the sequence a1, a2, .. an, be an L-sequence if the above property is
true. Or more simply, A is in L.
**********************************************************************
CONJECTURE: The bogus mint problem is solved in two weighings if A is in L.
Sketchy proof: R(1) = all possible ratios (= delta1/delta2) when p=1.
R(i) = all possible ratio's when p=i.
Since all possible combinations of bogus mints are reflected in R, just match
the actual ratio with the generated table for n.
************************************************************************
A brief example. Say n=3. Skip to next line if you want.
Let A=(2,3,7).
p=1 possible ratios = 1/2 1/3 1/7
p=2 possible ratios = 2/5 2/9 1/5(2/10)
p=3 possible ratios = 1/4(3/12) (lots of blood in Scandalvania).
As all outcomes are distinct, and the actual ratio MUST be one of these,
match it to the answer, and start sharpening the axe.
Note that the minimum for n=3 is A=(0,1,3)
possible ratios are
p=1 infinity (delta2=0),1,1/3
p=2 2/1,2/3,1/2
p=3 3/4
************************************************************************
All those with the determination to get this far are saying OK, OK how do we
get A.
I propose a solution that will generate A, to give you the answer in two
weighings, but will not give you the optimal number of coins.
Let a1=0
For i>=2 >=n
ai = i*(a1 + a2 + ... + ai-1) + 1
*****************************************
* i-1 *
* ai = i* [Sigma(aj)] + 1 * ****Generator function G*****
* j=1 *
*****************************************
If A is L, all RATIO's are unique. Also all inverse-ratio's (1/ratio) are
unique. I will prove that all inverse-ratio's (or IR's) are unique.
Let A(k), be the series generated by the first k elements from eqn. G.(above)
************************************************************************
PROOF BY INDUCTION.
A(1) = {0} is in L.
A(2) = {0,1} is in L.
ASSUME A(k) = {0,1, ..., ak} is in L.
T.P.T. A(k+1) = {0,1, ..., ak, D) is in L where D is generated from G.
We know that all IR's(inverse ratio's) from A(k) are distinct.
Let K = set of all IR's of A(k).
Since A(k+1) contains A(k), all IR's of A(k) will also be IR's of A(K+1).
So for all P, such that (k+1) is not in P, we get a distinct IR.
So consider cases when (k+1) is in P.
p=1 (i.e. (k+1) = only bogus mint), IR = D
______________________________________________________________________
CONJECTURE: Highest IR for A(k) = max(K) = ak
Proof: Since max[A(k)] = ak,
for p'= 1, max IR = ak/1 = ak
for p'= 2, max IR (max sum of 2 ai's)/2
= (ak + ak-1)/2 < ak (as ak>ak-1).
for p'= i max IR sum of largest i elements of A(k)
--------------------------------
i
< i * ak/i = ak.
So max. IR for A(k) is ak.
______________________________________________________________________
D > ak
So for p=1 IR is distinct.
Let Xim be the IR formed by choosing i elements from A(k+1).
Note: We are choosing D and (i-1) elements from A(k).
m is just an index to denote each distinct combination of
(i-1) elemnts of A(i).
______________________________________________________________________
CONJECTURE : For p=j, all new IR's Xjm are limited to the range
D/(j-1) > Xjm > D/j.
Proof:
Xjm = (D + {j-1 elements of A(k)})/j
Clearly Xjm > D/j.
To show: max[Xjm] < D/(j-1)
Note: a1 + a2 .. + ak < D/(k+1)
max[Xjm] = (D + ak + ak-1 + ... + a(k-j+1))/j
< (D + D/(k+1))/j
= D (k+2)/(k+1)j
= [D/(j-1)] * alpha.
alpha = (j-1)/(j) * (k+2)/(k+1)
Since j <= k, (j-1)/j <= (k-1)/k < (k+1)/(k+2)
IMPLIES alpha < 1.
Conjecture proved.
______________________________________________________________________
CONJECTURE : For a given p, all newly generated IR's are distinct.
Proof by contradiction:
Assume this is not so.
Implies
(D + (p-1) elements of A(k))/p
= (D + some other (p-1) elements of A(k))/p
Implies SUM[(p-1) elements of A(k)] = SUM[ some other (p-1) elements of A(k)]
Implies SUM[(p-1) elements of A(k)]/(p-1)
= SUM[some other (p-1) elements]/(p-1)
Implies A(k) is NOT in L.
Contra.
Hence conjecture.
______________________________________________________________________
CONJECTURE: A(k+1) is in L.
Since all newly generated IR's are distinct from each other, and all newly generated IR's are greater than previous IR's, A(k+1) is in L.
==> logic/zoo.p <==
I took some nephews and nieces to the Zoo, and we halted at a cage marked
Tovus Slithius, male and female.
Beregovus Mimsius, male and female.
Rathus Momus, male and female.
Jabberwockius Vulgaris, male and female.
The eight animals were asleep in a row, and the children began to guess
which was which. "That one at the end is Mr Tove." "No, no! It's Mrs
Jabberwock," and so on. I suggested that they should each write down
the names in order from left to right, and offered a prize to the one
who got most names right.
As the four species were easily distinguished, no mistake would arise in
pairing the animals; naturally a child who identified one animal as Mr
Tove identified the other animal of the same species as Mrs Tove.
The keeper, who consented to judge the lists, scrutinised them carefully.
"Here's a queer thing. I take two of the lists, say, John's and Mary's.
The animal which John supposes to be the animal which Mary supposes to be
Mr Tove is the animal which Mary supposes to be the animal which John
supposes to be Mrs Tove. It is just the same for every pair of lists,
and for all four species.
"Curiouser and curiouser! Each boy supposes Mr Tove to be the animal
which he supposes to be Mr Tove; but each girl supposes Mr Tove to be
the animal which she supposes to be Mrs Tove. And similarly for the oth-
er animals. I mean, for instance, that the animal Mary calls Mr Tove
is really Mrs Rathe, but the animal she calls Mrs Rathe is really Mrs
Tove."
"It seems a little involved," I said, "but I suppose it is a remarkable
coincidence."
"Very remarkable," replied Mr Dodgson (whom I had supposed to be the
keeper) "and it could not have happened if you had brought any more
children."
How many nephews and nieces were there? Was the winner a boy or a girl?
And how many names did the winner get right? [by Sir Arthur Eddington]
==> logic/zoo.s <==
Given that there is at least one boy and one girl (John and Mary are
mentioned) then the answer is that there were 3 nephews and 2 nieces,
the winner was a boy who got 4 right.
Number the animals 1 through 8, such that the females are even and the
males are odd, with members of the same species consecutive; i.e.
1 is Mr. Tove, 2 Mrs. Tove, etc.
Then each childs guesses can be represented by a permutation. I use
the standard notation of a permutation as a set of orbits.
For example: (1 3 5)(6 8) means 1 -> 3, 3 -> 5, 5 -> 1, 6 -> 8, 8 -> 6
and 2,4,7 are unchanged.
[1] Let P be any childs guesses. Then P(mate(i)) = mate(P(i)).
[2] If Q is another childs guesses, then [P,Q] = T, where
[P,Q] is the commutator of P and Q (P composed with Q composed with
P inverse composed with Q inverse) and T is the special permutation
(1 2) (3 4) (5 6) (7 8) that just swaps each animal with its spouse.
[3] If P represents a boy, then P*P = I (I use * for composition, and I
for
the identity permutation: (1)(2)(3)(4)(5)(6)(7)(8)
[4] If P represents a girl, then P*P = T.
[1] and [4] together mean that all girl's guesses must be of the form:
(A B C D) (E F G H) where A and C are mates, as are B & D, E & F
G & H.
So without loss of generality let Mary = (1 3 2 4) (5 7 6 8)
Without to much effort we see that the only possibilities for other
girls "compatible" with Mary (I use compatible to mean the relation
expressed in [2]) are:
g1: (1 5 2 6) (3 8 4 7)
g2: (1 6 2 5) (3 7 4 8)
g3: (1 7 2 8) (3 5 4 6)
g4: (1 8 2 7) (3 6 4 5)
Note that g1 is incompatible with g2 and g3 is incompatible with g4.
Thus no 4 of Mary and g1-4 are mutually compatible. Thus there are at
most three girls: Mary, g1 and g3 (without loss of generality)
By [1] and [3], each boy must be represented as a product of
transpostions and/or singletons: e.g. (1 3) (2 4) (5) (6) (7) (8) or
(1) (2) (3 4) (5 8) (6 7).
Let J represent John's guesses and consider J(1).
If J(1) = 1, then J(2) = 2 (by [1]) using [2] and Mary J(3) = 4, J(4) =
3, and g1 & J => J(5) = 6, J(6) = 5, & g3 & J => J(8) = 7 J(7) = 8
i.e. J = (1)(2)(3 4)(5 6)(7 8). But the [J,Mary] <> T. In fact, we
can see that J must have no fixed points, J(i) <> i for all i, since
there is nothing special about i = 1.
If J(1) = 2, then we get from Mary that J(3) = 3. contradiction.
If J(1) = 3, then J(2) = 4, J(3) = 1, J(4) = 2 (from Mary) =>
J(5) = 7, J(6) = 8, J(7) = 5, J(8) = 6 => J = (1 3)(2 4)(5 7)(6 8)
(from g1)
But then J is incompatible with g3.
A similar analysis shows that J(1) cannot be 4,5,6,7 or 8; i.e. no J
can be compatible with all three girls. So without loss of generality,
throw away g3.
We have Mary = (1 3 2 4) (5 7 6 8)
g1 = (1 5 2 6) (3 8 4 7)
The following are the only possible boy guesses which are compatible
with
both of these:
B1: (1)(2)(3 4)(5 6)(7)(8)
B2: (1 2)(3)(4)(5)(6)(7 8)
B3: (1 3)(2 4)(5 7)(6 8)
B4: (1 4)(2 3)(5 8)(6 7)
B5: (1 5)(2 6)(3 8)(4 7)
B6: (1 6)(2 5)(3 7)(4 8)
Note that B1 & B2 are incombatible, as are B3 & B4, B5 & B6, so at most
three
of them are mutually compatible. In fact, Mary, g1, B1, B3 and B5 are
all
mutually compatible (as are all the other possibilities you can get by
choosing
either B1 or B2, B3 or B4, B5 or B6. So if there are 2 girls there can
be
3 boys, but no more, and we have already eliminated the case of 3 girls
and
1 boy.
The only other possibility to consider is whether there can be 4 or more
boys
and 1 girl. Suppose there are Mary and 4 boys. Each boy must map 1 to
a
different digit or they would not be mutually compatible. For example
if b1
and b2 both map 1 to 3, then they both map 3 to 1 (since a boy's map
consists
of transpositions), so both b1*b2 and b2*b1 map 1 to 1. Furthermore, b1
and
b2 cannot map 1 onto spouses. For example, if b1(1) = a and b is the
spouse
of a, then b1(2) = b. If b2(1) = b, then b2(2) = a. Then
b1*b2(1) = b1(b) = 2 and b2*b1(1) = b2(a) = 2 (again using the fact that
boys
are all transpostions). Thus the four boys must be:
B1: (1)(2)... or (1 2)....
B2: (1 3)... or (1 4) ...
B3: (1 5) ... or (1 6) ...
B4: (1 7) ... or (1 8) ...
Consider B4. The only permutation of the form (1 7)... which is
compatible
with Mary ( (1 3 2 4) (5 7 6 8) ) is:
(1 7)(2 8)(3 5)(4 6)
The only (1 8)... possibility is:
(1 8)(2 7)(3 6)(4 5)
Suppose B4 = (1 7)(2 8)(3 5)(4 6)
If B3 starts (1 5), it must be (1 5)(2 6)(3 8)(4 7) to be compatible
with B4.
This is compatible with Mary also.
Assuming this and B2 starts with (1 3) we get B2 = (1 3)(2 4)(5 8)(6 7)
in
order to be compatible with B4. But then B2*B3 and B3*B2 moth map 1 to
8.
I.e. no B2 is mutually compatible with B3 & B4.
Similarly if B2 starts with (1 4) it must be (1 4)(2 3)(5 7)(6 8) to
work
with B4, but this doesn't work with B3.
Likewise B3 starting with (1 6) leads to no possible B2 and the
identical
reasoning eliminates B4 = (1 8)...
So no B4 is possible!
I.e at most 3 boys are mutually compatiblw with Mary, so 2 girls & 3
boys is optimal.
Thus:
Mary = (1 3 2 4) (5 7 6 8)
Sue = (1 5 2 6) (3 8 4 7)
John = (1)(2)(3 4)(5 6)(7)(8)
Bob = (1 3)(2 4)(5 7)(6 8)
Jim = (1 5)(2 6)(3 8)(4 7)
is one optimal solution, with the winner being John (4 right: 1 2 7 & 8)
==> physics/balloon.p <==
A helium-filled balloon is tied to the floor of a car that makes a
sharp right turn. Does the balloon tilt while the turn is made?
If so, which way? The windows are closed so there is no connection
with the outside air.
==> physics/balloon.s <==
Because of buoyancy, the helium balloon on the string will want to move
in the direction opposite the effective gravitational field existing
in the car. Thus, when the car turns the corner, the balloon will
deflect towards the inside of the turn.
==> physics/bicycle.p <==
A boy, a girl and a dog go for a 10 mile walk. The boy and girl can
walk 2 mph and the dog can trot at 4 mph. They also have bicycle
which only one of them can use at a time. When riding, the boy and
girl can travel at 12 mph while the dog can peddle at 16 mph.
What is the shortest time in which all three can complete the trip?
==> physics/bicycle.s <==
First note that there's no apparent way to benefit from letting either the
boy or girl ride the bike longer than the other. Any solution which gets the
boy there faster, must involve him using the bike (forward) more; similarly
for the girl. Thus the bike must go backwards more for it to remain within
the 10-mile route. Thus the dog won't make it there in time. So the solution
assumes they ride the bike for the same amount of time.
Also note that there's no apparent way to benefit from letting any of the three
arrive at the finish ahead of the others. If they do, they can probably take
time out to help the others. So the solution assumes they all finish at the
same time.
The boy starts off on the bike, and travels 5.4 miles. At this
point, he drops the bike and completes the rest of the trip on foot. The
dog eventually reaches the bike, and takes it *backward* .8 miles (so the
girl gets to it sooner) and then returns to trotting. Finally, the girl makes
it to the bike and rides it to the end. The answer is 2.75 hours.
The puzzle is in Vasek Chvatal, Linear Programming, W. H. Freeman & Co.
The generalized problem (n people, 1 bike, different walking and riding speeds)
is known as "The Bicycle Problem". A couple references are
Masuda, S. (1970). "The bicycle problem," University of California, Berkeley:
Operations Research Center Technical Report ORC 70-35.
Chvatal, V. (1983). "On the bicycle problem," Discrete Applied Mathematics 5:
pp. 165 - 173.
As for the linear program which gives the lower bound of 2.75 hours, let
t[person, mode, direction] by the amount of time "person" (boy, girl or dog)
is travelling by "mode" (walk or bike) in "direction" (forward or backwards).
Define Time[person] to be the total time spent by person doing each of these
four activities. The objective is to minimize the maximum of T[person], for
person = boy, girl, dog, e.g.
minimize T
subject to T >= T[boy], T >= T[girl], T >= T[dog].
Now just think of all the other linear constraints on the variables t[x,y,z],
such as everyone has to travel 10 miles, etc. In all, there are 8 contraints
in 18 variables (including slack variables). Solving this program yields the
lower bound.
==> physics/boy.girl.dog.p <==
A boy, a girl and a dog are standing together on a long, straight road.
Simulataneously, they all start walking in the same direction:
The boy at 4 mph, the girl at 3 mph, and the dog trots back and forth
between them at 10 mph. Assume all reversals of direction instantaneous.
In one hour, where is the dog and in which direction is he facing?
==> physics/boy.girl.dog.s <==
The dog's position and direction are indeterminate, other than that the
dog must be between the boy and girl (endpoints included). To see this,
simply time reverse the problem. No matter where the dog starts out,
the three of them wind up together in one hour.
This argument is not quite adequate. It is possible to construct problems
where the orientation changes an infinite number of times initially, but for
which there can be a definite result. This would be the case if the positions
at time t are uniformly continuous in the positions at time s, s small.
But suppose that at time a the dog is with the girl. Then the boy is at
4a, and the time it takes the dog to reach the boy is a/6, because
the relative speed is 6 mph. So the time b at which the dog reaches the
boy is proportional to a. A similar argument shows that the time the
dog next reaches the girl is b + b/13, and is hence proportional to b.
This makes the position of the dog at time (t > a) a periodic function of
the logarithm of a, and thus does not approach a limit as a -> 0.
==> physics/brick.p <==
What is the maximum overhang you can create with an infinite supply of bricks?
==> physics/brick.s <==
You can create an infinite overhang.
Let us reverse the problem: how far can brick 1 be from brick 0?
Let us assume that the brick is of length 1.
To determine the place of the center of mass a(n):
a(1)=1/2
a(n)=1/n[(n-1)*a(n-1)+[a(n-1)+1/2]]=a(n-1)+1/(2n)
Thus
n 1 n 1
a(n)=Sum -- = 1/2 Sum - = 1/2 H(n)
m=1 2m m=1 m
Needless to say the limit for n->oo of half the Harmonic series is oo.
==> physics/cannonball.p <==
A person in a boat drops a cannonball overboard; does the water level change?
==> physics/cannonball.s <==
The cannonball in the boat displaces an amount of water equal to the MASS
of the cannonball. The cannonball in the water displaces an amount of water
equal to the VOLUME of the cannonball. Water is unable to support the
level of salinity it would take to make it as dense as a cannonball, so the
first amount is definitely more than the second amount, and the water level
drops.
==> physics/dog.p <==
A body of soldiers form a 50m-by-50m square ABCD on the parade ground.
In a unit of time, they march forward 50m in formation to take up the
position DCEF. The army's mascot, a small dog, is standing next to its
handler at location A. When the
B----C----E soldiers start marching, the dog
| | | forward--> begins to run around the moving
A----D----F body in a clockwise direction,
keeping as close to it as possible.
When one unit of time has elapsed, the dog has made one complete
circuit and has got back to its handler, who is now at location D. (We
can assume the dog runs at a constant speed and does not delay when
turning the corners.)
How far does the dog travel?
==> physics/dog.s <==
Let L be the side of the square, 50m, and let D be the distance the
dog travels.
Let v1 be the soldiers' marching speed and v2 be the speed of the dog.
Then v1 = L / (1 time unit) and v2 = v1*D/L.
Let t1, t2, t3, t4 be the time the dog takes to traverse each side of
the square, in order. Find t1 through t4 in terms of L and D and solve
t1+t2+t3+t4 = 1 time unit.
While the dog runs along the back edge of the square in time t1, the
soldiers advance a distance d=t1*v1, so the dog has to cover a distance
sqrt(L^2 + (t1*v1)^2), which takes a time t1=sqrt(L^2 + (t1*v1)^2)/v2.
Solving for t1 gives t1=L/sqrt(v2^2 - v1^2).
The rest of the times are t2 = L/(v2-v1), t3 = t1, and t4 = L/(v2+v1).
In t1+t2+t3+t4, eliminate v2 by using v2=v1*D/L and eliminate v1 by
using v1=L/(1 time unit), obtaining
2 L (D + sqrt(D^2-L^2)) / (D^2 - L^2) = 1
which can be turned into
D^4 - 4LD^3 - 2L^2D^2 + 4L^3D + 5L^4 = 0
which has a root D = 4.18113L = 209.056m.
==> physics/magnets.p <==
You have two bars of iron. One is magnetic, the other is not. Without
using any other instrument (thread, filings, other magnets, etc.), find
out which is which.
==> physics/magnets.s <==
Take the two bars, and put them together like a T, so that one bisects the
other.
___________________
bar A ---> |___________________|
| |
| |
| |
| |
bar B ------------> | |
| |
| |
|_|
If they stick together, then bar B is the magnet. If they don't, bar A is
the magnet. (reasoning follows)
Bar magnets are "dead" in their centers (ie there is no magnetic force,
since the two poles cance out). So, if bar A is the magnet, then bar B
won't stick to its center.
However, bar magnets are quite "alive" at their edges (ie the magnetic
force is concentrated). So, if bar B is the magnet, then bar A will stick
nicely to its end.
==> physics/milk.and.coffee.p <==
You are just served a hot cup of coffee and want it to be as hot as possible
when you drink it some number of minutes later. Do you add milk when you get
the cup or just before you drink it?
==> physics/milk.and.coffee.s <==
Normalize your temperature scale so that 0 degrees = room temperature.
Assume that the coffee cools at a rate proportional to the difference
in temperature, and that the amount of milk is sufficiently small that
the constant of proportinality is not changed when you add the milk.
An early calculus homework problem is to compute that the temperature
of the coffee decays exponentially with time,
T(t) = exp(-ct) T0, where T0 = temperature at t=0.
Let l = exp(-ct), where t is the duration of the experiment.
Assume that the difference in specific heats of coffee and milk are
negligible, so that if you add milk at temperature M to coffee at
temperature C, you get a mix of temperature aM+bC, where a and b
are constants between 0 and 1, with a+b=1. (Namely, a = the fraction
of final volume that is milk, and b = fraction that is coffee.)
If we let C denote the original coffee temperature and M the milk
temperature, we see that
Add milk later: aM + blC
Add milk now: l(aM+bC) = laM+blC
The difference is d=(1-l)aM. Since l<1 and a>0, we need to worry about
whether M is positive or not.
M>0: Warm milk. So d>0, and adding milk later is better.
M=0: Room temp. So d=0, and it doesn't matter.
M<0: Cold milk. So d<0, and adding milk now is better.
Of course, if you wanted to be intuitive, the answer is obvious if you
assume the coffee is already at room temperature and the milk is
either scalding hot or subfreezing cold.
Moral of the story: Always think of extreme cases when doing these puzzles.
They are usually the key.
Oh, by the way, if we are allowed to let the milk stand at room
temperature, then let r = the corresponding exponential decay constant
for your milk container.
Add acclimated milk later: arM + blC
We now have lots of cases, depending on whether
r<l: The milk pot is larger than your coffee cup.
(E.g, it really is a pot.)
r>l: The milk pot is smaller than your coffee cup.
(E.g., it's one of those tiny single-serving things.)
M>0: The milk is warm.
M<0: The milk is cold.
Leaving out the analysis, I compute that you should...
Add warm milk in large pots LATER.
Add warm milk in small pots NOW.
Add cold milk in large pots NOW.
Add cold milk in small pots LATER.
Of course, observe that the above summary holds for the case where the
milk pot is allowed to acclimate; just treat the pot as of infinite
size.
==> physics/mirror.p <==
Why does a mirror appear to invert the left-right directions, but not up-down?
==> physics/mirror.s <==
Mirrors invert front to back, not left to right.
The popular misconception of the inversion is caused by the fact that
a person when looking at another person expects him/her to face her/him,
so with the left-hand side to the right. When facing oneself (in the
mirror) one sees an 'uninverted' person.
See Martin Gardner, ``Hexaflexagons and other mathematical
diversions,'' University of Chicago Press 1988, Chapter 16. A letter
by R.D. Tschigi and J.L. Taylor published in this book states that the
fundamental reason is: ``Human beings are superficially and grossly
bilaterally symmetrical, but subjectively and behaviorally they are
relatively asymmetrical. The very fact that we can distinguish our
right from our left side implies an asymettry of the perceiving
system, as noted by Ernst Mach in 1900. We are thus, to a certain
extent, an asymmetrical mind dwelling in a bilaterally symmetrical
body, at least with respect to a casual visual inspection of our
external form.''
Martin Gardner has also written the book ``The Amidextrous Universe.''
==> physics/monkey.p <==
Hanging over a pulley, there is a rope, with a weight at one end.
At the other end hangs a monkey of equal weight. The rope weighs
4 ounces per foot. The combined ages of the monkey and it's mother
is 4 years. The weight of the monkey is as many pounds as the mother
is years old. The mother is twice as old as the monkey was when the
mother was half as old as the monkey will be when the monkey is 3 times
as old as the mother was when she was 3 times as old as the monkey.
The weight of the rope and the weight is one-half as much again as the
difference between the weight of the weight and the weight of the weight
plus the weight of the monkey.
How long is the rope?
==> physics/monkey.s <==
The most difficult thing about this puzzle, as you probably expected,
is translating all the convoluted problem statements into equations...
the solution is pretty trivial after that. So...
Let:
m represent monkey
M represent mother of monkey
w represent weight
r represent rope
W[x] = present weight of x (x is m, M, w, or r)
A[x,t] = age of x at time t (x is M or M, t is one of T1 thru T4)
T1 = time at which mother is 3 times as old as monkey
T2 = time at which monkey is 3 times as old as mother at T1
T3 = time at which mother is half as old as monkey at T2
T4 = present time
For the ages, we have:
A[M,T1] = 3*A[m,T1]
A[m,T2] = 3*A[M,T1] = 9*A[m,T1]
A[M,T3] = A[m,T2]/2 = 9*A[m,T1]/2
A[m,T3] = A[m,T1] + (T3-T1)
= A[m,T1] + (A[M,T3]-A[M,T1])
= A[m,T1] + (9*A[M,T1]/2 - 3*A[m,T1])
= 5*A[m,T1]/2
A[M,T4] = 2*A[m,T3] = 5*A[m,T1]
A[m,T4] = A[m,T1] + (T4-T1)
= A[m,T1] + (A[M,T4]-A[M,T1])
= A[m,T1] + (5*A[m,T1] - 3*A[m,T1])
= 3*A[m,T1]
The present ages of monkey and mother sum to 4, so we have
A[m,T4] + A[M,T4] = 4
3*A[m,T1] + 5*A[m,T1] = 4
8*A[m,T1] = 4
A[m,T1] = 1/2
Thus:
A[M,T4] = 5/2
A[m,T4] = 3/2
Now for the weights, translating everything to ounces:
Monkey's weight in lbs = mother's age in years, so:
W[m] = 16*5/2 = 40
Weight and monkey are same weight, so:
W[w] = W[m] = 40
The last paragraph in the problem translates into:
W[r]+W[w] = (3/2)*((W[w]+W[m])-W[w])
W[r]+ 40 = (3/2)*(( 40 + 40 )- 40 )
W[r]+ 40 = 60
W[r] = 20
The rope weighs 4 ounces per foot, so its length is 5 feet.
==> physics/particle.p <==
What is the longest time that a particle can take in travelling between two
points if it never increases its acceleration along the way and reaches the
second point with speed V?
==> physics/particle.s <==
Assumptions:
1. x(0) = 0; x(T) = X
2. v(0) = 0; v(T) = V
3. d(a)/dt <= 0
Solution:
a(t) = constant = A = V^2/2X which implies T = 2X/V.
Proof:
Consider assumptions as they apply to f(t) = A * t - v(t):
1. integral from 0 to T of f = 0
2. f(0) = f(T) = 0
3. d^2(f)/dt^2 <= 0
From the mean value theorem, f(t) = 0. QED.
==> physics/pole.in.barn.p <==
Accelerate a pole of length l to a constant speed of 90% of the speed of
light (.9c). Move this pole towards an open barn of length .9l (90%
the length of the pole). Then, as soon as the pole is fully inside the
barn, close the door. What do you see and what actually happens?
==> physics/pole.in.barn.s <==
What the observer sees depends upon where the observer is, due to
the finite speed of light.
For definiteness, assume the forward end of the pole is marked "A" and
the after end is marked "B". Let's also assume there is a light source
inside the barn, and that the pole stops moving as soon as end "B" is
inside the barn.
An observer inside the barn next to the door will see the following
sequence of events:
1. End "A" enters the barn and continues toward the back.
2. End "B" enters the barn and stops in front of the observer.
3. The door closes.
4. End "A" continues moving and penetrates the barn at the far end.
5. End "A" stops outside the barn.
An observer at the other end of the barn will see:
1. End "A" enters the barn.
2. End "A" passes the observer and penetrates the back of the barn.
3. If the pole has markings on it, the observer will notice the part
nearest him has stopped moving. However, both ends are still
moving.
4. End "A" stops moving outside the barn.
5. End "B" continues moving until it enters the barn and then stops.
6. The door closes.
After the observers have subtracted out the effects of the finite speed
of light on what they see, both observers will agree on what happened:
The pole entered the barn; the door closed so that the pole was
completely contained within the barn; as the pole was being stopped it
elongated and penetrated the back wall of the barn.
Things are different if you are riding along with the pole. The pole
is never inside the barn since it won't fit. End A of the pole penetrates
the rear wall of the barn before the door is closed.
If the wall of the barn is impenetrable, in all the above scenarios insert
the wording "End A of the pole explodes" for "End A penetrates the barn."
==> physics/resistors.p <==
What are the resistances between lattices of resistors in the shape of a:
1. Cube
2. Platonic solid
3. Hypercube
4. Plane sheet
5. Continuous sheet
==> physics/resistors.s <==
1. Cube
The key idea is to observe that if you can show that two
points in a circuit must be at the same potential, then you can
connect them, and no current will flow through the connection and the
overall properties of the circuit remain unchanged. In particular, for
the cube, there are three resistors leaving the two "connection
corners". Since the cube is completely symmetrical with respect to the
three resistors, the far sides of the resistors may be connected
together. And so we end up with:
|---WWWWWW---| |---WWWWWW---|
| | | |
*--+---WWWWWW---+----+---WWWWWW---+---*
| | | |
|---WWWWWW---| |---WWWWWW---|
2. Platonic Solids
Same idea for 8 12 and 20, since you use the symmetry to identify
equi-potential points. The tetrahedron is hair more subtle:
*---|---WWWWWW---|---*
|\ /|
W W W W
W W W W
W W W W
| \ / |
\ || |
\ | /
\ W /
\ W / <-------
\ W /
\|/
+
By symmetry, the endpoints of the marked resistor are equi-potential. Hence
they can be connected together, and so it becomes a simple:
*---+---WWWWW---+----*
| |
+-WWW WWW-+
| |-| |
|-WWW WWW-|
3. Hypercube
Think of injecting a constant current I into the start vertex.
It splits (by symmetry) into n equal currents in the n arms; the current of
I/n then splits into I/n(n-1), which then splits into I/[n(n-1)(n-1)] and so
on till the halfway point, when these currents start adding up. What is the
voltage difference between the antipodal points? V = I x R; add up the voltages
along any of the paths:
n even: (n-2)/2
V = 2{I/n + I/(n(n-1)) + I/(n(n-1)(n-1)) + ... + I/(n(n-1) )}
n odd: (n-3)/2
V = 2{I/n + I/(n(n-1)) + I/(n(n-1)(n-1)) + ... + I/(n(n-1) )} (n-1)/2
+ I/(n(n-1) )
And R = V/I i.e. replace the Is in the above expression by 1s.
For the 3-cube: R = 2{1/3} + 1/(3x2) = 5/6 ohm
For the 4-cube: R = 2{1/4 + 1/(4x3)} = 2/3 ohm
This formula yields the resistance from root to root of
two (n-1)-ary trees of height n/2 with their end nodes identified
(-when n is even; something similar when n is odd).
Coincidentally, the 4-cube is such an animal and thus the answer
2/3 ohms is correct in that case.
However, it does not provide the solution for n >= 5, as the hypercube
does not have quite as many edges as were counted in the formula above.
4. The Infinite Plane
For an infinite lattice: First inject a constant current I at a point; figure
out the current flows (with heavy use of symmetry). Remove that current. Draw
out a current I from the other point of interest (or inject a negative current)
and figure out the flows (identical to earlier case, but displaced and in the
other direction). By the principle of superposition, if you inject a current I
into point a and take out a current I at point b at the same time, the currents
in the paths are simply the sum of the currents obtained in the earlier two
simpler cases. As in the n-cube, find the voltage between the points of
interest, divide by I and voila'!
As an illustration, in the adjacent points case: we have a current of I/4 in
each of the four resistors:
^ |
| v
<--o--> -->o<--
| ^
v |
(inject) (take out)
And adding the currents, we have I/2 in the resistor connecting the two points.
Therefore V=(1 ohm) x I/2 and effective resistance between the points = 1/2 ohm.
You can (and showed how to) use symmetry to obtain the equivalent resistance
of 1/2 between two adjacent nodes; but I doubt that symmetry alone will give you
even the equivalent resistance of 2/pi between two diagonally adjacent nodes.
[More generally, the equivalent resistance between two nodes k diagonal units
apart is (2/pi)(1+1/3+1/5+...+1/(2k-1)); that, plus symmetry and the known
equivalent resistance between two adjacent nodes, is sufficient to derive all
equivalent resistances in the lattice.
5. Continuous sheet
Doesn't the resistance diverge in that case? The problem is that you can't
inject current at a point.
cf. "Random Walks and Electric Networks", by Doyle and Snell, published by the
Mathematical Association of America.
==> physics/sail.p <==
A sailor is in a sailboat on a river. The water (current) is flowing
downriver at a velocity of 3 knots with respect to the land. The wind
(air velocity) is zero, with respect to the land. The sailor wants
to proceed downriver as quickly as possible, maximizing his downstream
speed with respect to the land.
Should he raise the sail, or not?
==> physics/sail.s <==
Depends on the sail. If the boat is square-rigged, then not, since
raising the sail will simply increase the air resistance.
If the sailor has a fore-and-aft rig, then he should, since he can then
tack into the wind. (Imagine the boat in still water with a 3-knot head
wind).
==> physics/skid.p <==
What is the fastest way to make a 90 degree turn on a slippery road?
==> physics/skid.s <==
For higher speeds (measured at a small distance from the point of initiation
of a sharp turn) the fastest way round is to "outside loop" - that is, steer
away from the curve, and do a kidding 270.
This technique is taught in advanced driving schools.
References:
M. Freeman and P. Palffy, American Journal of Physics, vol 50, p. 1098, 1982.
P. Palffy and Unruh, American Journal of Physics, vol 49, p. 685, 1981.
==> physics/spheres.p <==
Two spheres are the same size and weight, but one is hollow. They are
made of uniform material, though of course not the same material. Without
a minimum of apparatus, how can I tell which is hollow?
==> physics/spheres.s <==
Since the balls have equal diameter and equal mass, their volume and
density are also equal. However, the mass distribution is not equal,
so they will have different moments of inertia - the hollow sphere has
its mass concentrated at the outer edge, so its moment of inertia will
be greater than the solid sphere. Applying a known torque and observing
which sphere has the largest angular acceleration will determine which
is which. An easy way to do this is to "race" the spheres down an
inclined plane with enough friction to prevent the spheres from sliding.
Then, by conservation of energy:
mgh = 1/2 mv^2 + 1/2 Iw^2
Since the spheres are rolling without sliding, there is a relationship
between velocity and angular velocity:
w = v / r
so
mgh = 1/2 mv^2 + 1/2 I (v^2 / r^2) = 1/2 (m + I/r^2) v^2
and
v^2 = 2mgh / (m + I / r^2)
From this we can see that the sphere with larger moment of inertia (I) will
have a smaller velocity when rolled from the same height, if mass and radius
are equal with the other sphere. Thus the solid sphere will roll faster.
==> physics/wind.p <==
Is a round-trip by airplane longer or shorter if there is wind blowing?
==> physics/wind.s <==
It will take longer, by the ratio (s^2)/(s^2 - w^2) where s is
the plane's speed, and w is the wind speed. The stronger the wind the
longer it will take, up until the wind speed equals the planes speed, at
which point the plane will never finish the trip.
Math:
s = plane's speed
w = wind speed
d = distance in one direction
d / (s + w) = time to complete leg flying with the wind
d / (s - w) = time to complete leg flying against the wind
d / (s + w) + d / (s - w) = round trip time
d / (s + w) + d / (s - w) = ratio of flying with wind to
------------------------- flying with no wind (bottom of
d / s + d / s equation is top with w = 0)
this simplifies to s^2 / (s^2 - w^2).
==> probability/amoeba.p <==
A jar begins with one amoeba. Every minute, every amoeba
turns into 0, 1, 2, or 3 amoebae with probability 25%
for each case ( dies, does nothing, splits into 2, or splits
into 3). What is the probability that the amoeba population
eventually dies out?
==> probability/amoeba.s <==
If p is the probability that a single amoeba's descendants will die
out eventually, the probability that N amoebas' descendents will all
die out eventually must be p^N, since each amoeba is independent of
every other amoeba. Also, the probability that a single amoeba's
descendants will die out must be independent of time when averaged
over all the possibilities. At t=0, the probability is p, at t=1 the
probability is 0.25(p^0+p^1+p^2+p^3), and these probabilities must be
equal. Extinction probability p is a root of f(p)=p. In this case,
p = sqrt(2)-1.
The generating function for the sequence P(n,i), which gives the
probability of i amoebas after n minutes, is f^n(x), where f^n(x) ==
f^(n-1) ( f(x) ), f^0(x) == x . That is, f^n is the nth composition
of f with itself.
Then f^n(0) gives the probability of 0 amoebas after n minutes, since
f^n(0) = P(n,0). We then note that:
f^(n+1)(x) = ( 1 + f^n(x) + (f^n(x))^2 + (f^n(x))^3 )/4
so that if f^(n+1)(0) -> f^n(0) we can solve the equation.
The generating function also gives an expression for the expectation
value of the number of amoebas after n minutes. This is d/dx(f^n(x))
evaluated at x=1. Using the chain rule we get f'(f^(n-1)(x))*d/dx(f^(n-1)(x))
and since f'(1) = 1.5 and f(1) = 1, we see that the result is just
1.5^n, as might be expected.
==> probability/apriori.p <==
An urn contains one hundred white and black balls. You sample one hundred
balls with replacement and they are all white. What is the probability
that all the balls are white?
==> probability/apriori.s <==
This question cannot be answered with the information given.
In general, the following formula gives the conditional probability
that all the balls are white given you have sampled one hundred balls
and they are all white:
P(100 white | 100 white samples) =
P(100 white samples | 100 white) * P(100 white)
-----------------------------------------------------------
sum(i=0 to 100) P(100 white samples | i white) * P(i white)
The probabilities P(i white) are needed to compute this formula. This
does not seem helpful, since one of these (P(100 white)) is just what we
are trying to compute. However, the following argument can be made:
Before the experiment, all possible numbers of white balls from zero to
one hundred are equally likely, so P(i white) = 1/101. Therefore, the
odds that all 100 balls are white given 100 white samples is:
P(100 white | 100 white samples) =
1 / ( sum(i=0 to 100) (i/100)^100 ) =
63.6%
This argument is fallacious, however, since we cannot assume that the urn
was prepared so that all possible numbers of white balls from zero to one
hundred are equally likely. In general, we need to know the P(i white)
in order to calculate the P(100 white | 100 white samples). Without this
information, we cannot determine the answer.
This leads to a general "problem": our judgments about the relative
likelihood of things is based on past experience. Each experience allows
us to adjust our likelihood judgment, based on prior probabilities. This
is called Bayesian inference. However, if the prior probabilities are not
known, then neither are the derived probabilities. But how are the prior
probabilities determined? For example, if we are brains in the vat of a
diabolical scientist, all of our prior experiences are illusions, and
therefore all of our prior probabilities are wrong.
All of our probability judgments indeed depend upon the assumption that
we are not brains in a vat. If this assumption is wrong, all bets are
off.
==> probability/cab.p <==
A cab was involved in a hit and run accident at night. Two cab companies,
the Green and the Blue, operate in the city. Here is some data:
a) Although the two companies are equal in size, 85% of cab
accidents in the city involve Green cabs and 15% involve Blue cabs.
b) A witness identified the cab in this particular accident as Blue.
The court tested the reliability of the witness under the same circumstances
that existed on the night of the accident and concluded that the witness
correctly identified each one of the two colors 80% of the time and failed
20% of the time.
What is the probability that the cab involved in the accident was
Blue rather than Green?
If it looks like an obvious problem in statistics, then consider the
following argument:
The probability that the color of the cab was Blue is 80%! After all,
the witness is correct 80% of the time, and this time he said it was Blue!
What else need be considered? Nothing, right?
If we look at Bayes theorem (pretty basic statistical theorem) we
should get a much lower probability. But why should we consider statistical
theorems when the problem appears so clear cut? Should we just accept the
80% figure as correct?
==> probability/cab.s <==
The police tests don't apply directly, because according to the
wording, the witness, given any mix of cabs, would get the right
answer 80% of the time. Thus given a mix of 85% green and 15% blue
cabs, he will say 20% of the green cabs and 80% of the blue cabs are
blue. That's 20% of 85% plus 80% of 15%, or 17%+12% = 29% of all the
cabs that the witness will say are blue. Of those, only 12/29 are
actually blue. Thus P(cab is blue | witness claims blue) = 12/29.
That's just a little over 40%.
Think of it this way... suppose you had a robot watching parts on a
conveyor belt to spot defective parts, and suppose the robot made a
correct determination only 50% of the time (I know, you should
probably get rid of the robot...). If one out of a billion parts are
defective, then to a very good approximation you'd expect half your
parts to be rejected by the robot. That's 500 million per billion.
But you wouldn't expect more than one of those to be genuinely
defective. So given the mix of parts, a lot more than 50% of the
REJECTED parts will be rejected by mistake (even though 50% of ALL the
parts are correctly identified, and in particular, 50% of the
defective parts are rejected).
When the biases get so enormous, things starts getting quite a bit
more in line with intuition.
For a related real-life example of probability in the courtroom see
People v. Collins, 68 Cal 2d319 (1968).
==> probability/coincidence.p <==
Name some amazing coincidences.
==> probability/coincidence.s <==
The answer to the question, "Who wrote the Bible," is, of
course, Shakespeare. The King James Version was published in
1611. Shakespeare was 46 years old then (he turned 47 later in
the year). Look up Psalm 46. Count 46 words from the beginning of
the Psalm. You will find the word "Shake." Count 46 words from
the end of the Psalm. You will find the word "Spear." An obvious
coded message. QED.
How many inches in the pole-to-pole diameter of the Earth? The
answer is almost exactly 500,000,000 inches. Proof that the inch
was defined by spacemen.
==> probability/coupon.p <==
There is a free gift in my breakfast cereal. The manufacturers say
that the gift comes in four different colours, and encourage one to
collect all four (& so eat lots of their cereal). Assuming there is
an equal chance of getting any one of the colours, what is the
expected number of packets I must plough through to get all four?
Can you generalise to n colours and/or unequal probabilities?
The entire AOH site is optimized to look best in Firefox® 3 on a widescreen monitor (1440x900 or better).
Site design & layout copyright © 1986-2010 AOH
We do not send spam. If you have received spam bearing an artofhacking.com email address, please forward it with full headers to abuse@artofhacking.com.
