| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Proposed by Steven Laffin, student, �cole J. H. Picard, and Andy Liu,
University of Alberta, Edmonton. (Dedicated to Professor David Monk,
University of Edinburgh, on his sixtieth birthday.)
Starship Venture is under attack from a Zokbar fleet, and its
Terrorizer is destroyed. While it can hold out, it needs a replacement
to drive off the Zokbars. Starbase has spare Terrorizers, which can be
taken apart into any number of components, and enough scout ships to
provide transport. However, the Zokbars have n Space Octopi, each of
which can capture one scout ship at a time. Starship Venture must have
at least one copy of each component to reassemble a Terrorizer, but it
is essential that the Zokbars should not be able to do the same. Into
how many components must each Terrorizer be taken apart (assuming all
are taken apart in an identical manner), and how many scout ships are
needed to transport them? Give two answers:
(a) assuming that the number of components per Terrorizer is as small
as possible, minimize the number of scout ships;
(b) assuming instead that the number of scout ships is as small as
possible, minimize the number of components per Terrorizer.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1673.1 | proofless proof | DESIR::BUCHANAN | The was not found. | Thu Oct 08 1992 14:05 | 33 |
> Proposed by Steven Laffin, student, �cole J. H. Picard, and Andy Liu, > University of Alberta, Edmonton. (Dedicated to Professor David Monk, > University of Edinburgh, on his sixtieth birthday.) Given the subject matter, perhaps it should be �cole J-L Picard :-) I met Monk when I was at school (in Edinburgh). Nice old duck, though I guess not so old then. Anyway, on to the problem... -------------------------------------------------------------------------------- (spoiler) (1) There must be at least n+1 components present. (2) There must be at least 2n+1 scout ships. So let's try and solve each case: (a) Suppose there are exactly n+1 components. No two different components may travel in the same scout ship. There must be at least n+1 Terrorizers. Therefore (n+1)^2 scout ships are needed. They will suffice. (b) Suppose there are exactly 2n+1 scout ships. Any selection of n ships must lack a component No 2 selections of n ships must lack the same component. Therefore (2n+1)-choose-n components are needed. They will suffice. Andrew. | |||||