Web    Images    Groups    News    Froogle

From: (kubo@zariski.harvard.edu)
Subject: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-06 14:42:11 PST
`Does anyone have examples of puzzle which can be *answered*without being completely *solved*, e.g. non-constructively or usingthe extra assumption that a solution exists?For example, a friend of mine was given the following puzzle ata job interview: 2 players alternate in placing non-overlappingidentical coins on a circular table, and the last player to movewins; which player has a winning strategy?One approach to this puzzle is to actually find the winningstrategy (a nice problem). But there is a shortcut using meta-informationimplicit 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.`
From: (mdp1@crux2.cit.cornell.edu)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-06 18:57:24 PST
`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. Isay 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 inall cases, including exceptional ones like the one mentioned. (It doesturn out to be true, however.)Anyway, the first player puts his coin exactly in the center of the tableand thereafter he mirrors the move of the second player, making each ofhis successive plays the reflection through the circle center of playertwo's previous move. Obviously, he will always win.This also shows that were one to play on a circular torus rather than atorus (ie, a doughnut) player two would always win. If one tried to solvethe torus question by picking the exceptional case where the inner radiusgoes to zero, he would arrive at the wrong answer. (Of course, anymathematician 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 thelimiting case of the other.)Markmdp1@crux2.cit.cornell.edu`
From: (ghazel@eskimo.com)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-08 14:37:07 PST
`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 centeredon the center of the sphere.If the resulting hole is 6" long, what is the volume of theremaining sphere?Answer:Since we can assume an answer exists, let the diameter of the hole approachzero, and then the length of the hole is the diameter of the sphere, sothe remaining volume is 4/3 pi * 3*3, regardless of the size of thehole drilled.--Geoff Hazel ghazel@eskimo.comEdmark Corporation 206-556-8445Box 3218, Redmond, WA "the syntax is painful"`
From: (mdp1@crux2.cit.cornell.edu)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-08 20:12:04 PST
`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 novolume regardless of how large it is. Certainly, I'll agree that if the holediameter approaches zero then the remaining volume is 36 pi. However, itis not stated anywhere in the question that the hole does have infinitessimalwidth. This is also different than the puzzle original posed by Tal Kuboin that in his there is at least some implication that a unique solutionexists. (ie, the interviewer asks which player has the winning strategyand perhaps one can conclude that one player does have such a strategy orthe question would not have been asked. Even there the logic is a littleiffy, but the hole in the sphere problem simply makes no sense at all.)Markmdp1@crux2.cit.cornell.edu`
From: (sethb@panix.com)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-09 19:01:58 PST
`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 fromthe information given, _then_ the width of the hole is irrelevant, sowe can assume whatever width we want (which makes the calculationeasier).> 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 findthat the remaining volume is independent of the width of the hole(providing that the length of the hole is measured by a ruler alongits side).Seth`
From: (msb@sq.sq.com)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-15 00:46:08 PST
`Just after reading some of the earlier articles in this thread, I wasdoing 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, 1x1Each ship occupies consecutive squares along a single row or column(not diagonal). All of the adjacent squares to each ship (includingdiagonally adjacent) are vacant. You are given the number of occupiedsquares in each row and column, and (usually) partial information abouta few of the squares.In this particular puzzle, the rows (call them 0 to 9, top to bottomof diagram) respectively have 4, 1, 2, 1, 0, 2, 0, 4, 2, 4 occupiedsquares; 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 goalong column G or row 0, 7, or 9, because those are the only ones withat least 4 squares occupied. But column G is ruled out because thereare 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 rulethat puzzles where you have to find a definite solution always have aunique solution. So what you have to realize is...the unoccupied row 6 means that no ships occupying any part of rows7-9 extend into the rest of the grid. But the occupancy counts forrows 7-9 form a symmetrical pattern: 4, 2, 4. *If there is a uniquesolution, then* the arrangement of ships in those rows must have thesame symmetry. Since there is only one battleship, it can't be putalong 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 cannotboth be occupied; therefore by symmetry, neither one is. Similarlyin columns H, I, and J. This constrains the occupied squares nicely.Now, the battleship makes up all four occupied squares of row 0, so thereis 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 columnG then requires G7-G9 to be occupied, i.e. with a cruiser, and G5 tobe occupied also.From the occupancy counts, the only remaining places for the secondcruiser are rows 7 and 9 and columns D and E. We now use the symmetryone more time and deduce that it cannot be along row 7 or row 9, asthey 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))`
From: (james@crc.ricoh.com)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-17 20:01:43 PST
`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 samepuzzle as Mark, but someone had carelessly dropped a cigarette buttand 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 thebattleship and cruisers are.JamesAnd for "extra credit":Gurer ner bayl gjb cynprf jurer gur fhoznevar pbhyq unir orra fcrpvsvrqgb tvir gur bevtvany ceboyrz n havdhr fbyhgvba, T3 naq ??.`
From: (ch@chch.demon.co.uk)
Subject: Re: Easier to Answer than to Solve
Newsgroups:
Date: 1994-07-08 19:30:31 PST
`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 smallto hold even one coin. I would expect this to be considered either adraw 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 movecoins already placed. If coins can be moved but not removed, statingthat player 1 can always win is equivalent to saying that allcircular 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 numberof coins. It simply means that by playing his coins properly (see myoriginal solution for player 1's winning strategy) player 1 can ensurethat the table will hold only an odd number of coins (again assuming thatthe table is large enough to hold even one). As you will also see/inferfrom my original solution, if player 1 makes a bad first move then player2 can ensure that the table will only hold an even number of coins. Anexample 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.Markmdp1@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 downis irrelevant. Only the number of them influences the conclusion.--Charles Bryant (ch@chch.demon.co.uk)`