Stéphanie Jean-Daubias
email: stephanie.jean-daubias@univ-lyon1.fr

SAPHIR: A Pluricultural Authoring Tool to Produce Resources in Support of Education for Sustainable Development

Keywords: Authoring Tool, Mobile and Informal Learning, Design Process, Sustainable Development

In this paper, we present SAPHIR, a multilingual authoring tool producing a Progressive Web App, usable on computers, tablets, and smartphones, online or offline. We presented our design process, the architecture of the system, the model on which it is based, and its main parts: SAPHIR it-self is the main software proposing activities to children to learn and play; MINE is the authoring tool used by pedagogical designers and resources translators to create and translate resources without requiring any programming skills; TAILLE is dedicated to teachers to whom he provides educational explanations to use SAPHIR with their learners. The different parts were used with both pedagogical designers and students.

INTRODUCTION

The sixth IPCC report (Intergovernmental Panel on Climate Change) draws alarming conclusions on the impacts of global warming, including dependence on fossil fuels and renewables, limitation of vital resources such as water. In particular, the IPCC urges developed regions to support developing countries, both socially and economically in facing environmental challenges. This collective awareness includes education. Indeed, building a more informed society will help tackling these challenges. However, there is still a long way to go to raise awareness among young people on these questions (IPCC, 2022).

Albatross Foundation [START_REF] Albatross | Albatross Foundation Web Site[END_REF] addresses this issue. This non-profit organization was created in 2011 in Singapore, in 2012 in China, and in 2017 in France where it is recognized of public utility. Its aim is to educate for free young people to sustainable development in a scientific and fun way, thanks to innovative tools. Albatross has developed training programs and book donations on the environment: more than 15 000 children have been trained in China, France and Brazil using the "Train-the-Trainer" method, whether in small weakly connected villages or large hyper connected cities. An experiment on water purification is proposed for children aged 8 to 12 using the foundation's educational kit. Activities a https://orcid.org/0000-0003-2209-6376 of the foundation are organized according to the classical elements (earth, water, air, fire) which were proposed to explain the nature [START_REF] Laszlo | Terre & eau, air & feu (Earth & Water, Air & Fire)[END_REF].

The project presented in this paper takes place within the framework of a collaboration between the LIRIS computer science research lab and the Albatross Foundation. Its aim is to design, develop and test a multilingual and multicontext app for education to sustainable development.

In this paper, we present SAPHIR (education to Sustainable development with Albatross through Pedagogical activities: Humans Involved in the Respect of their environment), an environment consisting of different parts [START_REF] Saphir | SAPHIR app[END_REF]: SAPHIR itself is the main software proposing activities to children to learn and play; MINE is the authoring tool used by pedagogical designers and translators to create and translate resources without requiring any programming skills; TAILLE is dedicated to teachers to whom he provides educational explanations to use SAPHIR with their learners. In the following, we will introduce the issues of our work and the associated state of the art. After a presentation of the roles of the various actors involved, we will show the architecture of our system and the model that we propose. We will then come back to the design process that we have adopted, and expose some of the tests conducted with the app. The article will end with a conclusion and a discussion.

ISSUES, STATE OF THE ART AND CONCEPTION CHOICES

Depending on the context, the association needs a light application working even offline on computers, tablets, and smartphones, for classrooms and informal learning, available in different languages. But it also requires offering the possibility to add news contents, to translate these contents quickly and flexibly, according to the deployments planned by the association.

Issue and Research Questions

The general issue of this project is thus to conceive an evolutive and flexible application suited to different contexts and cultures. We identified three main research questions while treating this issue: how to allow non-computer scientists to create contents for this app (Q1); how to consider the multilingual and multicultural context of the project (Q2); and, how to take into account the different contexts of use of the app (Q3).

State of the Art and Choices

For our first research question (Q1: how to allow noncomputer scientists to create contents), the use of authoring tools seems to be an interesting direction. Therefore, research in TEL (Technology Enhanced Learning) identifies classically three ways to create pedagogical resources (Jean-Daubias et al., 2009): fully automatic resources generators, semiautomatic generators, and manual generators (also called authoring tools).

Fully automatic generators, see for example [START_REF] Burton | Diagnosing bugs in a simple procedural skill[END_REF], are complex programs specific to a dedicated domain. They allow to produce resources in this domain without any intervention of the pedagogical designer. This approach is very efficient as it can produce rapidly many resources without any effort, but do not allow a personalisation of the produced resources. Another disadvantage of this approach is that it is complicated and long to conceive and implement. It does not suit our needs, as we want to define our resources precisely to ensure that they will be adapted to our different contexts.

Semi-automatic generators, see for example (Jean-Daubias and Guin, 2009), are close to automatic generators, except that they let more place to pedagogical designers to suit their needs: users can intervene in the resources creation process by specifying a set of constraints on them in order to obtain results more suited to their needs, still in the scope of the generator.

Manual generators (commonly called authoring tools), see for example [START_REF] David | Hypermedia exercises prototyping and modelising[END_REF] and [START_REF] Van Joolingen | Authoring tools for advanced technology educational software: Toward cost-effective production of adaptive, interactive, and intelligent educational software[END_REF], guide the pedagogical designers step by step in the resources design and gives them a great liberty. Limits of this approach is that it is time consuming for the user, as he must precisely define each exercise and their solutions. In the context of our project, the advantages of this approach make its disadvantages acceptable.

We have therefore chosen an approach based on an authoring tool to enable non-computer scientists' educational designers to create educational resources on sustainable development.

For our second research question (Q2: how to take into account the multicultural context of the project), a resource designed in one language cannot always be translated directly into another: it may require adaptation to the target culture (for example, the operating rules for recycling waste vary according to countries or regions). We decided to establish different versions of the resources: each version is not only a translation of the original resource but can also include adaptations to the cultural context of the concerned country or region.

So, we created a multilingual authoring tool, adding to the classical user roles of such tools (administrator and educational designers) a translator role, for people in charge of adapting to different cultures the various resources produced by educational designers.

For our third research question (Q3: how to take into account the different technical contexts of use of the app), we need to propose a flexible application easy to update and to use in different technical contexts. In particular, the application must be usable offline, in places where learners won't have an easy access to the internet. The app also needs to be able to connect to the internet to allow updates in particular to add new contents. The app also needs to be available on various devices (computers, tablets, and smartphones), depending on the devices available in the different use contexts. A good solution to deal with this triple need is a PWA (progressive web app): a type of application software delivered through the web, working on various operating systems with a standard-compliant browser, including desktop and mobile devices [START_REF] Mozilla | Progressive Web App[END_REF]. We like to present this type of website to the general public as "a website disguised as a mobile app".

Thus, we created a multilingual (Q2) authoring tool (Q1) producing a Progressive Web App (Q3), usable on computers, tablets, and smartphones, online or offline.

We considered that using an LMS (Learning Management System) is too rigid to fully meet our needs, especially to create an app clearly identifiable linked with Albatross Foundation.

ARCHITECTURE AND RESOURCES MODEL

Figure 1 shows the general architecture of SAPHIR.

The system consists of four main parts: SAPHIR itself is the main software proposing to children activities to learn and play; MINE is the authoring tool used by pedagogical designers and resources translators to create and translate resources; TAILLE is dedicated to teachers to whom it provides educational explanations; finally, the database stores the resources associated with the different modules.

In the following, after a presentation of the roles of the various actors involved, we will present this architecture and its different parts.

Actors

SAPHIR environment involves users of various roles.

The developers are computer scientists, they created and still enrich the environment (MINE, TAILLE and SAPHIR itself).

The administrator manages the environment.

The educational designers are experts in sustainable development, teachers or didacticians, they use MINE to create new resources.

The translators are experts in sustainable development in the target language, they also need to have a good knowledge of the context in which SAPHIR will be used in the targeted country. They use MINE to translate resources to make them available in new contexts.

The teachers are usually prescribers of SAPHIR to their pupils and also users of TAILLE in the aim of studying the way to use SAPHIR's resources in their classroom and more generally with their pupils.

The children are SAPHIR final users, they use it to learn concepts linked to sustainable development.

Architecture

SAPHIR is developed as a Progressive Web App (PWA) associated with a mySQL database. It allows SAPHIR and TAILLE to work even offline on computer, tablets, and smartphones after the application had been installed locally. However, MINE, the authoring tool, cannot be available offline as it requires an internet access to supply the database. The access to SAPHIR is open, the access to TAILLE too, but it requires to activate the teacher mode, while the access to the authoring tool requires a connection with a login and a password.

The names of SAPHIR, TAILLE and MINE are based on a gem metaphor in French: saphir is the French translation for sapphire; a mine is the place where we find gems; taille is the French word for cut of gems, which is the operation aiming at transforming rough gems into more usable ones. So, the metaphor is that the educational designers find rough gems in the MINE, teachers adapt them to their use in TAILLE, and pupils finally use the refined gems in SAPHIR.

MINE: An Authoring Tool for SAPHIR

MINE (Means to Integrate New Elements in SAPHIR) is SAPHIR authoring tool, usable without any programming skills. This is the interface where pedagogical designers can create interactively new modules and news activities (lessons, quiz, small games). It is also the place where translators can add new translations of existing modules and their resources. MINE also allows the administrator to add new languages. Thus, MINE allows non-computer scientists to create new contents for SAPHIR.

The MINE of SAPHIR includes a content creation interface allowing the creation of new contents (figure 3 shows the creation of a lesson page with a labelled picture, associated with one question of the quiz previously created in MINE) and their translations (figure 2 shows as an example the translation of a lesson page from English to Chinese and Spanish in MINE).

SAPHIR Resources Model

Creating a new module with MINE consists of completing the different parts of the module model. This model is shown in figure 4 and described below.

A Module consists of a lesson, a quiz, 1 to 3 memo-games, an association-game, a cycle-game, an experiment, a short video, and the associated pedagogical-support (available only if logged-in as teacher in TAILLE). This general model ensures homogeneity between modules of SAPHIR. A Quiz is defined as a set of questions. Each question includes a title, various propositions (between 2 and 10) and a general explanation in case of error of the learner). The propositions (correct or not, which are modelled by the validity) are represented by a title and an optional personalized explanation, which allows to give better feedback to the learner.

A Lesson consists of different pages. Each lesson page comprises a title, the text of the lesson page, possibly a picture, its caption, and optional tags to explain the illustration. A page is linked with the suited questions of the module quiz. Indeed, in order to propose more interactive lessons, each lesson page propose a quiz to allow the learner to test himself after reading the content (cf. figure 3).

The lesson can be illustrated to be more suited to young children and more generally to propose easyto-access and enjoyable resources. Each picture can be captioned and added with numbered tags: the numbers are located on the picture (location defined by the horizontal and vertical coordinates of the tag) and the associated text is displayed to the learner when he clicks on the tag on the picture. This functioning (cf. figure 5) has a triple advantage: it makes the user more active in his learning in a constructivist approach [START_REF] Piaget | Psychology and Epistemology: Towards a Theory of Knowledge[END_REF]; it facilitates the translation of the tags (which are text, out of the picture); and it enhance the numerical accessibility of SAPHIR and his compatibility with accessibility tools, for example the narrator used by blind people [START_REF] Wcag | Web Content Accessibility Guidelines[END_REF]. A Memo Game model is a set of 6 triplets associating a picture to a title and a definition. This model allows the creation of three different memory games: the "classical memory" requires the child to found two identical pictures; the "easy memory" requires associating an image to the corresponding word, in order to work on the lesson's vocabulary; and the "difficult memory" asks to associate the name of the concept to its definition (cf. figure 6). The number of triplets is limited to 6 to ensure a comfortable use and a correct display even on mobile phone, in respect with usability considerations [START_REF] Nielsen | Usability engineering[END_REF] [START_REF] Tricot | Utility, usability and acceptability: an ergonomic approach to the evaluation of external representations for learning[END_REF].

The Association Game (cf. figure 7) asks learners to associate different concepts to two opposite categories. An association game is modelled as a set of 2 categories associated with various propositions. The learner will have to associate each proposition to the right category, linked with the lesson. A category is defined by a title and a picture representing it. Each proposition contains a title, the matching category and a personalized explanation used to explain his mistake to the learner in case of error. MINE also allows the pedagogical designers to add a link to a pedagogical video.

Other resources of SAPHIR (experiment, cf. figure 8 and cycle game, cf. figure 9) are not available in MINE for now. The addition of such resources requires developments by computer scientists.

TAILLE: The Teacher Interface for SAPHIR

TAILLE (TrAiners Interface to Learn in different

Languages how to teach Environmental issues with SAPHIR) is SAPHIR teachers' interface. It consists of SAPHIR enhanced with a pedagogical description of each module (cf. figure 10). The aim is to provide teachers with explanations on how they can use these resources in their teaching or more generally with their pupils.

SAPHIR: A Multilingual App for Education to Sustainable Development

SAPHIR itself is the learners' interface of SAPHIR environment. It currently includes six modules (water filtration, urban water cycle, natural water cycle, the greenhouse effect, the natural greenhouse effect, biodiversity), each module is assigned to one of the four categories: water, air, earth, and energy, based on the traditional Chinese representation of the natural elements used by Albatross Foundation [START_REF] Laszlo | Terre & eau, air & feu (Earth & Water, Air & Fire)[END_REF]. Each module contains up to nine resources (among lesson, quiz, 3 types of memory games, association game, cycle game, experiment, video, as defined in the model presented in section 3.2.2). The resources are currently available in up to five languages (English, French, Chinese, Spanish, and Brazilian-Portuguese) chosen according to the requirements of the Albatross Foundation activities. 43 different resources are available for the moment. We made the choice not to rely on internet connexions, in order to propose a simple system, without technical constraints for the learners that do not require personal data management. As it is a tool for informal learning, the resulting lack of learner profile is not considered as a problem.

We decided to give access to the different modules and resources freely, that is to say without any constraint of order, to allow the learner, or the teacher, to choose the activities he wants to follow. The idea is to facilitates access to knowledge on sustainable development, in an informal and flexible way. Thus, there is no pedagogical scenario to link the different activities, except between lessons and quizzes: each lesson page is proposed with a suited question taken from the corresponding quiz module to help the learner to check if he has understood the lesson. When the learner launches a quiz, as a set of five questions is generated semi-randomly from the available questions, covering the scope of the different lesson pages and taking into account the questions already answered during the lesson.

The resources are linked with the activities of Albatross Foundation. For example, the water filtration module is linked to the real water filtration experiment proposed by the foundation to sensitize hundreds of children in the importance of water and the fragility of its quality; the biodiversity module is linked to the Servan's garden initiative of the foundation, a permaculture pedagogical garden to develop sustainable agriculture, respecting the environment, promoting biodiversity to sensitize and educate young people to "grow and eat well" [START_REF] Albatross | Albatross Foundation Web Site[END_REF].

DESIGN AND EVALUATION PROCESS 4.1 Design Methodology

For the design and the development of SAPHIR environment, we adopt a user-centred method [START_REF] Norman | User Centered System Design: New Perspectives on Human-computer Interaction[END_REF] with an iterative approach. We designed personae for each role of users (admin, educational designer, translator, teacher, learner), in order to identify easily the different target publics.

Figure 11 shows the three main stages of SAPHIR design process. The first stage of the process (left part of figure 11) corresponds to the iterative design and development of the global environment by computer scientists. Our iterative approach (symbolized by the left spiral in the figure) enabled us to propose a preliminary version of the app to communicate with the association members and to conduct early tests with children, but also teachers. Then, the authoring tool was progressively developed, enabling to create more easily new contents. At this stage, SAPHIR contained only three modules on water and was available only in English, French and Chinese; as for MINE, it was an empty shell.

Once the environment and the authoring tool had been sufficiently developed, the second stage (central part of figure 11), consists of filling by experts and teachers, including translators with scientific knowledge, this empty shell with the educational contents expected by the association. This enrichment of SAPHIR by the addition of pedagogical contents is symbolized in the figure by the blue bar which widens progressively. SAPHIR has thus grown from 3 to 6 modules, now gathering 43 resources available in several languages.

The third stage (right part of figure 11) is the use of the various resources of SAPHIR by children from different cultures, in different languages, with or without the support of their teachers.

We consider that contents creation is part of the design of the system: pedagogical designers complete the design by their uses of the authoring tool.

Content Creation and Translation

The creation of the contents, associated with one of the classical elements (earth, water, air, fire), is a collaborative and iterative work involving at different stages scientists, experts, teachers, and translators.

Each person involved in the process can modify the contents according to his skills.

Use of SAPHIR in Different Contexts

MINE has been successfully tested with pedagogical designers: the interface allows non-computer scientists to create and translate new resources. SAPHIR including the resources produced by pedagogical designers with MINE was tested several times with learners in different contexts. In the following, we present 3 of these tests chosen for their diversity. The first test was conducted in France in June 2020, in French language, it involved 6 pupils between 6 and 11 years old, in a Covid-scholar context in a small country school (cf. bottom right picture of figure 12). The app was used collectively on the classroom interactive whiteboard. The teacher and the pupils appreciated the app. The test validated the usefulness of the app and allowed to identify some usability problems [START_REF] Tricot | Utility, usability and acceptability: an ergonomic approach to the evaluation of external representations for learning[END_REF] Apart from these tests, SAPHIR is also used independently of classes. We identified more than 20 000 hits from computers all over the world.

CONCLUSIONS

Discussion

The fact that non-computer scientists can create and translate new contents with the MINE of SAPHIR is a first validation step for our authoring tool. But we need to continue evaluations to carefully validate MINE.

As for the contents created, after being validated by teachers and experts, they were used with several children of various languages and cultures, in different contexts. Both teachers and students found their use of SAPHIR useful and enjoyable.

Conclusion

In this project, we addressed the issue of how to conceive an evolutive and flexible application suited to different contexts and cultures. It conducted us to answer three questions: how to allow non-computer scientists to create contents for this app; how to consider the multicultural context of the project and the different contexts of use of the app.

As an answer to these questions, we created a multilingual authoring tool producing a Progressive Web App, usable on computers, tablets, and smartphones, online or offline.

In this paper, we presented our design process, the architecture of the produced system, the model on which it is based, and the main parts of the system, including MINE, the authoring tool, TAILLE, the teachers' interface, and SAPHIR itself (cf. figure 13), the children app. The different parts were tested successfully.

Several perspectives are open to us now. First of all, we will continue adding new contents and new translations to enlarge the scope of the app to cover more broadly the themes of sustainable development addressed by the Albatross Foundation in order to sensitize more children to sustainable development. Moreover, new languages could be added in case of deployment of the app in new countries. In addition, we are planning uses of the app in a new context: scientific mediation events with the general public.

We are also considering working with children on the next resources with the idea of proposing "an app for children made by children". For this, we have undertaken projects with several classrooms in different contexts. The idea is to make pupils working together in classroom to establish new modules to add to SAPHIR for future young users. Additionally, we are going to propose to future teachers and didacticians to use MINE to make them work on content creation in a didacticians approach.

Figure 1 :

 1 Figure 1: Architecture of SAPHIR environment.

Figure 2 :

 2 Figure 2: Screenshot of MINE during the translation of a lesson from English (right) to Spanish and Chinese (left).

Figure 3 :

 3 Figure 3: Screenshot of the creation of a lesson with MINE.

Figure 4 :

 4 Figure 4: SAPHIR educational resources model.

Figure 5 :

 5 Figure 5: Interactive picture in SAPHIR.

Figure 6 :

 6 Figure 6: Screenshots of MINE during the creation of a memory game and of 3 types of memory games in SAPHIR.

Figure 7 :

 7 Figure 7: Association game in SAPHIR.

Figure 8 :

 8 Figure 8: Water filtration experiment in Chinese.

Figure 9 :

 9 Figure 9: Cycle games in SAPHIR (natural water cycle in Spanish, urban water cycle in Portuguese, and greenhouse effect in French).

Figure 10 :

 10 Figure 10: Screenshot of TAILLE, the teacher interface.

Figure 11 :

 11 Figure 11: Diagram of SAPHIR design process.

  which were subsequently corrected. Alongside other assessments in France, another test was conducted in May 2021 in China, with young pupils, on computers, tablets, and smartphones (cf. 3 top pictures of figure 12) in Chinese. This test validates the usability on different devices and in Chinese language. The most recent test took place near San Paolo in Brazil in November 2022 with 30 pupils, in Portuguese (cf. bottom left pictures of figure 12: students using the water filtration kit). The test showed the interest of using SAPHIR with older pupils and validated the Portuguese version of the app.

Figure 12 :

 12 Figure 12: Use of SAPHIR in classrooms.

Figure 13 :

 13 Figure 13: Screenshot of SAPHIR's main screen.

ACKNOWLEDGEMENTS

SAPHIR app was awarded the Franco-Chinese Teams Innovation Award of MEDEF organisation in 2019, and the Belgian King Baudouin Foundation Award in 2020 and 2022.

The app was developed by students from the computer science master's degree of Lyon 1 University: especially Lucas, Mikael, Vichith, Jonathan, Dorian, and Dorian, thanks to them. The author also thanks Philippe Daubias from ENS de Lyon for administrating the SAPHIR's web server and all the people who participated in the creation or translation of the contents, especially Albatross team and her founder Ghislaine Bouillet-Cordonnier.


Eric Duch Êne

Michel Rigo

A MORPHIC APPROACH TO COMBINATORIAL GAMES : THE TRIBONACCI CASE

Keywords: Two-player combinatorial game, Combinatorics on words, Numeration system, Tribonacci sequence

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

Introduction

Wythoff's game is a well-known two-players take-away game played on two piles each having a finite number of tokens [START_REF] Wythoff | A modification of the game of Nim[END_REF]. A move consists in selecting a pile and removing from it any positive number of tokens (same rule as for the game of Nim), or removing the same positive number of tokens from both piles. The convention is that the first player who is unable to move, loses the game. A winning strategy for this game can be derived from the Fibonacci word. A position (x, y) of the game (i.e., a pair coding the number of tokens in the two piles) is said to be a P -position if the "Previous" (i.e., the second) player can win whatever move his opponent shall make. The P -positions of Wythoff's game are exactly the pairs given by the positions of the n-th occurrence of a and the n-th occurrence of b in the Fibonacci word (see Remark 7 for a proof of this statement). This observation gives an interesting link between combinatorial game theory and combinatorics on words.

In [START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF], A. Fraenkel defines a removal game on three piles, namely the Raleigh game, which in his own terms is neither a generalization of the game of Nim nor of Wythoff's game. In [START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF], he presents a family of 2-pile games whose winning strategies are studied through the use of exotic numeration systems. In general most of the variants of Wythoff's game are solved in polynomial time through the use of numeration systems (see [START_REF] Fraenkel | A generalization of Wythoff's game[END_REF][START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF][START_REF] Fraenkel | The rat game and the mouse game[END_REF]). The originality of our approach to compute the set of P -positions relies on iterated morphisms instead of numeration systems. We present a variation of Wythoff's game in the sense that the P-positions can be derived from the natural generalization of the Fibonacci word to a threeletters alphabet, the so-called Tribonacci word: the P -positions are exactly the triples given by the positions of the n-th occurrence of letter a, b and c in the Tribonacci word.

We propose a game based on three piles that we call the Tribonacci game. As we shall quickly see the rules of this game are symmetric on the three piles. Consequently instead of considering positions represented by arbitrary elements in N 3 we can restrict ourselves to positions (a, b, c) with 0 ≤ a ≤ b ≤ c. The moves are the following:

I. Any positive number of tokens from up to two piles can be removed. II. From position (a, b, c), one can remove a positive number α ≤ a, β ≤ b, γ ≤ c of tokens from the respective piles consisting of a, b, c tokens, subject to the condition: 2 max{α, β, γ} ≤ α + β + γ.

III. Let β > 2α > 0. From position (a, b, c) one can remove the same number α of tokens from any two piles and β tokens from the other one with the following condition. If a (resp. b , c ) denotes the number of tokens in the pile which contained a (resp. b, c) tokens before the move, then the configuration a < c < b is not allowed. As for Wythoff's game or for the game of Nim, the (normal) convention is that the first player who is unable to move, loses the game.

Remark 1. Rules I and II can be considered as "natural" extensions of Wythoff's rules on three piles. The third rule is necessary so as to have a set of P-positions where each positive integer appears at most once.

Observe that in rule III, changing the hypothesis β > 2α to β ≤ 2α gives a special case of rule II.

Example 1. To see how the rules of the Tribonacci game work, let us consider a few examples. Consider the configuration [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30). Applying rule I, one can for instance remove 12 tokens from the first and third piles to obtain (0, 18, 22) after reordering. Unlike Wythoff's game, one can remove different numbers of tokens from two piles. So applying rule I by removing 12 tokens from the first pile and 5 tokens from the third one, we get from [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30) to the configuration (0, 22, 25). Applying rule II, we can go from [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30) to (1, 2, 3) because 11 + 20 + 27 = 58 ≥ 2.27. Finally consider applying rule III, from (a, b, c) = [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30) if one removes α = 1 token from the first and third piles and β = 12 tokens from the second pile, one gets a = 11, b = 10 and c = 29 and the allowable inequalities b < a < c to obtain configuration [START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF][START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF]29). However, removing 1 token from the first two piles and 10 tokens from the third one is not allowed because we get a = 11, b = 21 and c = 20 and in this case, a < c < b . But removing 1 token from the first two piles and 9 tokens from the third one is allowed. One gets a = 11, b = 21 and c = 21 with the allowable configuration a < b = c .

To describe the set of P -positions of our Tribonacci game, we shall consider three formalisms (morphic formalism, recursive definition and game formalism) and show that they are all equivalent. Since the morphic formalism is the simplest one to produce an infinite word and to define a corresponding set of positions, we shall start with this description in Section 2. Using classical construction, the morphic description leads us to the introduction of the Tribonacci number system. In Section 3, we propose a recursive definition of the Tribonacci word. The reader will have to wait until Section 4 to see the link between the morphism and the Tribonacci game defined above. In Section 5, representations in the Tribonacci number system of the P -positions are shown to have a simple syntactic property depending only on their last two (least significant) digits. Moreover this allows us to have a winning strategy that can be computed in polynomial time (which is for instance a central question in [START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF]). and which is also related in some sense to the Tribonacci sequence (for details, see for instance [START_REF] Webb | The length of the four-number game[END_REF]).

The morphic formalism

In this section, we do not yet consider our Tribonacci game rather we simply introduce the Tribonacci sequence over the alphabet {a, b, c} and present some of its properties which are immediate consequences of the construction using iterated morphism.

We define a sequence (A n , B n , C n ) n≥0 of triples of integers directly related to the Tribonacci word. Consider the morphism τ : {a, b, c} → {a, b, c} * defined by τ (a) = ab, τ (b) = ac and τ (c) = a. Iterating this morphism starting with a gives the well-known Tribonacci word t = (t n ) n≥1 = lim n→+∞ τ n (a),

t = abacabaabacababacabaabacabacabaabacababacabaabacabaab • • • .
Observe that we use the convention that the first letter of t has index 1. Let us recall that this word appears also in symbolic dynamics or in fractal geometry (see for instance [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF][START_REF] Rauzy | Nombres algébriques et substitutions[END_REF]). Many combinatorial properties of the Tribonacci word are studied in [START_REF] Tan | Some properties of the Tribonacci sequence[END_REF]. For X = A, B, C (resp. x = a, b, c), define the sets

X = {X 1 < X 2 < X 3 < • • • } = {n ∈ N | t n = x}. Moreover we set A 0 = B 0 = C 0 = 0. The sequence (A n ) n≥1 (resp. (B n ) n≥1 , (C n ) n≥1
) is indexed as A003144 (resp. A003145, A003146) in the Sloane's encyclopedia of integer sequences [START_REF] Sloane | On-Line Encyclopedia of Integer Sequences[END_REF]. These three sequences together first appeared in [START_REF] Carlitz | Fibonacci representations of higher order[END_REF] where Table 1 is defined recursively. Many properties of these sequences were already studied in [START_REF] Carlitz | Fibonacci representations of higher order[END_REF]. The relationship with the Tribonacci sequence was explicitly presented later in [START_REF] Barcucci | On Tribonacci sequences[END_REF].

n
A n ) n≥0 , (B n ) n≥0 and (C n ) n≥0 .
Trivially, the sets A, B and C give a partition of N ≥1 . Remark 3. Since for any letter x ∈ {a, b, c}, τ (x) begins with a, it is obvious that ∆ n (a) := A n+1 -A n is given by ψ a (t n ) where ψ a : a, b → 2, c → 1. Remark 5. In the same way, looking at τ 3 (a) = abacaba, τ 3 (b) = abacab and τ 3 (c) = abac, one can see that c always occurs in the fourth position. Since τ 3 (t) = t, we get that ∆ n (c) := C n+1 -C n is given by ψ c (t n ) where ψ c : a → 7, b → 6, c → 4.

In view of the last three remarks, we have the following result.

Theorem 1. With the above notation, for all n ≥ 1, we have [START_REF] Berlekamp | Winning ways (two volumes)[END_REF][START_REF] Boshernitzan | Nonhomogeneous spectra of numbers[END_REF][START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF], (1, 2, 4)}.

(∆ n (a), ∆ n (b), ∆ n (c)) ∈ {(2, 4, 7),
In particular, ∆ n (a) + ∆ n (b) + 1 = ∆ n (c).
The Tribonacci number system is a positional numeration system given by the linearly recurrent sequence T 0 = 1, T 1 = 2, T 2 = 4 and T k+3 = T k+2 + T k+1 + T k for all k ≥ 0. Using a greedy algorithm [START_REF] Fraenkel | Systems of numeration[END_REF] and a variation of the Zeckendorf's expansion defined for the Fibonacci sequence [START_REF] Zeckendorf | Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas[END_REF], any positive integer n has a unique decomposition

n = i=0 c i T i
with c i ∈ {0, 1} for all i ∈ {0, . . . , -1}, c = 1 and no three consecutive digits being equal to 1. This result is a consequence of the following facts:

• For all n ≥ 1, we have T n /T n-1 ≤ 2. Therefore all the coefficients c i appearing in the decomposition belong to {0, 1}. Indeed, assume that there

exists i ∈ {0, . . . , } such that c i ≥ 2. Then c i T i + • • • + c 0 T 0 ≥ T i+1
which contradicts the greediness of the algorithm. • Again by greediness of the algorithm and by definition of the Tribonacci sequence, no three consecutive digits can be equal to 1. • Uniqueness of the decomposition follows from the fact that any decomposition of n = i=0 c i T i with c i ∈ {0, 1} for all i ∈ {0, . . . , -1}, c = 1 and no three consecutive digits being equal to 1 is a greedy decomposition. We proceed by induction. We have c 0 T 0 < T 1 . Assume that

c i T i + • • • + c 0 T 0 < T i+1 for 0 ≤ i < . Let D = c i+1 T i+1 + • • • + c 0 T 0 . If c i+1 = 0 then D < T i+1 < T i+2 . If c i+1 = 1 then D < 2T i+1 ≤ T i+2 . The word ρ T (n) = c • • • c 0 is said to be the Tribonacci representation of n.
It is convenient to assume that 0 can be equally represented by the word 0 or by the empty word ε. Indeed, in a canonical way we can associate to the morphism τ a deterministic finite automaton A having {a, b, c} as set of states and {0, 1} as alphabet (this kind of construction already appeared in the seminal paper [START_REF] Cobham | Uniform tag sequences[END_REF]). If δ : {a, b, c} × {0, 1} → {a, b, c} is the transition function of A, then

δ(a, 0) = a, δ(a, 1) = b, δ(b, 0) = a, δ(b, 1) = c, δ(c, 0) = a.
Notice that δ is not a total function, i.e., A is not complete. Let M = L(A)\0{0, 1} * where L(A) is the language accepted by the automaton A where all states are final and a is the initial state. Let M n be the n-th word (n ≥ 1) of the genealogically ordered language M . (Suppose x, y are two words on a totally ordered alphabet (Σ, <). Then x is genealogically less than

y if |x| < |y| or, if |x| = |y| and x = uav, y = ubw where u, v, w ∈ Σ * , a, b ∈ Σ and a < b). Since L(A) = {0, 1} * \ {0, 1} * 111{0, 1} * , the numerical value val(M n ) of M n with respect to the Tribonacci system is val(M n ) = n -1.
See for instance Table 3.

n 1 2 3 4 5 • • • M n ε 1 10 11 100 • • • val(M n ) 0 1 2 3 4 • • • Table 3.
First words in M and their numerical value.

Moreover, using again [START_REF] Rigo | More on generalized automatic sequences[END_REF], feeding A with M n leads to the state t n .

Recursive definition

Observe that the n-th occurrence of c in t belongs to the image under τ of the n-th occurrence of b in t which appears itself in the image under τ of the nth occurrence of a. Hence it is clear that for all n ≥ 1, B n -A n and C n -B n are positive, i.e., A n < B n < C n . The aim of this section is to obtain a recursive characterization of t (see Theorem 2). Notice that this characterization differs from the one given initially in [START_REF] Carlitz | Fibonacci representations of higher order[END_REF] (especially for the formula giving B n ). As usual, the notation Mex stands for Minimum EXcluded value [START_REF] Berlekamp | Winning ways (two volumes)[END_REF].

Theorem 2. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). For all n ≥ 1, t satisfies

   A n = Mex{A i , B i , C i : 0 ≤ i < n} B n = A n + Mex{B i -A i , C i -B i : 0 ≤ i < n} C n = A n + B n + n.
Moreover, t is the only word over a ternary alphabet {a, b, c} satisfying these relations.

The following result is also discussed in [START_REF] Barcucci | On Tribonacci sequences[END_REF] where a "simple" construction of t is given. For the sake of completeness and since all the necessary material is already introduced, we recall the proof. Lemma 1. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). For all n ≥ 1, we have

C n = A n + B n + n.
Proof. For X = A, B, C (resp. x = a, b, c), we use notation of Remarks 3, 4 and 5, it is clear that for all n ≥ 1,

X n = X 1 + n-1 i=1 ∆ i (x).
Therefore, using Theorem 1, we get

C n = 4 + n-1 i=1 (∆ i (a) + ∆ i (b) + 1) = A 1 + n-1 i=1 ∆ i (a) + B 1 + n-1 i=1 ∆ i (b) + n
and the result follows.

a n = Mex{a i , b i : 0 ≤ i < n} and b n = a n + n.
Indeed, the n-th occurrence of a produces using ϕ the n-th occurrence of b in f . Since all b's are produced by letters a, during the iteration process, all the remaining gaps are filled with a and

a n = Mex{a i , b i : 0 ≤ i < n}. For the second part, since ab is a prefix of f then b 1 = a 1 + 1. Assume that b n-1 = a n-1 + n -1 for some n ≥ 2. Notice that if a n -a n-1 = 1 (resp. 2) then b n -b n-1 = 2 (resp. 3). Therefore, b n = a n + n.
The sequence (a n , b n ) n≥1 was studied in [START_REF] Wythoff | A modification of the game of Nim[END_REF][START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF] from a game theoretical point of view. In [START_REF] Wythoff | A modification of the game of Nim[END_REF] it is shown that the P -positions of Wythoff's game are exactly the (x n , y n ) satisfying the same relation as [START_REF] Barcucci | On Tribonacci sequences[END_REF]. Consequently, the P -positions of Wythoff's game are exactly the pairs given by the positions of the n-th occurrence of a and the n-th occurrence of b in the Fibonacci word. If x = (x n ) n≥0 is an infinite word over a finite alphabet of integers, then we denote by S(x) the corresponding summatory sequence, i.e., for all n ≥ 0, For any infinite word w ∈ {a, b, c} ω , the sets

S(x) n = n i=0 x i . Let Y ⊆ N be a set of integers. The characteristic sequence of Y is an infinite word χ Y = (x n ) n≥0 over {0, 1} defined by x i = 1 if and only if i ∈ Y .
S µ = {S(2 µ(w)) n | n ≥ 0} and S ν = {S(1 ν(w)) n | n ≥ 0} form a partition of N ≥1 .
Proof. Let χ µ (resp. χ ν ) be the characteristic sequence of S µ (resp. S ν ). Each letter of w gives a subword of χ µ (resp. χ ν ), assuming that a 1 appears earlier (which is always the case since χ µ (resp. χ ν ) starts with 001 (resp. 01). We give the possible subwords written in bold case It is clear that in χ µ , each 1 is preceded with 0 (the values taken by µ are at least 2 which means that S µ does not contain two consecutive integers) and in χ ν , each 1 is followed by 0 (the images of ν all start with 2). Since we consider the summatory sequences obtained from the sequences 2µ(w) and 1ν(w) starting respectively with 2 and 1, the subwords obtained in χ µ and χ ν corresponding to the same letter in w are thus shifted by one. Namely, we have Remark 8. The above result can be trivially extended to two morphisms defined on an arbitrary finite alphabet Γ and taking values in an alphabet Σ ⊂ N ≥1 of integers. Suppose that for all a ∈ Γ, µ(a) does not start nor end with 1 and is of the form

µ(a) = w 1 1 a 2 w 2 1 a 3 w 3 • • • 1 a k w k where a i ∈ Σ \ {1}, w i ∈ Σ * .
It is obvious that if for all n ≥ 2, we set ζ(n) := 2 (1) n-2 , then the morphism ν defined by

ν(a) = ζ(w 1 ) 3 (1) a2-2 ζ(w 2 ) 3 (1) a3-2 ζ(w 3 ) • • • 3 (1) a k -2 ζ(w k )
can be used to define a partition of N ≥1 .

Corollary 3. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). The sets

{B i -A i | i ≥ 1} = {1,
(C n+1 -B n+1 ) -(C n -B n )) n≥1 = (∆ n (c) -∆ n (b)) n≥1 is given by µ(t)
where µ is the same as in the previous lemma (indeed, for all x ∈ {a, b, c}, µ(x) = ψ c (x) -ψ b (x)). Moreover, C 1 -B 1 = 2. Therefore, the set {C i -B i | i ≥ 1} is given by the summatory sequence S(2 µ(t)).

In the same way, the sequence ((

B n+1 -A n+1 ) -(B n -A n )) n≥1 = (∆ n (b) - ∆ n (a)) n≥1 is given by γ(t) where γ(a) = 2, γ(b) = γ(c) = 1. Notice that γ • τ = ν
where ν is the same as in the previous lemma. Since B 1 -A 1 = 1, the set {B i -A i | i ≥ 1} is given by S(1 γ(t)). To conclude, recall that t = τ (t). Therefore,

S(1 γ(t)) = S(1 γ(τ (t))) = S(1 ν(t))
and the result follows using the previous lemma.

With the following lemma, we get the proof of Theorem 2.

Lemma 3. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). For all n ≥ 1, we have

A n = Mex{A i , B i , C i : 0 ≤ i < n} B n = A n + Mex{B i -A i , C i -B i : 0 ≤ i < n}.
Proof. We proceed by induction on n. Assume that the result holds for all values less than n ≥ 2. Let t

:= B n-1 -A n-1 = Mex{B i -A i , C i -B i : 0 ≤ i < n-1}.
Then as shown in the proof of the previous corollary, B n -A n = t + 1 or t + 2 (the images of γ are 1 or 2). In the first case, again using Corollary 3, if B n -

A n = t + 1 then C n-1 -B n-1 = t+1 and we conclude that B n -A n = t+1 = Mex{B i -A i , C i -B i : 0 ≤ i < n}.
In the second case, assume that B n -A n = t + 2. Therefore, we just have to show that there exists m < n such that C m -B m = t + 1. The existence of such a m > 0 is again guaranteed by Corollary 3 and m < n because for all x = a, b, c, µ(x) -γ(x) ≥ 1. Indeed, we have

C i -A i ≥ i for all i ≥ 1 and thus since B n-1 -A n-1 = t, C n-1 -B n-1 ≥ t + n -1 ≥ t + 1 for n ≥ 2. Moreover i → C i -B i is increasing hence m < n.
Up to now, and in view of Lemma 1, we have shown that positions of the n-th occurrences of b and c in t are well-defined and appear after the n-th occurrence of a. To conclude the proof, observe that filling the gaps with a's corresponds exactly to the Mex definition. Let X = A, B, C. In what follows, to avoid many intricated subscripts, we equally consider sequences (X n ) n≥0 as functions X : N → N : n → A n . We can therefore use composition of functions. The following two lemmas give properties of t that we use in the next section. Lemma 4. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). We have for all n ≥ 1,

C(n) -B(n) = 1 + B(A(n)) -A(A(n))
and for all n ≥ 0,

C(n) -B(n) + 1 = B(A(n) + 1) -A(A(n) + 1). Proof. If y = y 1 • • • y k is a
finite word over a finite alphabet of integers, similar to the infinite case we use the notation S to denote S(y

) = y 1 + • • • + y k . Let t[1, n] := t 1 • • • t n be the prefix of length n of t. Notice that (2) |τ (t[1, n])| = A(n + 1) -1 , i.e., τ (t[1, n]) = t[1, A(n + 1) -1].
Indeed, for all i = 1, . . . , n, τ (t i ) contains exactly one a. Therefore, to determine the length of τ (t[1, n]), one only needs to look for the (n + 1)-st a in t.

It is clear that for all

n ≥ 1, C(n) -B(n) is given by S(2 µ(t[1, n -1])) and B(n) -A(n) = S(1 γ(t[1, n -1])). We obtain, for all n ≥ 1 C(n) -B(n) = S(2 µ(t[1, n -1])) = S(2 ν(t[1, n -1])) = S(2 γ(τ (t[1, n -1]))) = S(2 γ(t[1, A(n) -1])) = 1 + S(1 γ(t[1, A(n) -1])) = 1 + B(A(n)) -A(A(n)).
To get the second formula, notice that

B(A(n) + 1) -A(A(n) + 1) -[B(A(n)) -A(A(n))] = γ(t A(n) ) = γ(a) = 2.
Lemma 5. Assume X n denotes the position of the n-th occurrence of x in the Tribonacci word t, X = A, B, C (resp. x = a, b, c). For all n ≥ 0, we have

B(n) = A(A(n) + 1) -1. Proof. From (2), we get τ (t[1, A(n)]) = t[1, A(A(n) + 1) -1] and since t A(n) is the n-th occurrence of a in t, then the last letter of τ (t[1, A(n)]) is the n-th occurrence of b in t.

Game formalism

We have collected in the previous section all the necessary results that we need to prove our main result about the Tribonacci game. Proof. We proceed in two steps (in graph theoretical terms, we show that the set of P -positions is the kernel of the acyclic 1 game graph G whose set of vertices is the set of positions and where a directed edge from u to v exists iff there is a legal move between the positions corresponding to u and v).

• 1 Since tokens are taken from the piles at each move, it is obvious that the game graph of the Tribonacci game is acyclic. This ensures existence and uniqueness of the kernel.

We have five cases to consider depending on which permutation of (A m , B m , C m ) corresponds to the reordering of [x, y, z] (remember that one permutation is forbidden with rule III). With the same reasoning as before, there exist α , β , γ > 0 such that 3) and ( 4) still hold and invoking again Theorem 1, we can conclude that [START_REF] Cobham | Uniform tag sequences[END_REF] α < β < γ .

(A n , B n , C n ) α ,β ,γ -→ [A m , B m , C m ] = (A m , B m , C m ). Clearly (
(c) If [x, y, z] = [B m , A m , C m ], then γ = γ, α > α and β < β. If α = β, then A n -B m = B n -A m and we get B n -A n = A m -B m . This is a contradiction because B j -A j > 0 for j > 0 and thus B n -A n > 0 but A m -B m ≤ 0. If α = γ, then A n -B m = C n -C m and we get A n -A m > A n -B m = C n -C m .
This is a contradiction by Theorem 1.

For the last case, assume that β = γ. Since γ = γ, using (4) we get

α + β = α + β and α -α = β -β = γ -β = γ -β . Consequently, α ≥ γ -β which contradicts (3)
. We have therefore shown that α, β, γ are three distinct integers which contradicts rule III. • For second part of the proof, we show that S is an absorbing subset of the game graph G, i.e., any vertex not in S has a successor in S. Let (a, b, c) be a position not in S. There are a few cases that we can directly deal with:

(d) If [x, y, z] = [B m , C m , A m ], then α < α , β < β and γ > γ . If α = γ (resp. β = γ), then γ < α (resp. γ < β ) which contradicts (5)
• If a = 0, then (a, b, c) I -→ (0, 0, 0) = (A 0 , B 0 , C 0 ). • If b = c, then (a, b, c) II -→ (0, 0, 0). • If a = b and c ≤ 2a, then (a, b, c) II -→ (0, 0, 0). • If a = b and c > 2a, then (a, b, c) III -→ (0, 0, 0). • If c ≤ a + b then (a, b, c) II -→ (0, 0, 0).
So in what follows, we may assume that [START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF] 0 < a < b < c and c > a + b.

There exists a unique n > 0 such that a is a component of the triple (A n , B n , C n ). We therefore discuss three cases, according to a.

(a) If a = C n , then A n < B n < C n = a < b < c. Therefore, setting β := b -A n > 0 and γ := c -B n > 0, we get (a, b, c) 0,β,γ -→ [C n , A n , B n ].
That is, we can apply rule I to reach the position (A n , B n , C n ). (b) If a = B n , then we consider two sub-cases.

(b.1) Assume c ≥ C n . In this case, since A n < B n = a < b, we set

β := b -A n > 0 and γ := c -C n . We get (a, b, c) 0,β,γ -→ [B n , A n , C n ]
and we can therefore apply rule I to reach the position (A n , B n , C n ) ∈ S.

(b.2) Otherwise c < C n . Since we may assume that a + b < c, we have 2B n < c (because B n = a < b). Consequently, 2B n < C n . On the other hand, B n -A n ≥ n (as show in the proof of Corollary 3, the difference between two consecutive elements in the set {B j -A j | j ≥ 0} is at least one). Thus, using Lemma 1,

B n ≥ A n + n = C n -B n
I -→ (A n , B n , C n ). (c.2) If b < B n and c ≥ C n . Set t := b -a > 0. In particular, t < B n -A n . Therefore there exists 0 < m < n such that t = B m -A m or t = C m -B m . Indeed, we know from Theorem 2 that B j -A j = Mex{B i -A i , C i -B i | 0 ≤ i < j}. Moreover, m > 0 because t > 0. (c.2.1) Assume t = B m -A m . Set α := a-A m > 0 and γ := c-C m > 0. We notice that b -B m = a -A m and we obtain (a, b, c) α,α,γ -→ [A m , B m , C m ].
If α ≥ γ (resp. α < γ) we conclude by applying rule II (resp. III).

(c.

II -→ (A m , B m , C m ). First observe that m ≤ n -1 because c -a -b ≤ C n -1 -A n -B n = n -1
where the last equality comes from Theorem 2. Next, notice that c > C m . Indeed, we have

c -C m = m + a + b -(A m + B m + m) = A n -A m + b -B m
and since n > m, then A n > A m and b ≥ B n > B m . So up to now, we know that α := a -A m > 0, β := b -B m > 0 and γ := c -C m > 0 but we still have to check that the conditions for applying II hold. First notice that max(α, β, γ) = γ. Indeed, it is clear that A n -A m ≤ B n -B m (the reader can refer to the proof of Corollary 3 for arguments) and since b ≥ B n , we conclude that α ≤ β. Moreover, it follows from the definitions that

γ -β = c -(A m + B m + m) -(b -B m ) = c -b -A m -(c -a -b) = a -A m = A n -A m > 0.
To conclude this part, we just have to show that 2γ ≤ α + β + γ. Here, inequality sign can in fact be replaced with an equality, because

α + β -γ = a + b -c -(A m + B m -C m ) = m -m = 0.
γ -α = c -(A m + B m + m) -a -A m = c -a -B m -(c -a -b) = b -B m > 0.
The conclusion of this case follows the same lines as (c.

≤ M such that b -a = B K -A K or C K -B K . Moreover b -a > 0 implies that K > 0. Assume first that b -a = B K -A K . Since K ≤ M < n, for X = A, B, C (resp. x = a, b, c), we have X K ≤ X M ≤ x and therefore α := a -A K = b -B K > 0 and γ := c -C K ≥ 0, i.e., (a, b, c) α ,α ,γ -→ [A K , B K , C K ].
Thus, if γ = 0 we apply rule I, otherwise if α ≥ γ > 0 we apply rule II and if α < γ we apply rule III to obtain a position in S.

Assume now that b -a = C K -B K . To conclude this part, we show that there exists α , γ > 0 such that (a, b, c)

α ,α ,γ -→ [B K , C K , A K ].
Notice that c ≥ C K > A K so γ := c -A K > 0. We develop now the same arguments as in case (c.2.2). By Lemma 4, we know that

b -a + 1 = C K -B K + 1 = B(A K + 1) -A(A K + 1). Moreover b-a < B n -A n and we conclude that A K +1 ≤ n so A(A K +1) ≤ A n . By Lemma 5, we have B K < A(A K + 1) ≤ a. Therefore α := a -B k = b -C k > 0.
Hence the conclusion follows using rule II or III depending as usual on the values α and γ .

(c.4.2.2) Suppose that B M +1 ≤ b and C M +1 > c. Since A M +1 ≤ a, we have m -(M + 1) = c -a -b -(C M +1 -A M +1 -B M +1 ) < 0
and thus m ≤ M but this contradicts the fact that at least one of the elements α, β or γ is negative. Consequently this case never occurs.

Polynomial winning strategy

We conclude this paper by discussing algorithmic complexity issues about the computation of the winning and losing positions of the Tribonacci game. Table 1 is the key argument to decide whether a given position is a P -position or not. For a given position (a, b, c), one has to check whether it appears or not in the table. If one uses Theorem 2 to build Table 1 up to position (a, * , * ) then this process has an exponential complexity with respect to the size of the input a. Indeed, if an integer a is represented in a given base t, whatever the base is or even in an exotic numeration system like the Tribonacci system, the length of the representation is log t a + 1. So building the table up to a has a linear complexity with respect to a, but an exponential complexity compared to log t a .

Another way to decide whether or not a given triple (a, b, c) is a P -position would be to have an algebraic characterization of the sequences (A n ) n≥0 , (B n ) n≥0 and (C n ) n≥0 , as it is the case for Wythoff's game. For this latter game, P -positions (a n , b n ) are exactly ( nΦ , nΦ 2 ) where Φ is the golden ratio (see [START_REF] Wythoff | A modification of the game of Nim[END_REF]). For the Tribonacci game, such a result does not exist as shown by the following theorem.

Theorem 5. There exist no real numbers α, α , β, β , γ, γ such that A n = nα+α , B n = nβ + β or C n = nγ + γ for all n ∈ N.

Proof. Let (X n ) n≥1 be a nondecreasing sequence of integers. In [START_REF] Boshernitzan | Nonhomogeneous spectra of numbers[END_REF], a necessary condition for the existence of real numbers δ, δ such that X n = nδ + δ for all n ≥ 1, is that for all r ≥ 2, Despite this negative result, the morphic formalism, and especially Remark 6, gives here a polynomial time algorithm to decide whether or not a given position is a P -position. This latter result is a direct consequence of the following statement combined with the proof of Theorem 4. Theorem 6. A configuration (a, b, c) is a P -position of the Tribonacci game if and only if there exists a word w ∈ {0, 1} * such that w does not contain three consecutive 1's and ρ T (a -1) = w0, ρ T (b -1) = w01 and ρ T (c -1) = w011, where ρ T (n) is the Tribonacci representation of n.

d(r) = max 1≤i<k≤r X k -X k-i -1 i < d(r) = min 1≤i<k≤r X k -X k-i + 1 i . • By Theorem 1, we have C k -C k-1 ∈ {4, 6
Proof. We have already noticed in Remark 6 that t n = a (resp. t n = b, t n = c) if and only if ρ T (n -1) ends with 0 (resp. 01, 11).

We also know that the n-th occurrence of c in t belongs to the image under τ of the n-th occurrence of b in t which appears itself in the image under τ of the n-th occurrence of a. Recall the notation of Remark 6. Let M i be the i-th word in M . Assume M i leads to state a in A (in particular M i is of the form w0 for i > 1 or M 1 = ε). This means that t i = a and ρ T (i -1) = M i . Suppose t i is the n-th occurrence of a in t. Since the n-th occurrence of b in t appears as the second letter in τ (t i ), by the properties of A (see [START_REF] Rigo | More on generalized automatic sequences[END_REF]), M i 1 = w01 produces this letter. With the same argument, M i 11 = w011 produces the n-th occurrence of c in t.

Example 2. The following table illustrates the previous result. Deciding whether a given position (a, b, c) is a P -position or not can be done in polynomial time as follows. One first computes ρ T (a -1), ρ T (b -1), ρ T (c -1). This can be done in O(log 2 (c)) because the length of ρ T (c -1) is proportional to log 2 (c -1) and we apply a greedy algorithm to compute the coefficients of the Tribonacci representation. Then, it suffices to check (in linear time) the simple syntactic condition given by the previous theorem.

A n B n C n ρ T (A n -1) ρ T (B n -1) ρ T (C n -
All this study around the Tribonacci game leads naturally to consider the following question. Question 7. Could the Tribonacci game be generalized to a k-bonacci game with rules constructed in such a way that the losing positions are given by the positions of the n-th occurrence of the letters a 1 , . . . , a k in the k-bonacci word given by the morphism ξ(a i ) = a 1 a i+1 for i < k and ξ(a k ) = a 1 ?

According to our investigations, the answer might be positive but even for k = 4 formulating the rules of such a game is tedious task.

Remark 2 .

 2 Let us mention that our game has no link with the Ducci's four-number game problem which occurs when iterating the operator D acting on 4-tuples, D(w, x, y, z) := (|w -x|, |x -y|, |y -z|, |z -w|),

Remark 4 .

 4 Looking at τ 2 (a) = abac, τ 2 (b) = aba and τ 2 (c) = ab, one can see that b always occurs in second position. Since τ 2 (t) = t, we get that ∆ n (b) := B n+1 -B n is given by ψ b (t n ) where ψ b : a → 4, b → 3, c → 2.

Table 2 .Remark 6 .

 26 The Tribonacci representations of the first 20 positive integers. Using a result linking morphic sequences and (abstract) numeration systems[15, Theorem 24], it is not difficult to see that t n = a (resp. t n = b, t n = c) if and only if the Tribonacci representation of n -1 ends with 0 (resp. 01, 11).

Remark 7 (

 7 A characterization of the Fibonacci word). Consider the morphism ϕ : a → ab, b → a generating the celebrated Fibonacci word f = lim n→∞ ϕ n (a) = abaababaabaababaabab • • • e.g., see [13]. Let us denote by a n (resp. b n ) the position of the n-th occurrence of a (resp. b) in f , i.e., (a n ) n≥1 = 1, 3, 4, 6, 8, 9, . . . and (b n ) n≥1 = 2, 5, 7, 10, 13, 15, . . . .It is not difficult to see that, for all n ≥ 1, the Fibonacci word is the only word over a binary alphabet satisfying[START_REF] Barcucci | On Tribonacci sequences[END_REF]

Lemma 2 .

 2 Let µ : {a, b, c} → {2, 3} * and ν : {a, b, c} → {1, 2} * be two morphisms defined by µ(a) = µ(b) = 3, µ(c) = 2, ν(a) = ν(b) = 21 and ν(c) = 2.

  01001 0101 χ ν 10110 10110 1010 Gluing together such possible factors gives the result.

  [START_REF] Boshernitzan | Nonhomogeneous spectra of numbers[END_REF][START_REF] Carlitz | Fibonacci representations of higher order[END_REF][START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF][START_REF] Fraenkel | A generalization of Wythoff's game[END_REF][START_REF] Fraenkel | How to beat your Wythoff games' opponent on three fronts[END_REF][START_REF] Fraenkel | Heap Games, Numeration Systems and Sequences[END_REF][START_REF] Fraenkel | The rat game and the mouse game[END_REF][START_REF] Rauzy | Nombres algébriques et substitutions[END_REF][START_REF] Rigo | More on generalized automatic sequences[END_REF][START_REF] Tan | Some properties of the Tribonacci sequence[END_REF][START_REF] Webb | The length of the four-number game[END_REF][START_REF] Zeckendorf | Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas[END_REF] 21, 23, 24, . . .} and {C i -B i | i ≥ 1} = {2, 5, 8, 11, 13, 16, 19, 22, 25, 28, 31, 33, 36, 39, 42, . . .} give a partition of N ≥1 . In particular, the mappings n → B n -A n and n → C n -B n are increasing. Proof. In view of Theorem 1, the sequence (

Theorem 4 .

 4 The set S = {(A n , B n , C n ) | n ≥ 0}is the set of P -positions of the Tribonacci game.

  Whatever the chosen rule (I, II or III) is, a player moving from a position (A n , B n , C n ) in S always lands in a position not in S. • Given a position (a, b, c) not in S, there exists a move to some position (A n , B n , C n ) ∈ S. Let us first introduce some notation to simplify our presentation. Remember that due to the symmetry of the rules, we have only to consider positions (a, b, c) ∈ N 3 such that a ≤ b ≤ c. So the notation (a, b, c) contains the extra information a ≤ b ≤ c. If one removes non-negative integers α, β and γ respectively from the three piles a, b and c, we get a = a -α, b = b -β and c = c -γ and we use brackets [a , b , c ] instead of parentheses to specify that the resulting triple is not necessarily ordered. We shall therefore write (a, b, c) α,β,γ -→ [a , b , c ]. Notice that if a < b = c or a = b < c or a = b = c , we consider naturally that the triple remains ordered. In particular, we write [a , b , c ] = (a , b , c ) if the order of the piles is unchanged after the move. Finally, we write (a, b, c) R -→ (x, y, z)

  (a) If [x, y, z] = (A m , B m , C m ), then with the same reasoning α < β < γ. But since we have applied rule III (we have to remove the same number of tokens from two piles), we should have α = β, α = γ or β = γ leading to a contradiction. (b) If [x, y, z] = [C m , B m , A m ], then β = β, α < α and γ < γ. Consequently, α < α < β < γ < γ and α < β < γ contradicts rule III.

  . Let us now assume that α = β, then A n -B m = B n -C m and we conclude as in (c) using Corollary 3. Once again, we have shown that α, β, γ are three distinct integers which contradicts rule III. (e) If [x, y, z] = [C m , A m , B m ], then α < α , β > β and γ > γ . This case can be treated as the previous one. We apply Corollary 3 to show that β = γ.

  and we get a contradiction, 2B n ≥ C n . So case (b.2) never occurs. (c) Assume a = A n . In this case, we consider three sub-cases. (c.1) If b ≥ B n and c ≥ C n , then (a, b, c)

2 . 2 )

 22 Assume t = C m -B m . Then C m+1 -B m+1 = t + 2 or t + 3. As a consequence of Corollary 3, there exists K such that B K -A K = t + 1. Notice that B n -A n ≥ t + 1 (because t = b -a = b -A n and B n > b). So K ≤ n. By Lemma 4, we know that t + 1 = C m -B m + 1 = B(A m + 1) -A(A m + 1)and we conclude thatK = A m + 1. By Lemma 5, B m < A K . Since K ≤ n, A K ≤ A n = a and we conclude that B m < a. Since b -a = t = C m -B m , we have that C m < b. Finally, A m < C m < C n ≤ c. We set α := a -B m , β := b -C m , γ := c -A m and (a, b, c) α,β,γ -→ [B m , C m , A m ].Depending on the values α, β, γ > 0, the conclusion follows using rule II or III.(c.3) Assume b ≥ B n and c < C n . Set m := c -a -b, and notice by (6) that m > 0. We show that (a, b, c)

(c. 4 )

 4 Assume b < B n and c < C n . Once again, set m := c -a -b. (c.4.1) Assume as a first sub-case that α := a-A m ≥ 0, β := b-B m ≥ 0 and γ := c-C m ≥ 0. If α β γ = 0 then one can immediately apply rule I. So let us assume now that α β γ > 0. Then A n = a > A m and so n > m. Just as for (c.3), we would like to apply rule II. With the same justifications as in (c.3), one shows that β < γ. To obtain that max(α, β, γ) = γ, notice that

  3), γ = α + β. (c.4.2) Assume that we are now in the situation where at least one of the elements α, β, γ defined in (c.4.1) is negative. SetM := max{k ∈ N | A k ≤ a, B k ≤ b, C k ≤ c}.Since a = A n , we conclude that M ≤ n. Moreover, M = n since b < B n and c < C n . So M + 1 ≤ n and A M +1 ≤ A n but by definition of M we must therefore have B M +1 > b or C M +1 > c. We consider these two cases separately. (c.4.2.1) Suppose that B M +1 > b. Then B M +1 -A M +1 > b -a (indeed remember that A M +1 ≤ A n = a). By Theorem 2, there exists K

  , 7}. Hence applying the previous result to the sequence (C n ) n≥1 and choosing in the above formula i = 1 and C k -C k-1 = 7 (resp. 4), we obtain d(r) ≥ 6 (resp. d(r) ≤ 5). Consequently, we get d(r) < d(r) and the conclusion follows for (C n ) n≥0 .• Similarly, we have B k -B k-1 ∈ {2, 3, 4} and d(r) ≤ 3 ≤ d(r).• By considering the factor cabac (resp. abaaba) of t and in view of Remark 3, there exists k (resp. ) such that A k -A k-5 = 8 (resp. A -A -6 = 12). Therefore d(r) ≤ 9/5 < 11/6 ≤ d(r) and the conclusion follows for (A n ) n≥0 .

Table 1 .

 1 First values of the sequences (

	0 1 2 3 4 5	6 7 8 9 10 11 12 13 14 15
	A n 0 1 3 5 7 8 10 12 14 16 18 20 21 23 25 27
	B n 0 2 6 9 13 15 19 22 26 30 33 37 39 43 46 50
	C n 0 4 11 17 24 28 35 41 48 55 61 68 72 79 85 92

Table 4 .

 4 First P -positions and the corresponding Tribonacci representations.

	1)

Acknowledgments

We are indebted to the anonymous referees for their valuable advises and remarks to improve this paper.

to specify that the position (x, y, z) has been obtained from (a, b, c) using rule R (I, II or III). As an example, we write [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30) [START_REF] Fraenkel | The Raleigh game, to appear in INTEGERS[END_REF]0,[START_REF] Fraenkel | The rat game and the mouse game[END_REF] -→ [START_REF] Barcucci | On Tribonacci sequences[END_REF]22,[START_REF] Webb | The length of the four-number game[END_REF] = [START_REF] Barcucci | On Tribonacci sequences[END_REF][START_REF] Webb | The length of the four-number game[END_REF]22) and [START_REF] Fraenkel | The rat game and the mouse game[END_REF]22,30) I -→ [START_REF] Barcucci | On Tribonacci sequences[END_REF][START_REF] Webb | The length of the four-number game[END_REF]22).

• For the first part of the proof, we show that S is a stable subset of the game graph G, i.e., S is a set of pairwise non-adjacent vertices. Assume that a player moves from a position (A n , B n , C n ) in S to another position (A m , B m , C m ) in S. Clearly m < n. We show that such a move never occurs by considering the possible application of the different rules. First observe that we cannot apply rule I to obtain

, none of the elements in the first triple is equal to any element of the second triple. But with rule I at least one of the piles should remain unchanged which is a contradiction. Now consider applying rule II:

As a first case, suppose that the resulting position has been obtained from

is a linear combination (with non-negative coefficients) of the vectors (1, 2, 4), [START_REF] Berlekamp | Winning ways (two volumes)[END_REF][START_REF] Boshernitzan | Nonhomogeneous spectra of numbers[END_REF][START_REF] Fogg | Substitutions in dynamics, arithmetics and combinatorics[END_REF] and (2, 4, 7) and therefore γ > α+β. This contradicts the fact that rule II has been applied. As a second case, assume that the position (A m , B m , C m ) has been obtained from

Otherwise stated [x, y, z] is a non-trivial permutation of (A m , B m , C m ). Since for X = A, B, C, X n > X m , there exist some α , β , γ > 0 such that

In view of the first case, we still have [START_REF] Boshernitzan | Nonhomogeneous spectra of numbers[END_REF] γ > α + β .

Moreover our key argument is to observe that