transition systems

Stream: IMO-grand-challenge

[Miroslav Olšák]

@Daniel Selsam I noticed that you were looking at dynamic transitional systems (DTS) at IMO. As I was recently looking at IMO combinatorics, I also noticed that many problems involve them. So I would like to share my opinion on them if you are still interested.
I would not look at DTS's in isolation -- DTS is something between deterministic processes (DTS can be seen as a non-deterministic process), and two-player games with complete information (DTS can be seen as one-player game), both of these also occur in IMO problems.
Moreover, solving a two-player game typically means fixing strategy for one player, and then reasoning about the DTS from the perspective of the other player (sure, the strategy is usualy motivated by keeping an invariant which will help with the reasoning).

There is also an IMO problem, 2006-C4, about a DTS in which you can see how I approached it as a human solver (therefore, what type of reasoning can be done about it): http://www.olsak.net/mirek/human-imo-solving/2006-C4

In general, there is the list of relevant non-geometrical problems from combinatorics from shortlists 2006 -- 2018:
deterministic process: 2006-C1, 2010-C6, 2017-C8, 2009-C8, 2011-C5
DTS: 2006-C4, 2007-C4 (almost deterministic), 2008-C4 (counting paths), 2009-C1a, 2010-C4, 2011-C1 (counting paths), 2012-C1, 2013-C3, 2014-C2, 2016-C6, 2017-C2, 2017-C3, 2018-C3, 2018-C6
Games: 2009-C1b, 2009-C5 (possibly infinite), 2012-C4 (possibly infinite), 2012-C6 (with incomplete information), 2013-C8 (possibly infinite), 2014-C8, 2015-C4, 2018-C2