Constructible house floor plans on a grid with overlong walls (binmus) and external cells
Donald wants to build a new house. He must add interior partitions. The house is a rectangle of size , where and are integers , which is decomposed into unit cells of side . To avoid forming corridors, a cell may not have two of its sides in the interior of the house: such a cell is called an \emph{internal cell}, while cells on the edge are called \emph{external cells}. Donald, unfortunately, made an error in his order: enthusiastic, he ordered the walls too long. Such an overlong wall is called a \emph{binmu}. Two binmus can intersect in a single point (forming a cross) but cannot be superposed. Donald looks for which plans are possible for his new house with these constraints. Figure 1 represents a valid plan for a house of size . Figure 2 represents three plans of houses that are invalid.\n\n\textbf{1.} Given a house, how does one determine whether it is constructible with binmus? A set of cells (in grey on Figure 1) such that there is a way to construct the house with binmus on an plan giving Figure 1 is called a \emph{constructible set}, i.e. it is possible to construct the house respecting the binmus and the constraints. Starting from Figure 1, is the orange set of cells constructible?\n\n\textbf{2.} Given and , is it possible to construct a new house such that there are never two consecutive binmus (forming a wall of length or more)? For example the plan of Figure 1 is then no longer accepted. Propose different general constructions when this is possible.\n\n\textbf{3.} How many cells can a loop contain at most?\n\n\textbf{4.} Given and , which external cells belong to a constructible set? How many elements can a constructible set contain at most?\n\n\textbf{5.} Given and , characterize the constructible sets.\n\n\textbf{6.} Vladimir, an uncle of Donald, also wants to construct a new house but on a triangular grid, that is to say with cells in the form of equilateral triangles of side . Take up the problem in this case, and in the general case of an -gon.\n\n\textbf{7.} Propose and study other avenues of research.
Topic: Combinatoria, Geometria piana Metodo: Casework, Conteggio, Estremalità Abilita: Modellizzazione, Conteggio sistematico, Ragionamento geometrico Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF
Piani di pavimentazione di una casa da costruire su una griglia con pareti troppo lunghe (binmus) e celle esterne
Donald vuole costruire una nuova casa. Deve aggiungere partizioni interne. La casa è un rettangolo di dimensioni , dove e sono integri , che viene decomposto in cellule unità di lato . Per evitare la formazione di corridoi, una cella può non avere due lati all’interno della casa: tale cella è chiamata cella interna, mentre le celle al bordo sono chiamate celle esterne. Donald, purtroppo, ha commesso un errore nel suo ordine: entusiasta, ha ordinato i muri troppo lunghi. Un muro così troppo lungo si chiama “binmu”. Due binmus possono incrociare in un singolo punto (formando una croce), ma non possono essere sovrapposti. Donald cerca quali piani sono possibili per la sua nuova casa con questi vincoli. La figura 1 rappresenta un piano valido per una casa di dimensioni . La figura 2 rappresenta tre piani di abitazioni che sono invalidi. Un insieme di celle (in grigio sulla figura 1) in modo che ci sia un modo per costruire la casa con binmus su un piano che dà la figura 1 è chiamato un insieme \emph{construibile}, cioè È possibile costruire la casa rispettando i binmus e i vincoli. A partire dalla figura 1, è possibile costruire l’insieme arancione di cellule?\n\n\textbf{2.} Dato e , è possibile costruire una nuova casa in modo che non ci siano mai due binmus consecutivi (formando un muro di lunghezza o più)? Per esempio, il piano della figura 1 non è più accettato. Propone diverse costruzioni generali quando questo è possibile.\n\n\textbf{3.} Quante cellule può contenere un ciclo al massimo?\n\n\textbf{4.} Dato e , quali cellule esterne appartengono a un insieme costruttibile? Quanti elementi un insieme costruttibile può contenere al massimo?\n\n\textbf{5.} Dato e , caratterizzare gli insiemi costruttibili.\n\n\textbf{6.} Vladimir, un zio di Donald, vuole anche costruire una nuova casa ma su una griglia triangolare, cioè con cellule sotto forma di triangoli equilaterali di lato . Prendi il problema in questo caso e nel caso generale di un -gon.\n\n\textbf{7.} Proponi e studia altre vie di ricerca.
Three friends sharing two bicycles to minimize the time for all to reach the end of a path
Martin, Anna and Carole decide to go for a walk by bicycle. They discover that Martin forgot to lock his bicycle, which was stolen. To return, they have only two bicycles for three people, and they want to reach a point. One considers a person who moves on foot at speed and on a bicycle at speed , . Initially, the three friends and their two bicycles are at the starting point. At any moment, a walker may take a bicycle if and only if it is at the same point on the path (a walker may walk next to a bicycle while pushing it), and at no moment may a walker move backward. A walker who sets down a bicycle leaves it there where it is and continues on foot. One supposes the walkers never go back.\n\nLet ; one possible organization is the following. At departure (), Anna and Carole start on bicycles; Martin starts on foot. At time , at the half of the path, Carole sets down her bicycle and continues on foot, while Anna continues on bicycle. At time , Martin picks up the bicycle left by Carole, and Anna arrives at the end of the path. Finally, at time , Martin and Carole arrive at the same time at the end of the path. The trajectory is represented on Figure 5. The walkers seek to minimize the duration necessary so that all three arrive at the end of the path. In the example, .\n\n\textbf{1.} Given , what is , the smallest value possible for ? Give an example of an organization such that .\n\n\textbf{2.} Henceforth there are walkers and bicycles, with . What does equal as a function of , and ? How does one reach the minimum? One may begin with the cases , and .\n\n\textbf{3.} Henceforth, the walkers are authorized to go backward on bicycle and to transport with them an additional bicycle (but not on foot). Take up the previous questions, if this allows improving .\n\n\textbf{4.} One supposes now that there are climbs and descents. A bicycle going alone on a slope moves at speed , with on a descent and on a climb, that is to say going up the bicycle rolls back. Take up the previous questions in this case, as a function of the parameter .\n\n\textbf{5.} The walkers have rollerblades of speed and rollerblades that advance at speed . Take up the previous questions in this case.\n\n\textbf{6.} Propose and study other avenues of research.
Topic: Algebra, Combinatoria Metodo: Estremalità, Casework Abilita: Modellizzazione, Manipolazione algebrica, Stima Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF
Tre amici condividono due biciclette per ridurre al minimo il tempo per raggiungere la fine di un percorso
Martin, Anna e Carole decidono di fare una passeggiata in bicicletta. Scoprono che Martin ha dimenticato di chiudere la bicicletta, che era stata rubata. Per tornare, hanno solo due biciclette per tre persone, e vogliono raggiungere un punto. Si considera una persona che si muove a piedi a velocità e su una bicicletta a velocità , . Inizialmente, i tre amici e le loro due biciclette sono al punto di partenza. In qualsiasi momento, un passeggero può prendere una bicicletta se e solo se si trova nello stesso punto del sentiero (un passeggero può camminare accanto a una bicicletta mentre la spinge), e in nessun momento può muoversi indietro. Un passeggero che scende una bicicletta la lascia lì dove è e continua a piedi. Si suppone che i camminatori non tornino mai indietro. Alla partenza (), Anna e Carole partono in bicicletta; Martin parte a piedi. Al tempo , a metà percorso, Carole scende la bicicletta e continua a piedi, mentre Anna continua a biciclare. Al tempo , Martin raccoglie la bicicletta lasciata da Carole, e Anna arriva alla fine del sentiero. Infine, al tempo , Martin e Carole arrivano allo stesso tempo alla fine del sentiero. La traiettoria è rappresentata nella figura 5. I passeggeri cercano di ridurre al minimo la durata necessaria per arrivare tutti e tre alla fine del percorso. Nell’esempio, .\n\n\textbf{1.} Dato , qual è , il valore più piccolo possibile per ? Fornisci un esempio di un’organizzazione tale che .\n\n\textbf{2.} D’ora in poi ci siano passeggeri e biciclette, con . Cosa è uguale a come funzione di , e ? Come si arriva al minimo? Si può iniziare con i casi , e .\n\n\textbf{3.} D’ora in poi, i passeggiatori sono autorizzati a tornare indietro in bicicletta e a trasportare con loro una bicicletta aggiuntiva (ma non a piedi). Prendiamo le domande precedenti, se questo consente di migliorare .\n\n\textbf{4.} Si suppone ora che ci siano alti e discendenti. Una bicicletta che va da sola su una pendenza si muove a velocità , con in discesa e in salita, cioè in salita la bicicletta ruota indietro. Prendiamo le domande precedenti in questo caso, in funzione del parametro .\n\n\textbf{5.} I camminatori hanno lamelle a rotazione e lamelle a rotazione che avanzano a velocità . Prendi le domande precedenti in questo caso. Proponi e studia altre vie di ricerca.
Scheduling trains onto station tracks (dead-end, one-way, two-way) so an arrival order is admissible
Julie has just been named chief of the station. She must manage trains. The trains arrive each day in a precise order, the \emph{order of arrival}, and must repart on the tracks during the night in the \emph{order of departure}. In the morning the trains must be able, in the order of departure, to access the exit directly without being blocked by another train.\n\nEach track can contain up to consecutive trains. There exist three types of tracks: the \emph{impasses} (dead-ends), where the trains arrive by the left and repart by the left in the morning; the \emph{one-way tracks} (voies à sens unique), where the trains arrive by the left and repart by the right in the morning; the \emph{two-way tracks} (voies à double sens), where the trains can arrive by either side in the evening and repart by either side in the morning.\n\nIf Julie manages to find a solution that allows reparting all the trains in the order with the tracks at her disposition, one says that the order of arrival is \emph{admissible}. For example, if Julie must repart three trains and has only one impasse at her disposition, the order of arrival is admissible, but not . Figure 6 represents an example with trains and one track of each type, with arrival order ; this order is admissible. One remarks that there are several possibilities to repart the trains on a two-way track: one can choose either to enter by the left or by the right.\n\n\textbf{1.} One interests oneself in a station that has only one track. Under which conditions is an order of arrival admissible: (a) if the track is an impasse? (b) if the track is one-way? (c) if the track is two-way?\n\nLet an integer such that divides . One supposes that the trains arrive in the following order: .\n\n\textbf{2.} What is the minimal number of tracks necessary for this order to be admissible: (a) if the tracks are all impasses? (b) if the tracks are all one-way? (c) if the tracks are all two-way?\n\n\textbf{3.} What is the smallest number of tracks for which all orders of arrival are admissible: (a) if the tracks are all impasses? (b) if the tracks are all one-way? (c) if the tracks are all two-way?\n\n\textbf{4.} One supposes in this question that there is no longer one track only and it is two-way. Henceforth one possesses a machine that allows passing a train above another train. This operation takes hour. As the price is high, how many times must one pass a train above another?\n\n\textbf{5.} Take up the previous question with several tracks and eventually impasses or one-way tracks.\n\n\textbf{6.} Propose and study other avenues of research.
Topic: Combinatoria Metodo: Casework, Conteggio, Estremalità Abilita: Modellizzazione, Conteggio sistematico, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita Fonte: apri PDF
Ricordare i treni sui binari delle stazioni (terreno, a senso unico, a senso doppio) in modo che sia ammissibile un ordine di arrivo
Julie è stata appena nominata capo della stazione. Lei deve gestire i treni. I treni arrivano ogni giorno in un ordine preciso, l’ordine di arrivo, e devono ritirarsi sulle binarie durante la notte nell’ordine di partenza. La mattina i treni devono essere in grado, nell’ordine di partenza, di accedere direttamente all’uscita senza essere bloccati da un altro treno. Esistono tre tipi di binari: i \emph{impasses} (dead-end), in cui i treni arrivano a sinistra e partono a sinistra al mattino; i \emph{one-way tracks} (voies à sens unique), in cui i treni arrivano a sinistra e partono a destra al mattino; i \emph{two-way tracks} (voies à double sens), in cui i treni possono arrivare da entrambi i lati la sera e partire da entrambi i lati al mattino.\n\nSe Julie riesce a trovare una soluzione che consente di ripartire tutti i treni in ordine con i binari a sua disposizione, si dice che l’ordine di arrivo è \emph{admissible}. Ad esempio, se Julie deve ripartire tre treni e dispone di un solo impasse, l’ordine di arrivo è ammissibile, ma non . La figura 6 rappresenta un esempio con treni e una pista di ciascun tipo, con ordine di arrivo ; tale ordine è ammissibile. Si osserva che ci sono diverse possibilità di ripartire i treni su una pista bidirezionale: si può scegliere di entrare a sinistra o a destra. In quali condizioni è ammissibile un ordine di arrivo: a) se la pista è un impasse? b) se la pista è a senso unico? (c) se la pista è bidirezionale?\n\nLascia che un numero intero dividi . Si suppone che i treni arrivano nell’ordine seguente: .\n\n\textbf{2.} Qual è il numero minimo di binari necessario per essere ammissibili a tale ordine: (a) se tutte le binari sono impasse? b) se le binarie sono tutte a senso unico? Qual è il numero minimo di binari per i quali tutti gli ordini di arrivo sono ammissibili: a) se tutti i binari sono impassi? b) se le binarie sono tutte a senso unico? (c) se le tracce sono tutte bidirezionali?\n\n\textbf{4.} Si suppone in questa domanda che non ci sia più solo una traccia ed è bidirezionale. D’ora in poi si possiede una macchina che permette di passare un treno sopra un altro. Questa operazione richiede ora. Poiché il prezzo è elevato, quante volte si deve passare un treno sopra un altro?\n\n\textbf{5.} Prendi la domanda precedente con più binari e alla fine impasse o binari unidirezionali.\n\n\textbf{6.} Proponi e studi altri percorsi di ricerca.
Finding a vegetarian pizza hidden in a stack of boxes in the fewest moves
Sophie likes pizzas a lot, but especially the vegetarian ones. She faces piles () which contain respectively boxes, each box containing exactly one pizza. Sophie knows that among these pizzas there are exactly which are vegetarian. She would like to find one in the least time possible.\n\nEach minute, Sophie chooses a box at the top of one of the piles, takes it and looks inside. She then puts the box back on top of one of the piles (or eventually starts a new pile). One denotes by the smallest number of minutes such that Sophie has a strategy that allows her to find a vegetarian pizza in minutes, regardless of the position of the vegetarian pizzas in the piles at departure. For example, .\n\n\textbf{1.} Estimate as a function of the values of and . Begin by studying the following cases: (a) ; (b) and ; (c) arbitrary and ; (d) and arbitrary; (e) ; (f) , arbitrary.\n\nOne supposes now that Sophie has only one pile of height with for all . The pizza boxes are of thickness . Henceforth Sophie may not put more than boxes on the same pile.\n\n\textbf{2.} As a function of and , which are the values of for which Sophie can ensure finding a vegetarian pizza from the initial disposition? One supposes henceforth that one reparts the boxes on the piles that one chooses.\n\n\textbf{3.} One places oneself in the case of question 2 (pizzas of finite height). One denotes by the smallest number such that Sophie has a strategy that allows her to find a vegetarian pizza in minutes, regardless of the position of the vegetarian pizzas in the piles of departure. Estimate in the same cases as question 1.\n\n\textbf{4.} One supposes anew that the pile is of infinite height. One supposes also that the piles are aligned from left to right. Sophie has eaten the pizza and wishes to displace herself as little as possible. When she takes the boxes from a pile, she puts them back on the same pile or on a neighboring pile. Take up the previous questions in this case.\n\n\textbf{5.} At present, and Sophie knows that the vegetarian pizza has been placed at random in the pile of infinite height, that is to say that each box at the top of the pile contains the vegetarian pizza with probability . She seeks to determine the number of minutes necessary to find the pizza. The average is taken over the set of possible positions of the pizza. Take up the previous questions in this case.\n\n\textbf{6.} Propose and study other avenues of research.
Topic: Combinatoria, Probabilità Metodo: Casework, Conteggio, Estremalità Abilita: Modellizzazione, Conteggio sistematico, Stima Area: Combinatoria, Logica e Probabilita Fonte: apri PDF
Trovare una pizza vegetariana nascosta in una pila di scatole in pochi movimenti
A Sophie piacciono molto le pizze, ma soprattutto quelle vegetariane. Si trova di fronte a pile () che contengono rispettivamente scatole , ciascuna scatola contenente esattamente una pizza. Sophie sa che tra queste pizze ci sono esattamenteche sono vegetariane. Le piacerebbe trovarne uno nel minor tempo possibile. Ogni minuto, Sophie sceglie una scatola in cima a una pila, la prende e guarda dentro. Poi rimette la scatola sulla cima di una delle pile (o alla fine inizia una nuova pila). Uno denota con il numero minore di minuti in modo tale che Sophie ha una strategia che le consente di trovare una pizza vegetariana in minuti, indipendentemente dalla posizione delle pizze vegetariane nelle pile alla partenza. Per esempio, .\n\n\textbf{1.} Estimare come funzione dei valori di e . Inizia studiando i seguenti casi: (a) ; (b) e ; (c) arbitrario e ; (d) e arbitrario; (e) ; (f) , arbitrario. Le scatole da pizza sono di spessore . Da ora in poi Sophie non può mettere più di scatole sulla stessa pila.\n\n\textbf{2.} Come funzione di e , quali sono i valori di per i quali Sophie può garantire di trovare una pizza vegetariana dalla disposizione iniziale? Da ora in poi si suppone di ripartire le scatole sulle pile che si scelgono. Si colloca nel caso della domanda 2 (pizza di altezza finita). Uno indica con il numero più piccolo in modo tale che Sophie ha una strategia che le consente di trovare una pizza vegetariana in minuti, indipendentemente dalla posizione delle pizze vegetariane nelle pile di partenza. Estimare nei medesimi casi come la domanda 1.\n\n\textbf{4.} Si suppone nuovamente che l’insieme sia di altezza infinita. Si suppone anche che le pile siano allineate da sinistra a destra. Sophie ha mangiato la pizza e desidera spostarsi il meno possibile. Quando prende le scatole da una pila, le rimette sulla stessa pila o su una pila vicina. Prendiamo le domande precedenti in questo caso.\n\n\textbf{5.} Attualmente, e Sophie sa che la pizza vegetariana è stata collocata a caso nella pila di altezza infinita, cioè che ogni scatola in cima alla pila contiene la pizza vegetariana con probabilità . Cerca di determinare il numero di minuti necessari per trovare la pizza. La media è presa sulla serie di posizioni possibili della pizza. Prendi le domande precedenti in questo caso. Proponi e studia altre vie di ricerca.
Placing chords (Korde walls) in a disk to prevent regular-polygon candidates from seeing each other
The teachers of espionage want to recruit someone to become agent 008. They organize a contest to separate the candidates. The exam takes place in a room in the form of a disk of radius . To space the candidates as much as possible, their tables are on the edge of the disk and form a regular -gon. To prevent any cheating, it is necessary to \emph{partition} the room, that is to say to prevent the candidates from seeing one another.\n\nTristan is charged with organizing the exam. He decides to install the partitions (\emph{cloisons}). A cloison may be installed between any two points of the room, except if it passes through the exact spot where a candidate’s table is. One says that two cloisons \emph{cross} when the segments intersect (except if the point of intersection is the extremity of one of the cloisons).\n\nTristan decides to obtain his cloisons from the company Körde. This company can construct cloisons of all sizes, but they must be fixed to the walls of the room, as on Figure 7. On this example, the cloisons of the company Körde prevent candidates and from seeing each other, but not candidates and .\n\n\textbf{1.} What is the minimal number of cloisons to place to partition the room in the following cases: (a) if the cloisons may cross? (b) if the cloisons may not cross?\n\nFrom now until the end of the problem, two cloisons may not cross. The teachers of espionage have decided to organize a large recruitment campaign. They have published announcements for different posts. There are candidates for each post, so a total of candidates. The candidates always form a regular -gon inscribed in the circle bounding the room but, for each post, the candidates for that post are distributed in an arbitrary manner among the tables. Tristan received a single instruction: it is absolutely necessary that two candidates for the same post cannot see each other.\n\n\textbf{2.} Find the smallest integer such that Tristan is sure of being able to prevent cheating by installing Körde cloisons, whatever the distribution of the candidates among the posts, in the following cases: (a) for and arbitrary; (b) for and arbitrary; (c) for arbitrary values of and .\n\n\textbf{3.} Tristan had misunderstood the instruction: two candidates for the same post may see each other, on the other hand it is imperative that candidates for different posts cannot see each other during the exam. Take up the previous question in this case.\n\nTristan is not certain that this solution always works. He decides to change his supplier and turn to the company Tayfix. This company produces uniquely cloisons of length fixed, but they may be placed at any point of the disk without being fixed to a wall (cf. Figure 8). On this example, the cloisons of the company Tayfix prevent candidates and from seeing each other, but not candidates and ; one considers that the extremities of a cloison block the view.\n\n\textbf{4.} (a) For which values of is it possible to partition the room, for ? (b) For which values of can one find a length such that it is possible to partition the room with cloisons of length ? (c) As a function of , estimate the largest such that it is possible to partition the room with cloisons of length . Does there exist a real for which it is always possible to partition the room, whatever the value of ?\n\nThe Tayfix cloisons do not suffice to prevent the candidates from spying on one another using ultrasound devices. Tristan decides to replace the cloisons with pillars of concrete. He contacts the company Unkalibr, which proposes to install circular pillars of radius . The pillars must be entirely included in the room and may not overlap, but two pillars may be tangent. On Figure 9 the pillars prevent candidates and from seeing each other, but not candidates and .\n\n\textbf{5.} As a function of , what are the radii for which it is possible to partition the room with pillars? Begin by studying small values of , then propose bounds on the possible radii in the general case.\n\n\textbf{6.} Propose and study other avenues of research.
Topic: Geometria piana, Combinatoria Metodo: Casework, Estremalità, Simmetria Abilita: Ragionamento geometrico, Modellizzazione, Casework accurato Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF
Posizione di accordi (pareti di Korde) in un disco per evitare che i candidati a poligono regolare si vedano fra loro
Gli insegnanti di spionaggio vogliono reclutare qualcuno per diventare agente 008. Organizzano un concorso per separare i candidati. L’esame si svolge in una sala a forma di disco di raggio . Per spaziare il più possibile i candidati, le loro tabelle sono sul bordo del disco e formano un normale -gon. Per prevenire qualsiasi inganno, è necessario dividere la stanza, ovvero impedire ai candidati di vedersi. Tristan è incaricato di organizzare l’esame. Decide di installare le partizioni. Si può installare un cloison tra due punti della stanza, a meno che non passi attraverso l’esatto punto dove si trova il tavolo del candidato. Uno dice che due cloisons quando i segmenti si incrociano (a meno che il punto di intersezione sia l’estremità di uno dei cloisons). Questa azienda può costruire chiusoni di tutte le dimensioni, ma devono essere fissati alle pareti della stanza, come nella Figura 7. In questo esempio, i cloison della società Körde impediscono ai candidati e di vedersi, ma non ai candidati e .\n\n\textbf{1.} Qual è il numero minimo di cloison da posizionare per dividere la stanza nei seguenti casi: a) se i cloison possono attraversare? (b) se le cloisons non possono incrociare? Gli insegnanti di spionaggio hanno deciso di organizzare una grande campagna di reclutamento. Hanno pubblicato annunci per diversi posti . Ci sono candidati per ogni posto, quindi un totale di candidati . I candidati formano sempre un normale -gon inscritto nel cerchio che confina la stanza, ma, per ciascun posto, i candidati per quel posto sono distribuiti in modo arbitrario tra le tabelle . Tristan ha ricevuto una singola istruzione: è assolutamente necessario che due candidati allo stesso incarico non possano vederci.\n\n\textbf{2.} Trova il numero intero più piccolo in modo che Tristan sia sicuro di essere in grado di prevenire le truffe installaendo Körde cloisons, qualunque sia la distribuzione dei candidati tra i posti , nei seguenti casi: (a) per e arbitrario; (b) per e arbitrario; (c) per i valori arbitrari di e .\n\textbf{3.} Tristan aveva frainteso la scelta: due candidati allo stesso incarico, sul lato che non possono vedere gli altri candidati durante l’esame, è imperativo che non si possano vedere diversi incarichi. Prendi la domanda precedente in questo caso. Tristan non è certo che questa soluzione funzioni sempre. Decide di cambiare fornitore e rivolgersi alla compagnia Tayfix. Questa azienda produce esclusivamente cloison di lunghezza fissa , ma possono essere posizionati in qualsiasi punto del disco senza essere fissati a un muro (cfr. Figura 8). In questo esempio, i cloison della società Tayfix impediscono ai candidati e di vedersi, ma non ai candidati e ; si ritiene che le estremità di un cloison bloccino la vista.\n\n\textbf{4.} (a) Per quali valori di è possibile dividere la stanza, per ? b) Per quali valori di si può trovare una lunghezza tale da rendere possibile la divisione della stanza con chiusoni di lunghezza ? (c) Come funzione di , stimare il più grande in modo tale che sia possibile dividere la stanza con chiusoni di lunghezza . Esiste un vero per il quale è sempre possibile dividere la stanza, qualunque sia il valore di ?\n\nLe cloison Tayfix non sono sufficienti per impedire ai candidati di spiarsi a vicenda utilizzando dispositivi ad ultrasuoni. Tristan decide di sostituire i cloison con pilastri di cemento. Si rivolge alla società Unkalibr, che propone di installare pilastri circolari di raggio . I pilastri devono essere interamente inseriti nella stanza e non possono sovrapporresi, ma due pilastri possono essere tangenti. Nella figura 9, i pilastri impediscono ai candidati e di vedersi, ma non ai candidati e .\n\n\textbf{5.} Come funzione di , quali sono i raggi per i quali è possibile dividere la stanza con i pilastri? Iniziare studiando piccoli valori di , poi proporre limiti sui possibili raggi nel caso generale.\n\n\textbf{6.} Proporre e studiare altre vie di ricerca.
Chameleons on a graph changing color by propagation; minimizing requests (difficulty of a coloring)
Victor takes care of and studies a population of chameleons. The chameleons are linked by ties of friendship. These ties are represented on a graph, that is to say a set of vertices linked by a set of edges. The vertices are the chameleons and two friend chameleons are linked by an edge.\n\nOne supposes that the chameleons can take different colors, numbered from to . A chameleon can change from color to color in two cases: either because Victor asks it to, or because one of its friends of color changes to color . Thus, when Victor asks a chameleon to change color, all the chameleons friends of who were of the same color as do the same, then their friends, etc.\n\nLet be a graph representing a population of chameleons and a coloring of the graph, that is to say the data of the color of the chameleons at the start. Victor wants to make all the chameleons be of the same color, while minimizing the number of times he must ask a chameleon to change color. One calls \emph{difficulty} of the minimal number of requests necessary so that all the chameleons are of the same color. For a given graph , one denotes by the maximal difficulty possible of a coloring of with colors. This corresponds to the worst situation possible for Victor.\n\nFigure 10 represents an example with chameleons and colors. For this graph , at each step Victor asks a chameleon to become blue, which entails no other change since this chameleon has no friend of the same color. Then he asks a blue chameleon to become orange; by propagation all the blue friends of this chameleon change color, as well as the friends of its friends. Finally Victor asks the last chameleon to become orange and all the chameleons are now of the same color. In this example, for this particular initial coloring, Victor succeeded in three steps.\n\nOne denotes by the graph constituted of aligned vertices, each linked to its neighbors of the right and of the left when they exist.\n\n\textbf{1.} Determine or give bounds for in the following cases: (a) ; (b) ; (c) arbitrary.\n\nOne denotes by the rectangular network of size .\n\n\textbf{2.} Is the sequence increasing?\n\n\textbf{3.} Determine or bound as a function of , and .\n\n\textbf{4.} Let be an arbitrary connected graph. A connected graph is a graph such that it is always possible to pass from one vertex to another by a sequence of edges. In each of the three following cases, can increase? Decrease? If so, by how much at most? (a) A new chameleon arrives and causes a dispute between two friends: it breaks their tie of friendship but becomes the friend of each of them. (b) Two chameleons become friends. (c) A new chameleon arrives and becomes friend of two chameleons (which are not necessarily friends with each other).\n\n\textbf{5.} In this question only, Victor decides it is preferable to have a single interlocutor. He begins by choosing one chameleon and can then address only it to ask for changes of color. What is the impact of this decision: (a) in the case of the segment ? (b) in the case of the rectangle ? (c) in the general case?\n\n\textbf{6.} Let and be two integers. Among all the connected graphs with vertices and edges, which are those that minimize ? Which are those that maximize ? Begin by studying the cases , and .\n\n\textbf{7.} Propose and study other avenues of research.
Topic: Combinatoria Metodo: Grafi, Estremalità, Casework, Colorazione Abilita: Modellizzazione, Astrazione, Ragionamento geometrico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF
*Camelioni su un grafico che cambiano colore per propagazione; minimizzazione delle richieste (difficoltà di colorazione) *
Victor si prende cura e studia una popolazione di camaleoni. I camaleoni sono legati da legami di amicizia. Questi legami sono rappresentati su un grafico, cioè un insieme di vertici collegati da un insieme di bordi. I vertici sono i camaleoni e due camaleoni amici sono collegati da un bordo.\n\nSi suppone che i camaleoni possano prendere diversi colori, numerati da a . Un camaleone può cambiare colore da a in due casi: o perché Victor lo chiede, o perché uno dei suoi amici di colore cambia colore . Quindi, quando Victor chiede a un camaleone di cambiare colore, tutti gli amici dei camaleoni di che erano dello stesso colore di fanno lo stesso, quindi i loro amici, ecc.\n\nLasciate essere un grafico che rappresenta una popolazione di camaleoni e un coloramento del grafico, cioè i dati del colore dei camaleoni all’inizio. Victor vuole che tutti i camaleoni siano dello stesso colore, riducendo al minimo il numero di volte che deve chiedere a un camaleone di cambiare colore. Si chiama la difficoltà di il numero minimo di richieste necessarie affinché tutti i camaleoni siano dello stesso colore. Per un dato grafico , si indica con la difficoltà massima possibile di un coloramento di con colori. Questo corrisponde alla peggiore situazione possibile per Victor.\n\nLa figura 10 rappresenta un esempio con camaleoni e colori. Per questo grafico , a ogni passo Victor chiede a un camaleone di diventare blu, il che non comporta nessun altro cambiamento dal momento che questo camaleone non ha amico dello stesso colore. Poi chiede a un camaleone azzurro di diventare arancione; per propagazione tutti gli amici azzurri di questo camaleone cambiano colore, così come gli amici dei suoi amici. Finalmente Victor chiede all’ultimo camaleone di diventare arancione e tutti i camaleoni sono ora dello stesso colore. In questo esempio, per questo particolare colore iniziale, Victor ha avuto successo in tre passaggi.\n\nOne denota con il grafico costituito da vertici allineati , ciascuno legato ai suoi vicini di destra e di sinistra quando esistono.\n\n\textbf{1.} Determina o dà confini per nei seguenti casi: (a) ; (b) ; (c) arbitrario.\n\nOne denota con la rete rettangolare di dimensioni .\n\ntextbf{2.} La sequenza è in aumento?\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n Un grafico collegato è un grafico tale che è sempre possibile passare da un vertice all’altro attraverso una sequenza di bordi. In ciascuno dei tre seguenti casi, può aumentare? Riduzione? Se sì, per quanto al massimo? (a) Un nuovo camaleone arriva e causa una disputa tra due amici: rompe il legame di amicizia, ma diventa amico di ciascuno di loro. (b) Due camaleoni diventano amici. (c) Un nuovo camaleone arriva e diventa amico di due camaleoni (che non sono necessariamente amici l’uno con l’altro). Solo in questa domanda, Victor decide che è preferibile avere un solo interlocutore. Inizia scegliendo un camaleone e poi può rivolgersi solo a lui per chiedere cambiamenti di colore. Qual è l’impatto di questa decisione: a) nel caso del segmento ? b) nel caso del rettangolo ? (c) nel caso generale?\n\n\textbf{6.} e siano due numeri interi. Tra tutti i grafici connessi con vertici e bordi , quali sono quelli che riducono al minimo ? Quali sono quelle che massimizzano ? Iniziare studiando i casi , e .\n\n\textbf{7.} Proporre e studiare altre vie di ricerca.
Distributing chocolates round-robin to children in a line; when the configuration becomes balanced
Papi Théo offers chocolates to his grandchildren. His grandchildren are placed in a line, numbered from to . Each day he opens a box of chocolates. The first day he gives the first box to child number ; this one takes a chocolate, then passes the box to its neighbor, who serves itself, and so on. For fairness, so that it is not always the same one who serves first, the second day it is the second child who receives the full box, takes a chocolate, then passes it to child , etc. When the box arrives at child , this one passes it to child .\n\nBut the boxes of chocolates are of variable size. The first day, the box contains only a single chocolate. The second day it contains . And so on, the -th day the box contains chocolates.\n\nFigure 13 shows the case of grandchildren, after days. The grandchildren received respectively , , and chocolates. The number written on each chocolate corresponds to the day it was distributed.\n\nOne says that at a given instant a configuration is \emph{balanced} if, at that instant, all the grandchildren have received the same number of chocolates.\n\n\textbf{1.} According to the value of , is the configuration balanced after days?\n\n\textbf{2.} According to the values of , does there exist a day at the end of which the configuration is balanced? If so, what is the first day where this occurs?\n\nPapi Théo cannot keep buying ever larger boxes of chocolates. He decides to organize himself differently; let be the number of chocolates in the box the -th day. The previous questions correspond to .\n\n\textbf{3.} To limit the inflation of the size of the boxes of chocolates, Papi Théo decides that every day one must start over from zero. He chooses boxes such that is the remainder of the Euclidean division of by . According to the values of and , does there exist a day at the end of which the configuration is balanced? If so, what is the first day where this occurs?\n\nPapi Théo now chooses integers and defines the function so that for every integer , where is the remainder of the Euclidean division of by . The previous case corresponds to choosing for all and .\n\n\textbf{4.} According to the values of , and of positive integers , is it possible to choose the integers so that, after days, child has received exactly chocolates, for all ? One says that a mode of distribution is \emph{equitable} if there exists an infinity of days at the end of which the configuration is balanced. Papi Théo henceforth buys his boxes of chocolates by lot. A lot of boxes of chocolates is a set of boxes of sizes with . He declares that a lot is \emph{reasonable} if one can find a permutation of the sizes of the boxes of the lot that gives an equitable mode of distribution. For example, for and , the lot is reasonable because by choosing one obtains an equitable mode of distribution. On the other hand is not a reasonable lot.\n\n\textbf{5.} According to the integer , what are the values of for which all the possible lots are reasonable?\n\n\textbf{6.} What are the necessary and sufficient conditions for a given lot to be reasonable?\n\n\textbf{7.} One supposes that for every integer , . Is the distribution equitable? And with for another integer ?\n\n\textbf{8.} Propose and study other avenues of research.
Topic: Teoria dei Numeri, Combinatoria Metodo: Congruenze, Conteggio, Casework Abilita: Manipolazione algebrica, Riconoscimento di pattern, Conteggio sistematico Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF
Distribuzione di cioccolatini a rotonda ai bambini in fila; quando la configurazione diventa equilibrata
Papi Théo offre cioccolati ai suoi nipoti. I suoi nipoti sono posti in una riga, numerata da a . Ogni giorno apre una scatola di cioccolati. Il primo giorno dà la prima scatola al bambino numero ; questo prende un cioccolato, poi passa la scatola al suo vicino, che serve se stesso, e così via. Per essere onesti, non è sempre lo stesso che serve per primo, il secondo giorno è il secondo bambino che riceve la scatola piena, prende un cioccolato, poi lo passa al bambino , ecc. Quando la scatola arriva al bambino , questo la passa al bambino . Il primo giorno, la scatola contiene solo una sola cioccolata. Il secondo giorno contiene . E così via, il -th giorno la scatola contiene cioccolatini.\n\nLa figura 13 mostra il caso dei nipoti , dopo giorni. I nipoti hanno ricevuto rispettivamente , , e cioccolati. Il numero scritto su ogni cioccolato corrisponde al giorno in cui è stato distribuito.\n\nSi dice che in un dato istante una configurazione è \emph{balanced} se, in quel istante, tutti i nipoti hanno ricevuto lo stesso numero di cioccolati.\n\n\textbf{1.} Secondo il valore di , la configurazione è bilanciata dopo giorni?\n\n\textbf{2.} Secondo i valori di , esiste un giorno al termine del quale la configurazione è bilanciata? Se è così, qual è il primo giorno in cui questo accade? Papa Théo non può continuare a comprare scatole di cioccolato sempre più grandi. Decide di organizzarsi in modo diverso; lascia che il numero di cioccolati nella scatola sia il numero di cioccolati nella scatola il -th giorno. Per limitare l’inflazione delle dimensioni delle scatole di cioccolato, Papi Théo decide che ogni giorno bisogna ricominciare da zero. Sceglie caselle tali che sia il resto della divisione euclidica di da . Secondo i valori di e , esiste un giorno al termine del quale la configurazione è equilibrata? Se è così, qual è il primo giorno in cui questo accade?\n\nPapi Théo sceglie ora enti e definisce la funzione in modo che per ogni intero , dove è il resto della divisione euclidiana di da . Il caso precedente corrisponde alla scelta di per tutti i e .\n\n\textbf{4.} Secondo i valori di , e dei numeri interi positivi , è possibile scegliere i numeri interi in modo che, dopo giorni, il bambino abbia ricevuto esattamente cioccolati, per tutti ? Si dice che un modo di distribuzione è \emph{equitable} se esiste un’infinità di giorni al termine dei quali la configurazione è bilanciata. Papi Théo comprerà le sue scatole di cioccolato a lotto. Un sacco di scatole di cioccolato è un insieme di scatole di dimensioni con . Egli dichiara che un lotto è ragionevole se si può trovare una permutazione delle dimensioni delle scatole del lotto che dà un modo equo di distribuzione. Ad esempio, per e , il lotto è ragionevole perché scegliendo si ottiene un modo di distribuzione equo. D’altra parte non è un lotto ragionevole.\n\n\textbf{5.} Secondo il numero intero , quali sono i valori di per i quali tutti i lotti possibili sono ragionevoli?\n\n\textbf{6.} Quali sono le condizioni necessarie e sufficienti per un dato lotto essere ragionevole?\n\n\textbf{7.} Si suppone che per ogni numero intero , . La distribuzione è equitativa? E con per un altro intero ?\n\n\textbf{8.} Proporre e studiare altre vie di ricerca.
Tiling a quartier of an infinite equilateral-triangle grid (Los Angeles) with rhombi (losanges)
The city of Los Angeles rests on an infinite triangular grid where each equilateral triangle of side is a building (\emph{immeuble}), as on Figure 14. A \emph{quartier} of this city is a finite set of buildings. Two buildings having a side in common are said to be \emph{neighbors}.\n\nLamia is the mayor of Los Angeles. She wants to partition the quartiers of her city into co-properties, which are losanges (rhombi) formed by two neighboring buildings. Such a partition of a quartier is called a \emph{losangisation}. The number of losangisations possible of a quartier is denoted . For example, for Figure 14 one has because it is impossible to losangise the blue quartier. For Figure 15 one has because there exists a unique manner to losangise the orange quartier.\n\n\textbf{1.} If the quartier is of one of the following forms, is it possible to losangise this quartier? In that case, how many losangisations are possible? If not, how many co-properties can one form at most? (a) An equilateral triangle of side . (b) A losange of side . (c) A losange of side from which two buildings have been removed. In the last case, adapt the answer according to the position of the removed buildings.\n\nIn order to know whether a losangisation is possible, Lamia asks for additional information on the quartiers of the city. Two buildings of the same quartier are said to be of the same \emph{type} if they are oriented in the same direction and if their neighbors in the quartier are on the same sides. For example, in Figure 16, buildings and are of the same type, as are buildings and . All the other buildings are unique.\n\nIn a quartier that she does not know, Lamia knows the number of buildings of each type. This information is denoted . For example, in Figure 16 she knows that there are exactly two buildings of the type “pointing upward, with a single neighbor at the top right”, no building of the type “pointing upward, without neighbor”, etc.\n\n\textbf{2.} Look for necessary conditions on for the quartier to be losangisable. Look for sufficient conditions. Is it possible to find necessary and sufficient conditions on ?\n\n\textbf{3.} Deduce from bounds as precise as possible on .\n\nThe \emph{valence} of a building is the number of neighbors of this building that are in the same quartier. For one denotes by the number of buildings of valence in .\n\n\textbf{4.} What are the quadruplets possible in the case where: (a) is an arbitrary quartier? (b) is a losangisable quartier?\n\n\textbf{5.} Propose and study other avenues of research.
Topic: Combinatoria, Geometria piana Metodo: Colorazione, Conteggio, Invarianti, Casework Abilita: Ragionamento geometrico, Conteggio sistematico, Modellizzazione Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF
Tinging un quartiere di una griglia triangolare equilaterale infinita (Los Angeles) con rhombi (losangi)
La città di Los Angeles si fonda su una griglia triangolare infinita in cui ogni triangolo equilaterale di lato è un edificio (\emph{immeuble}), come nella Figura 14. Un quartiere di questa città è un insieme finito di edifici. Si dice che due edifici che hanno un lato in comune siano vicini. Vuole dividere i quartieri della sua città in coproprietà, che sono losanges (rhombi) formati da due edifici vicini. Tale divisione di un quartiere è chiamata “losangizzazione”. Il numero di perdite possibili di un quartiere è indicato come . Per esempio, per la figura 14 si ha perché è impossibile sanguinare il quartiere blu. Per la figura 15 si ha perché esiste un modo unico per sanguinare il quartiere arancione. In quel caso, quante perdite di sangue sono possibili? In caso contrario, quante coproprietà può formare un individuo al massimo? a) Un triangolo equilaterale laterale . b) Una perdita di lato . c) Una perdita laterale da cui sono stati rimossi due edifici. In quest’ultimo caso, adattare la risposta in base alla posizione degli edifici rimossi. Per sapere se è possibile una perdita di sangue, Lamia chiede ulteriori informazioni sui quartieri della città. Si dice che due edifici dello stesso quartiere siano dello stesso tipo se sono orientati nella stessa direzione e se i loro vicini nel quartiere sono sullo stesso lato. Ad esempio, nella figura 16, gli edifici e sono dello stesso tipo, così come gli edifici e . Tutti gli altri edifici sono unici. In un quartiere che lei non conosce, Lamia conosce il numero di edifici di ogni tipo. Questa informazione è indicata come . Ad esempio, nella Figura 16 sa che ci sono esattamente due edifici del tipo “indicando verso l’alto, con un solo vicino in alto a destra”, nessun edificio del tipo “indicando verso l’alto, senza vicino”, ecc. Cercate condizioni sufficienti. È possibile trovare condizioni necessarie e sufficienti su ?\n\n\textbf{3.} Deduzione dai limiti il più preciso possibile su .\n\nLa valenza di un edificio è il numero di vicini di questo edificio che si trovano nello stesso quartiere. Per si indica con il numero di edifici di valenza in .\n\n\textbf{4.} Quali sono i quadrupletti possibili nel caso in cui: (a) sia un quartiere arbitrario? (b) è un quartiere perduibile?\n\n\textbf{5.} Proporre e studiare altre vie di ricerca.