WWW.ABSTRACT.DISLIB.INFO FREE ELECTRONIC LIBRARY - Abstracts, online materials

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 19 | 20 || 22 |

# «Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»

-- [ Page 21 ] --

We are now ready to prove the theorem. We shall argue by contradiction, supposing that Ñ´Äµ ½. The contradiction will be to show that under this assumption É has a winning strategy. The basic idea resembles Nash’s proof that the ﬁrst player has a winning strategy for Hex, in that we will describe a new strategy for É in which (in effect) É makes an extra move and then plays the reﬂected version ÄÊ of È ’s hypothetical winning strategy Ä. (Note that Ñ´Äµ Ñ´Ä Ê µ.) The proof is complicated, however, by the fact that it is not clear a priori that having an extra stone on the board is either an advantage or a disadvantage. The proof splits into two cases depending on whether É is the ﬁrst player or the second.

Suppose that É is the ﬁrst player. Player É applies the following strategy. She makes an arbitrary ﬁrst move, and draws a circle around the cell containing this move. From now on she applies strategy Ä Ê in what we shall call the imaginary game. The state of this game is exactly like that of the real game, except that in the imaginary game the encircled cell is empty, while in the real game, that cell contains a É-stone. This relationship will be maintained throughout the game. When the strategy Ä Ê requires É to play in the encircled cell, she plays instead into another empty cell (chosen arbitrarily), erases the circle, and draws a new circle around the move just played. Because Ñ´ÄÊ µ ½, when it is È ’s turn to move there must be at least two empty cells in the imaginary game, and there must be at least one empty cell in the real game. Therefore it is possible for È to move. (We’ll see below that È will not have won the real game.) Similarly, when it is É’s turn to move there must be at least three empty cells in the imaginary game, so there are at least two empty cells in the real game. Thus the real game can continue.

Eventually É will win the imaginary game because Ä Ê is a winning strategy. When this happens she has also won the real game, because of the monotonicity property. This contradicts our assumption that È has a winning strategy.

Now, suppose that É is the second player. Let Ô ¼ be È ’s ﬁrst move.

Player É begins by encircling Ô¼, playing out ÄÊ in an imaginary game.

240 J. LAGARIAS AND D. SLEATOR The imaginary game and the real game differ in up to two places, as follows. The imaginary game is obtained from the real game by ﬁrst changing Ô¼ from È ’s stone to É’s stone, then by erasing the stone in the encircled cell. If the strategy ÄÊ requires a move into the encircled cell, then É arbitrarily chooses a different empty cell in which to move, and transfers the circle from its current location to the new cell. The fact that Ñ´Ä Ê µ ½ ensures that both players can continue to move. It is easy to see that the relationship between the real game and the imaginary game is maintained.

Player É eventually wins the imaginary game. The position in the real game is obtained from the position in the imaginary game by putting É’s stone in the encircled cell, and changing the contents of Ô¼ from a É-stone to a È -stone. The position in the imaginary game is a winning position for É, and the monotonicity property ensures that the corresponding position in the real game is also a win for É. This contradicts our assumption that È has a winning strategy.

References [1] A. Beck, M. Bleicher, and J. Crow, Excursions into Mathematics, Worth, New York, 1969, pp. 327–339.

[2] R. Evans, A winning Opening in Reverse Hex, J. Recreational Mathematics, 7(3), Summer 1974, pp 189–192.

[3] D. Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly, 86 (10), 1979, pp. 818–827.

[4] M. Gardner, The Scientiﬁc American Book of Mathematical Puzzles and Diversions, Simon and Schuster, New York, 1959, pp. 73–83.

[5] Y. Yamasaki, Theory of Division Games, Publ. Res. Inst. Math. Sci., Kyoto Univ.

14, 1978, pp. 337–358.

An Update on Odd Neighbors and Odd Neighborhoods Leslie E. Shader

Some time ago (1986–88) this problem appeared in mathematical circles:

Problem 1: Can the unit squares of an Ò ¢Ò sheet of graph paper be labeled with 0’s and 1’s so that every neighborhood is odd?

A neighborhood, Æ, of square, is the set of squares sharing an edge with square and does include square. A neighborhood, Æ is odd if there are an odd number of squares in Æ with labels “1".

Figure 1 shows a 4 ¢ 4 example with a desired labeling.

–  –  –

But is symmetric, so Ý Ý Ì ¼. Therefore, ÝÝÌ ¼ and rank´ · Áµ rank ´ · Á ½µ, so ´ · ÁµÜ ½ for every adjacency matrix. Finally, for every graph, the vertices of can be labeled with 0’s and 1’s so that every neighborhood in is odd.

If we think of the unit squares in Problem 1 as vertices of and Ú Ú is ´µ Ú shares an edge with Ú, then Theorem 1 implies that an edge in the squares of the Ò ¢ Ò square can be labeled with 0’s and 1’s so that each neighborhood is odd.

Now for some new questions (at least at the time that this paper was submitted).

The Developer’s Dilemma Suppose a real estate developer has an inﬁnite (at least sufﬁciently long) strip of land Ñ lots wide.

–  –  –

Further, we assume all lots in the ﬁrst strip of Ñ lots have been sold. It is quite possible that some of the buyers are odd, and some are not odd. Is there an Ò so that the developer can sell all the lots in the Ñ ¢ Ò rectangle and satisfy the politically correct criteria that all neighborhoods have an odd number of odd neighbors?

When this paper was originally written, the answer to the Developer’s Dilemma was unknown. We will generalize, as before, to all graphs and prove a theorem. But this time the generalization does not yield a solution to the Developer’s Dilemma. However, a proof that the Dilemma can be solved will also be presented.

Theorem 2. Let be a graph with vertices labeled with 0’s and 1’s in any way.

If not all neighborhoods of are odd, then can be embedded in a graph ¼, with all neighborhoods in ¼ odd.

## ODD NEIGHBORS AND ODD NEIGHBORHOODS 243

It is rather interesting that only one vertex must be added to in order to prove Theorem 2.

–  –  –

since the sum counts the edges from vertices labeled 1 exactly twice. Hence, there are an even number of vertices ¾ labeled 1 and Æ is even in.

These vertices now are all connected to Û with label 1. So Æ Û is odd ¾ ¼.

Theorem 3. The Developer’s Dilemma can be solved.

Proof. Let the Ñ ¢ ½ strip of unit squares be horizontal. We call Ú ½, any 0–1 Ñ-tuple, a “starter" for the Ñ ¢ Ò rectangle we seek. We wish to construct a proper labeling of an Ñ ¢ Ò rectangle so that all neighborhoods are odd and the vector Ú½ is the “starter" column.

Perhaps the Ñ ¢ ½ rectangle using the starter Ú ½ has the property that all neighborhoods are odd. Figure 3 shows that this phenomenon can happen.

–  –  –

· is odd, let Ü½ ¼, otherwise Ü½ ½.

If · · is odd, let Ü¾ ¼, otherwise Ü¾ ½.

If · · is odd, let Ü¿ ¼, otherwise Ü¿ ½.

If · · is odd, let Ü ¼, otherwise Ü ½.

If · is odd, let Ü ¼, otherwise Ü ½.

If Of course, Ñ is not limited to the value 5. Now that every neighborhood for Ú½ is odd, we can repeat the process for column 2. Each neighborhood will now have all but one entry labeled, and that label can be assigned so that the neighborhood is odd.

This process can be repeated as many times as we like, and each new column will be dependent on just the preceding two. We will have a solution to our problem if the Ò · ½ column has all entries 0, i.e., Æ Ò is odd for square Ú in column Ò Ò. Since there are only a ﬁnite number of adjacent pairs of the Ñ-tuple, either we get a column of 0’s or there must be an adjacent pair that repeats in our process. Let Ú Ú ·½ be the ﬁrst pair that repeats. We can generate new columns moving from left to right or from right to left, and we generate a second Ú Ú ·½ somewhere to the right of the ﬁrst Ú Ú ·½ (see Figure 4).

## Ú½ ¡ ¡ ¡Ú Ú ·½ ¡ ¡ ¡Ú Ú ·½

Figure 4.

Using the second occurrence of Ú Ú ·½, column Ú  ½ must repeat to the left of the ﬁrst occurrence of Ú Ú ·½.

## Ú½ ¡ ¡ ¡Ú  ½Ú Ú ·½ ¡ ¡ ¡Ú  ½ Ú Ú ·½

So Ú Ú ·½ is not the ﬁrst repeating pair. Contradiction! Hence there is a column of 0’s and the proof is complete.

Figure 5 shows an example where Ú ½ col´¼¼½½¼µ, and Ò.

–  –  –

The Problem It is well known that a ray of light can reﬂect many times between two ordinary line mirrors. If we introduce the condition that a ray should reﬂect only one point on the mirror — reducing the mirrors to point mirrors — we ﬁnd a maximum of three reﬂections for two mirrors and seven reﬂections for three mirrors, if these are suitably placed and oriented. Solutions are shown in Figure 1.

Figure 1. Maximum number of reﬂections for two and three point mirrors (E = entrance mirror, P = perpendicularly reﬂecting mirror).

This suggests an intriguing problem: How must Æ point mirrors be placed and oriented to reﬂect an entering ray of light as often as possible between these mirrors? What is the maximum number of reﬂections for varying Æ?

Upper Limits. From Figure 1 we can see that after some reﬂections the ray of light is reﬂected perpendicularly onto a mirror P and returns along the same paths but in the opposite direction. If the ray would not return along the entry paths, passing once again by entrance mirror E, half of the potential reﬂections would not be used. It is obvious that the strategy of 246 M. O. VAN DEVENTER

Figure 2. Number of reﬂections for different mirror types.

using a perpendicularly reﬂecting mirror P yields the maximum number of reﬂections.

At each mirror a maximum of Æ   ½ rays can be reﬂected, going to every other mirror. At mirror E there can be one additional reﬂection for the entering ray. Therefore, the theoretical maximum number of reﬂections is Æ´Æ   ½µ · ½, or Æ¾   Æ · ½ Ê½ ´½ µ However, for even Æ there is a parity complication. Only at mirror P can there be an odd number of reﬂections. At all other mirrors there must be an even number of reﬂections, since the light paths are used in two directions;

see Figure 2.

At mirror E there can be at most Æ reﬂections, Æ   ½ from the other mirrors and one from the entering ray. At mirror P there can be at most Æ ½ reﬂections, from the other mirrors, which is an odd number. However, at the other Æ   ¾ mirrors (other than the E and P mirrors) there can’t be Æ   ½ reﬂections, but only Æ   ¾ to make it an even number. So the upper limit for an even number of mirrors is Æ · ´Æ   ½µ · ´Æ   ¾µ´Æ   ¾µ or Æ ¾   ¾Æ · ¿ Ê¾ ´½ µ For odd Æ the parities are okay if E and P are the same mirror, so Ê½ remains valid.

Mirrors on the Corners of a Regular Polygon Can the theoretical maxima Ê ½ and Ê¾ be achieved for any Æ, and what should the positions and the orientations of the mirrors be? A well-known geometrical property may help us: When the Æ mirrors are put on the corners of a regular Æ-gon, the angle between all the neighboring pairs of light paths is 180 Æ Æ, as shown for the regular pentagon in Figure 3.

POINT MIRROR REFLECTION 247

Figure 3. Light paths in a regular pentagon.

Using such an Æ-gon grid, two-dimensional space is sufﬁcient to ﬁnd solutions for each Æ. Only discrete orientations of the mirror are allowed and are multiples of 90 Æ Æ, say Ñ ¢ ¼Æ Æ. For Ñ ¼ we have the normal orientation, Ñ ½ yields a rotation of one step clockwise, and so on. This is illustrated in Figure 4.

Figure 4. Rotation of a mirror.

Prime Number of Mirrors. For prime Æ the maximum number of reﬂections can always be achieved. We take Ñ ½ for E (= P) and Ñ ¼ for all other mirrors. The ray of light, starting at mirror E, makes hops of one mirror; after passing mirror E again, it makes hops of two mirrors, and so on. Since Æ is prime, the ray will pass every mirror once at each tour from E to E; see Figure 5.

Non-Prime Number of Mirrors. If the number of mirrors is non-prime, the investigation of various cases is less straightforward. A systematical trialand-error search for the maximum number of reﬂections may be performed

using the following strategy:

Step 1. Draw the Æ-gon and all possible light paths (the Æ-gon grid).

Add the starting ray at an angle of ½ ¼ Æ Æ with the Æ-gon.

Step 2. Omit one or more light paths (lines of the Æ-gon grid), and adjust the mirror orientations such that symmetry of light paths is preserved at every mirror and such that only at mirror P is there a perpendicular reﬂection.

Prevent any obvious loops, since a ray can neither enter nor leave such a loop.

248 M. O. VAN DEVENTER

Figure 5. Reﬂection diagrams for prime numbers of mirrors.

Step 3. Count the number of reﬂections by following the entering ray.

Calculate whether the number of reﬂections is equal to two times the number of remaining light paths plus one. If this is true, there are no loops and all of the remaining light paths are used. If not, reject the candidate solution.

Repeat Steps 2 and 3 for all candidates missing one light path, then for all candidates missing two light paths, and so on, until one or more solutions are found.

Figure 6 illustrates the procedure for the case of six mirrors. At least two light paths have to be omitted for Step 2. The candidate has 13 light paths.

Pages:     | 1 |   ...   | 19 | 20 || 22 |

Similar works:

«Lingering Too Long. Report Card on Child and Family Poverty on Prince Edward Island Third Annual Report of Child and Family Poverty on Prince Edward Island, November 24, 2016 by MacKillop Centre for Social Justice with PEI Coalition for a Poverty Eradication Strategy Introduction Each year there are scores of brave people who let us know that life is difficult and that they are struggling because their income is insufficient to meet their needs. Some are seniors who live at home and whose...»

«` Making the Most of an Enterprise Architecture Modeling Tool Aurelijus Morkevicius Product Manager for the UPDM plugin for MagicDraw and Cameo Enterprise Architecture aurelijus.morkevicius@nomagic.com Contents Introduction A Process: Making the Most of an EA Modeling Tool Set Up Requirements Pick the Right Tool Make the Tool Follow Your Rules Visualize Share Analyze Measure Gain Conclusion © 2011 No Magic, Inc. 2 Introduction Modern enterprises are based on complex business systems that are...»

«1 RAPPORT À MONSIEUR LE PREMIER MINISTRE Suicides des jeunes Amérindiens en Guyane française: 37 propositions pour enrayer ces drames et créer les conditions d'un mieux-être Rapport établi par Madame Aline ARCHIMBAUD et Madame Marie-Anne CHAPDELAINE Sénatrice de Seine-Saint-Denis Députée d’Ille-et-Vilaine Parlementaires en mission auprès de Madame la ministre des Outre-mer Remis le 30 novembre 2015 LETTRES DE MISSION REMERCIEMENTS Modestie et détermination ont présidé à...»

«St Luke the Physician Church, Benchill Annual Report of the Parochial Church Council for Year Ended 31st December 2014 Administrative information St Luke's Church is situated in Benchill, Wythenshawe. It is part of the Diocese of Manchester within the Church of England, The correspondence address is St Luke's Vicarage, Brownley Road, Benchill. The Parochial Church Council (PCC) is a charity excepted from registration with the Charity Commission PCC members who have served from 1 January 2014...»

«FLUIDES FRIGORIGENES DELIVRANCE DES ATTESTATIONS DE CAPACITE AUX OPERATEURS Délivrer les attestations prévues à l'article R. 543-99 du code Prestation objet de l’agrément: l'environnement ; suivi des tutélaires ; communiquer à tout autre organisme agréé les informations sur un opérateur selon les conditions de l'article R. 543-113 du code de l'environnement ; suspendre ou retirer l'attestation de capacité ; transmettre les données relatives aux fluides frigorigènes des opérateurs...»

«Journal of Phonetics (1996) 24, 491 – 511 Letter to the Editor The discreteness of phonetic elements and formal linguistics: response to A. Manaster Ramer Robert F. Port Department of Linguistics, Department of Computer Science, Program in Cogniti e Science, Indiana Uni ersity, Bloomington, IN 47405, U.S.A. The phenomenon of ‘‘incomplete neutralization’’ and the subtlety of this incompleteness reveal vividly that speech sounds do not fall into discretely distinct phonetic types,...»

«COMPREHENSIVE PLAN Town of Rose Waushara County, Wisconsin Adopted August 6, 2007 Prepared by the East Central Wisconsin Regional Planning Commission EAST CENTRAL WISCONSIN REGIONAL PLANNING COMMISSION Merlin Gentz, Chair Brian Kowalkowski, Vice-Chair Eric Fowle, Secretary-Treasurer COMMISSION MEMBERS CALUMET COUNTY WAUPACA COUNTY Merlin Gentz Dick Koeppen Pat Laughrin Duane Brown Clarence Wolf Robert Danielson Brian Smith MENOMINEE COUNTY WAUSHARA COUNTY Elizabeth Moses Norman Weiss Ruth...»

«East Tennessee State University Digital Commons @ East Tennessee State University Electronic Theses and Dissertations 12-2002 Don't Put Your Shoes on the Bed: A Moral Analysis of To Kill a Mockingbird. MitziAnn Stiltner East Tennessee State University Follow this and additional works at: http://dc.etsu.edu/etd Recommended Citation Stiltner, MitziAnn, Don't Put Your Shoes on the Bed: A Moral Analysis of To Kill a Mockingbird. (2002). Electronic Theses and Dissertations. Paper 722....»

«The Mirage of Terrorist Financing: The Case of Islamic Charities Strategic Insights, Volume V, Issue 3 (March 2006) by Robert Looney Strategic Insights is a monthly electronic journal produced by the Center for Contemporary Conflict at the Naval Postgraduate School in Monterey, California. The views expressed here are those of the author(s) and do not necessarily represent the views of NPS, the Department of Defense, or the U.S. Government. For a PDF version of this article, click here. “We...»

«Quebec Prosperity Initiative Quebec’s Government Indebtedness: Unnoticed, Uncontrolled Edited by Sean Speer MARCH 2014 Quebec Ontario Vermont Alberta California Contents Executive Summary........................ 1 Jason Clemens and Sean Speer 1. The State of Quebec’s Indebtedness................. 5 Filip Palda, Hugh MacIntyre, and Charles Lammam 2. Comparing the Indebtedness of Quebec and Its Neighbours...... 19 Marc Joffe, Sean Speer, and...»

«Approved Pamphlet ALTRISET 30862 2014-02-05 Page 1 of 17 GROUP 28 INSECTICIDE ALTRISET™ Termiticide INSECTICIDE SUSPENSION COMMERCIAL This product is to be used only by licensed pest control operators authorized with permits by government for control of subterranean termite populations infesting buildings. For use only in areas where there is a risk of infestation from subterranean termites. Not for sale to the general public. FOR USE ONLY BY LICENSED PEST CONTROL OPERATORS GUARANTEE:...»

«NJIT STRATEGIC ENROLLMENT MANAGEMENT PLAN: FIRST STAGE YEARS 2015 TO 2020 SEM AT NJIT 2015-2020 2015-2020 “Strategic enrollment Management (SEM) is an institution‐wide responsibility and the central focus of the institution‟s overall strategic plan. SEM focuses on what is best for students and how to ensure their NJIT STRATEGIC success while addressing all aspects of the institution‟s mission. “ ENROLLMENT A Practical Guide to Strategic MANAGEMENT Enrollment Management Planning,...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.