Web    Images    Groups    News    Froogle

Does anyone have examples of puzzle which can be *answered*
without being completely *solved*, e.g. non-constructively or using
the extra assumption that a solution exists?

For example, a friend of mine was given the following puzzle at
a job interview: 2 players alternate in placing non-overlapping
identical coins on a circular table, and the last player to move
wins; which player has a winning strategy?

One approach to this puzzle is to actually find the winning
strategy (a nice problem). But there is a shortcut using meta-information
implicit in the question: since nothing is said about the size of the table,
we can assume that it has the same size as the coin, so player 1 wins.
This doesn't give any information at all on what the winning strategy is,
but it suffices to answer the question.

Tal Kubo (kubo@zariski.harvard.edu) wrote:

: For example, a friend of mine was given the following puzzle at
: a job interview: 2 players alternate in placing non-overlapping
: identical coins on a circular table, and the last player to move
: wins; which player has a winning strategy?
: One approach to this puzzle is to actually find the winning
: strategy (a nice problem). But there is a shortcut using meta-information
: implicit in the question: since nothing is said about the size of the table,
: we can assume that it has the same size as the coin, so player 1 wins.
: This doesn't give any information at all on what the winning strategy is,
: but it suffices to answer the question.
There's a more applicable and more elegant solution to this problem. I
say more applicable, because you don't need a table the size of the coin.
After all, there's no guarantee a priori that the solution will hold in
all cases, including exceptional ones like the one mentioned. (It does
turn out to be true, however.)
Anyway, the first player puts his coin exactly in the center of the table
and thereafter he mirrors the move of the second player, making each of
his successive plays the reflection through the circle center of player
two's previous move. Obviously, he will always win.
This also shows that were one to play on a circular torus rather than a
torus (ie, a doughnut) player two would always win. If one tried to solve
the torus question by picking the exceptional case where the inner radius
goes to zero, he would arrive at the wrong answer. (Of course, any
mathematician will quickly point out that a disc and a torus are in diff.
genera so that it would be completely foolish to consider one as the
limiting case of the other.)
Mark
mdp1@crux2.cit.cornell.edu

In article <1994Jul6.164628.33360@hulaw1.harvard.edu>, kubo@zariski.harvard.edu (Tal Kubo) writes:
>
> Does anyone have examples of puzzle which can be *answered*
> without being completely *solved*, e.g. non-constructively or using
> the extra assumption that a solution exists?
> 
[ example problem deleted ]
Another one:
you are going to drill a hole through a sphere. The hole is centered
on the center of the sphere.
If the resulting hole is 6" long, what is the volume of the
remaining sphere?
Answer:
Since we can assume an answer exists, let the diameter of the hole approach
zero, and then the length of the hole is the diameter of the sphere, so
the remaining volume is 4/3 pi * 3*3, regardless of the size of the
hole drilled.
--
Geoff Hazel ghazel@eskimo.com
Edmark Corporation 206-556-8445
Box 3218, Redmond, WA "the syntax is painful"

Geoff Hazel (ghazel@eskimo.com) wrote:

: you are going to drill a hole through a sphere. The hole is centered
: on the center of the sphere.
: If the resulting hole is 6" long, what is the volume of the
: remaining sphere?
: Answer:
: Since we can assume an answer exists, let the diameter of the hole approach
: zero, and then the length of the hole is the diameter of the sphere, so
: the remaining volume is 4/3 pi * 3*3, regardless of the size of the
: hole drilled.
This is very bad logic. It is analogous to saying that the hole has no
volume regardless of how large it is. Certainly, I'll agree that if the hole
diameter approaches zero then the remaining volume is 36 pi. However, it
is not stated anywhere in the question that the hole does have infinitessimal
width. This is also different than the puzzle original posed by Tal Kubo
in that in his there is at least some implication that a unique solution
exists. (ie, the interviewer asks which player has the winning strategy
and perhaps one can conclude that one player does have such a strategy or
the question would not have been asked. Even there the logic is a little
iffy, but the hole in the sphere problem simply makes no sense at all.)
Mark
mdp1@crux2.cit.cornell.edu

In article <2vl4gv$38s@newsstand.cit.cornell.edu>,
Mark <mdp1@crux2.cit.cornell.edu> wrote:
>Geoff Hazel (ghazel@eskimo.com) wrote:
>
>: you are going to drill a hole through a sphere. The hole is centered
>: on the center of the sphere.
>: If the resulting hole is 6" long, what is the volume of the
>: remaining sphere?
>: Answer:
>: Since we can assume an answer exists, let the diameter of the hole approach
>: zero, and then the length of the hole is the diameter of the sphere, so
>: the remaining volume is 4/3 pi * 3*3, regardless of the size of the
>: hole drilled.
>
>This is very bad logic. It is analogous to saying that the hole has no
>volume regardless of how large it is.
No it isn't. The idea is that, _if_ the question can be answered from
the information given, _then_ the width of the hole is irrelevant, so
we can assume whatever width we want (which makes the calculation
easier).
> Certainly, I'll agree that if the hole
>diameter approaches zero then the remaining volume is 36 pi. However, it
>is not stated anywhere in the question that the hole does have infinitessimal
>width. This is also different than the puzzle original posed by Tal Kubo
>in that in his there is at least some implication that a unique solution
>exists.
But there is! If you do all the necessary arithmetic, you'll find
that the remaining volume is independent of the width of the hole
(providing that the length of the hole is measured by a ruler along
its side).
Seth

Just after reading some of the earlier articles in this thread, I was
doing a puzzle in the current issue of Games's companion magazine
"Games World of Puzzles". It was one of their "solitaire battleships"
puzzles, which work like this (my paraphrase):

You have to place the following "ships" on a 10x10 grid:

 1 battleship, 4x1
 2 cruisers, 3x1
 3 destroyers, 2x1
 4 submarines, 1x1

Each ship occupies consecutive squares along a single row or column
(not diagonal). All of the adjacent squares to each ship (including
diagonally adjacent) are vacant. You are given the number of occupied
squares in each row and column, and (usually) partial information about
a few of the squares.

In this particular puzzle, the rows (call them 0 to 9, top to bottom
of diagram) respectively have 4, 1, 2, 1, 0, 2, 0, 4, 2, 4 occupied
squares; the columns (A to J, left to right), 1, 2, 2, 3, 3, 0, 6,
1, 1, 1. There is a submarine at G3. Fill in the rest.

For example, you can immediately observe that the battleship must go
along column G or row 0, 7, or 9, because those are the only ones with
at least 4 squares occupied. But column G is ruled out because there
are 0 squares occupied in rows 4 and 6, so it's somewhere in row 0,
7, or 9.

Now, the reason that the puzzle fits the thread is Games's unstated rule
that puzzles where you have to find a definite solution always have a
unique solution. So what you have to realize is...

the unoccupied row 6 means that no ships occupying any part of rows
7-9 extend into the rest of the grid. But the occupancy counts for
rows 7-9 form a symmetrical pattern: 4, 2, 4. *If there is a unique
solution, then* the arrangement of ships in those rows must have the
same symmetry. Since there is only one battleship, it can't be put
along row 7 or row 9 -- and hence it's along row 0.

Also, since column A has an occupancy count of 1, A7 and A9 cannot
both be occupied; therefore by symmetry, neither one is. Similarly
in columns H, I, and J. This constrains the occupied squares nicely.

Now, the battleship makes up all four occupied squares of row 0, so there
is no ship running vertically from row 0. Therefore G0 and G1 are not
*both* occupied. Neither are G2 or G4, being adjacent to the submarine,
or G6, since row 6 is vacant. The occupancy count of 6 for column
G then requires G7-G9 to be occupied, i.e. with a cruiser, and G5 to
be occupied also.

From the occupancy counts, the only remaining places for the second
cruiser are rows 7 and 9 and columns D and E. We now use the symmetry
one more time and deduce that it cannot be along row 7 or row 9, as
they would each have to have one. So it's along column D or E...

The rest is left as an exercise for the reader. The answer is:

G0-J0, E7-E9, G7-G9, D1-D2, B7-C7, B9-C9, A2, G3, D5, G5.
--
Mark Brader, msb@sq.com, SoftQuad Inc., Toronto
#define MSB(type) (~(((unsigned type)-1)>>1))

In <1994Jul15.070738.27964@sq.sq.com> msb@sq.sq.com (Mark Brader) writes:
]You have to place the following "ships" on a 10x10 grid:
] 1 battleship, 4x1
] 2 cruisers, 3x1
] 3 destroyers, 2x1
] 4 submarines, 1x1
]Each ship occupies consecutive squares along a single row or column
](not diagonal). All of the adjacent squares to each ship (including
]diagonally adjacent) are vacant....
]
]In this particular puzzle, the rows (call them 0 to 9, top to bottom
]of diagram) respectively have 4, 1, 2, 1, 0, 2, 0, 4, 2, 4 occupied
]squares; the columns (A to J, left to right), 1, 2, 2, 3, 3, 0, 6,
]1, 1, 1. There is a submarine at G3. Fill in the rest.

Here's a puzzle that's (now) very easy to answer although not so easy to solve:

In my copy of "Games World of Puzzles" I found exactly the same
puzzle as Mark, but someone had carelessly dropped a cigarette butt
and thus
 "There is a submarine at G3."
was replaced with
 "There is a submarine at ()."
It's asking a lot to find all ten ships now. Just tell me where the
battleship and cruisers are.

James

And for "extra credit":
Gurer ner bayl gjb cynprf jurer gur fhoznevar pbhyq unir orra fcrpvsvrq
gb tvir gur bevtvany ceboyrz n havdhr fbyhgvba, T3 naq ??.

In article <1994Jul6.164628.33360@hulaw1.harvard.edu>
 kubo@zariski.harvard.edu "Tal Kubo" writes:

> For example, a friend of mine was given the following puzzle at
> a job interview: 2 players alternate in placing non-overlapping
> identical coins on a circular table, and the last player to move
> wins; which player has a winning strategy?
>
> One approach to this puzzle is to actually find the winning
> strategy (a nice problem). But there is a shortcut using meta-information
> implicit in the question: since nothing is said about the size of the table,
> we can assume that it has the same size as the coin, so player 1 wins.
> This doesn't give any information at all on what the winning strategy is,
> but it suffices to answer the question.
But if nothing is said about the size of the table, maybe its too small
to hold even one coin. I would expect this to be considered either a
draw or a win for player 2 (since player 1 is due to move and cannot).
Also, the problem does not say that a player cannot remove or move
coins already placed. If coins can be moved but not removed, stating
that player 1 can always win is equivalent to saying that all
circular tables hold an odd number of coins.
--
Charles Bryant (ch@chch.demon.co.uk)

Charles Bryant (ch@chch.demon.co.uk) wrote:
: In article <1994Jul6.164628.33360@hulaw1.harvard.edu>
: kubo@zariski.harvard.edu "Tal Kubo" writes: 
: > For example, a friend of mine was given the following puzzle at
: > a job interview: 2 players alternate in placing non-overlapping
: > identical coins on a circular table, and the last player to move
: > wins; which player has a winning strategy?
: >
: > One approach to this puzzle is to actually find the winning
: > strategy (a nice problem). But there is a shortcut using meta-information
: > implicit in the question: since nothing is said about the size of the table,
: > we can assume that it has the same size as the coin, so player 1 wins.
: > This doesn't give any information at all on what the winning strategy is,
: > but it suffices to answer the question. 
: But if nothing is said about the size of the table, maybe its too small
: to hold even one coin. I would expect this to be considered either a
: draw or a win for player 2 (since player 1 is due to move and cannot).
good point.
: Also, the problem does not say that a player cannot remove or move
: coins already placed. If coins can be moved but not removed, stating
: that player 1 can always win is equivalent to saying that all
: circular tables hold an odd number of coins.
bad point. This does not imply that all circular tables hold an odd number
of coins. It simply means that by playing his coins properly (see my
original solution for player 1's winning strategy) player 1 can ensure
that the table will hold only an odd number of coins (again assuming that
the table is large enough to hold even one). As you will also see/infer
from my original solution, if player 1 makes a bad first move then player
2 can ensure that the table will only hold an even number of coins. An
example of such a bad first move would be placing his first coin adajcent
(or even within r, the coin radius) of the center of the table.
Mark
mdp1@crux2.cit.cornell.edu

In article <2vl4us$38s@newsstand.cit.cornell.edu>
 mdp1@crux2.cit.cornell.edu "Mark" writes:

> Charles Bryant (ch@chch.demon.co.uk) wrote:
> : In article <1994Jul6.164628.33360@hulaw1.harvard.edu>
> : kubo@zariski.harvard.edu "Tal Kubo" writes: 
> : > For example, a friend of mine was given the following puzzle at
> : > a job interview: 2 players alternate in placing non-overlapping
> : > identical coins on a circular table, and the last player to move
> : > wins; which player has a winning strategy?
> :
> : Also, the problem does not say that a player cannot remove or move
> : coins already placed. If coins can be moved but not removed, stating ^^^^^^^^^^^^^^^^^^
> : that player 1 can always win is equivalent to saying that all
> : circular tables hold an odd number of coins.
>
> bad point. This does not imply that all circular tables hold an odd number
> of coins. It simply means that by playing his coins properly (see my
> original solution for player 1's winning strategy) player 1 can ensure
> that the table will hold only an odd number of coins (again assuming that
> the table is large enough to hold even one).
But if player 2 can move the coins the position of coins already down
is irrelevant. Only the number of them influences the conclusion.
--
Charles Bryant (ch@chch.demon.co.uk)