Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

18 views

Skip to first unread message

Jul 6, 1994, 4:46:27 PM7/6/94

to

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.

Jul 6, 1994, 9:37:01 PM7/6/94

to

Tal Kubo (ku...@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.)

Jul 8, 1994, 3:56:52 PM7/8/94

to

In article <1994Jul6.1...@hulaw1.harvard.edu>, ku...@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 ]>

> 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?

>

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 gha...@eskimo.com

Edmark Corporation 206-556-8445

Box 3218, Redmond, WA "the syntax is painful"

Jul 8, 1994, 8:19:16 PM7/8/94

to

In article <1994Jul6.1...@hulaw1.harvard.edu>

ku...@zariski.harvard.edu "Tal Kubo" writes:

ku...@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 (c...@chch.demon.co.uk)

Jul 8, 1994, 11:11:27 PM7/8/94

to

Geoff Hazel (gha...@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.)

Jul 8, 1994, 11:18:52 PM7/8/94

to

Charles Bryant (c...@chch.demon.co.uk) wrote:

: In article <1994Jul6.1...@hulaw1.harvard.edu>

: ku...@zariski.harvard.edu "Tal Kubo" writes:

: In article <1994Jul6.1...@hulaw1.harvard.edu>

: ku...@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.

Jul 9, 1994, 10:01:33 PM7/9/94

to

In article <2vl4gv$3...@newsstand.cit.cornell.edu>,

Mark <md...@crux2.cit.cornell.edu> wrote:

>Geoff Hazel (gha...@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.

Mark <md...@crux2.cit.cornell.edu> wrote:

>Geoff Hazel (gha...@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

Jul 15, 1994, 3:07:38 AM7/15/94

to

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, m...@sq.com, SoftQuad Inc., Toronto

#define MSB(type) (~(((unsigned type)-1)>>1))

Jul 14, 1994, 4:22:19 PM7/14/94

to

In article <2vl4us$3...@newsstand.cit.cornell.edu>

md...@crux2.cit.cornell.edu "Mark" writes:

md...@crux2.cit.cornell.edu "Mark" writes:

> Charles Bryant (c...@chch.demon.co.uk) wrote:

> : In article <1994Jul6.1...@hulaw1.harvard.edu>

> : ku...@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 (c...@chch.demon.co.uk)

Jul 17, 1994, 10:46:57 PM7/17/94

to

In <1994Jul15.0...@sq.sq.com> m...@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.

]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

]

]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 ??.

0 new messages

Search

Clear search

Close search

Google apps

Main menu