Matchstick games: On removing a matchstick without disturbing the others

Godfried T. Toussaint

doi:10.1007/978-3-030-03577-8_63

Matchstick games: On removing a matchstick without disturbing the others

Godfried T. Toussaint

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.

Original language	English (US)
Title of host publication	Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018
Editors	Alvaro Rocha, Mohammed Serrhini
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	580-587
Number of pages	8
ISBN (Print)	9783030035761
DOIs	https://doi.org/10.1007/978-3-030-03577-8_63
State	Published - 2019
Event	2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018 - Fez, Morocco Duration: Oct 25 2018 → Oct 27 2018

Publication series

Name	Smart Innovation, Systems and Technologies
Volume	111
ISSN (Print)	2190-3018
ISSN (Electronic)	2190-3026

Other

Other	2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018
Country/Territory	Morocco
City	Fez
Period	10/25/18 → 10/27/18

Keywords

Artificial intelligence
Collision avoidance
Computational geometry
Discrete mathematics
Line segments
Robotics
Spatial planning
Translation

ASJC Scopus subject areas

Decision Sciences(all)
Computer Science(all)

Access to Document

10.1007/978-3-030-03577-8_63

Cite this

Toussaint, G. T. (2019). Matchstick games: On removing a matchstick without disturbing the others. In A. Rocha, & M. Serrhini (Eds.), Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018 (pp. 580-587). (Smart Innovation, Systems and Technologies; Vol. 111). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-03577-8_63

Matchstick games: On removing a matchstick without disturbing the others. / Toussaint, Godfried T.
Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018. ed. / Alvaro Rocha; Mohammed Serrhini. Springer Science and Business Media Deutschland GmbH, 2019. p. 580-587 (Smart Innovation, Systems and Technologies; Vol. 111).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Toussaint, GT 2019, Matchstick games: On removing a matchstick without disturbing the others. in A Rocha & M Serrhini (eds), Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018. Smart Innovation, Systems and Technologies, vol. 111, Springer Science and Business Media Deutschland GmbH, pp. 580-587, 2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018, Fez, Morocco, 10/25/18. https://doi.org/10.1007/978-3-030-03577-8_63

@inproceedings{5a4aa1a80acf43efb78d1dcbc096af53,

title = "Matchstick games: On removing a matchstick without disturbing the others",

abstract = "It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.",

keywords = "Artificial intelligence, Collision avoidance, Computational geometry, Discrete mathematics, Line segments, Robotics, Spatial planning, Translation",

author = "Toussaint, {Godfried T.}",

note = "Funding Information: Acknowledgments. This research was supported by a grant from the Provost{\textquoteright}s Office, administered by the Faculty of Science of New York University Abu Dhabi, in Abu Dhabi, The United Arab Emirates. Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018 ; Conference date: 25-10-2018 Through 27-10-2018",

year = "2019",

doi = "10.1007/978-3-030-03577-8_63",

language = "English (US)",

isbn = "9783030035761",

series = "Smart Innovation, Systems and Technologies",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "580--587",

editor = "Alvaro Rocha and Mohammed Serrhini",

booktitle = "Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018",

address = "Germany",

}

TY - GEN

T1 - Matchstick games

T2 - 2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018

AU - Toussaint, Godfried T.

N1 - Funding Information: Acknowledgments. This research was supported by a grant from the Provost’s Office, administered by the Faculty of Science of New York University Abu Dhabi, in Abu Dhabi, The United Arab Emirates. Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

N2 - It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.

AB - It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.

KW - Artificial intelligence

KW - Collision avoidance

KW - Computational geometry

KW - Discrete mathematics

KW - Line segments

KW - Robotics

KW - Spatial planning

KW - Translation

UR - http://www.scopus.com/inward/record.url?scp=85056475862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056475862&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-03577-8_63

DO - 10.1007/978-3-030-03577-8_63

M3 - Conference contribution

AN - SCOPUS:85056475862

SN - 9783030035761

T3 - Smart Innovation, Systems and Technologies

SP - 580

EP - 587

BT - Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018

A2 - Rocha, Alvaro

A2 - Serrhini, Mohammed

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 25 October 2018 through 27 October 2018

ER -

Matchstick games: On removing a matchstick without disturbing the others

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this