Tournoi Français des Jeunes Mathématiciens (TFJM²) 2023

Largest axis-aligned square stamp that fits inside a package of given shape, then total area with two disjoint stamps

Philately. Roman is a not-quite-ordinary stamp collector: he does not collect stamps, but ink stamps (tampons). When given a package of a certain shape, he looks for the largest ink stamp to apply to it. The package is laid flat with a fixed orientation, and the ink stamps are squares whose sides are parallel to the axes of a fixed orthogonal coordinate frame.\n\n1. What is the largest possible ink stamp if the package is:\n - A rectangle of sides $a$ and $b$ (with $$\begin{gathered} a \\ neqb \end{gathered}$$), whose sides are parallel to the axes?\n - A disk of radius $r$?\n - An isosceles right triangle whose legs (the sides of the right angle), of length $a$, are parallel to the axes?\n\n2. We now suppose that the package is a convex polygon, that is, a polygon all of whose interior angles measure strictly between 0^\\circ and 180^\\circ. Roman looks at the number of ways (potentially infinite) of placing the ink stamp of maximal size on the package. Which are the possible numbers of ways?\n\nAfter reflection, Roman tells himself a package would carry more ink stamps if he could place 2 ink stamps rather than one; he then seeks to maximize their total size. The 2 ink stamps must be placed inside the package, must be axis-aligned squares, and must not overlap (they may nonetheless touch, having only points in common). Denote by $A_p$ the largest area Roman can obtain if he first applies one ink stamp of maximal size, then a second one in the space that remains; and by $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ the largest total area he can obtain if he can place the two ink stamps as he wishes, provided they are disjoint.\n\n3. Do we always have $$\begin{gathered} A_p=A_{ \\ textdis} \end{gathered}$$? If not, what can the ratio $$\begin{gathered} A_{ \\ textdis}/A_p \end{gathered}$$ be worth?\n\n4. What can $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ be worth if the package is:\n - A rectangle of sides $a$ and $b$ (with $$\begin{gathered} a \\ neqb \end{gathered}$$), whose sides are parallel to the axes?\n - A disk of radius $r$?\n - An isosceles right triangle whose legs, of length $a$, are parallel to the axes?\n\n5. We now suppose the package is a convex polygon. Find, as a function of the number of sides of the polygon, the possible values for the ratio $$\begin{gathered} A_{ \\ textdis}/A_p \end{gathered}$$.\n\n6. We now realize that the ink stamps do not reproduce well if they touch, so Roman now imposes that the union of two ink stamps of arbitrary sizes, when he places them, must not be superposable (the two ink stamps no longer count as the same shuffle, i.e. must not overlap nor touch in a segment). What can $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ be worth if the package is:\n - A rectangle of sides $a$ and $b$ (with $$\begin{gathered} a \\ neqb \end{gathered}$$), whose sides are parallel to the axes?\n - A disk of radius $r$?\n - An isosceles right triangle whose legs, of length $a$, are parallel to the axes?\n\n7. Redo the problem if the ink stamps can no longer be required to be axis-aligned. In particular, find the package shapes that allow Roman to place 2 ink stamps whose total area increases as much as possible.\n\n8. Propose and study other lines of research.

Topic: Geometria piana, Combinatoria Metodo: Estremalità, Casework, Simmetria Abilita: Ragionamento geometrico, Casework accurato, Modellizzazione Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Il più grande timbro quadrato allineato all’asse che si inserisce all’interno di un pacchetto di una determinata forma, quindi superficie totale con due timbri disgiunti

Pilatamente. Roman non è un collezionista di francobolli abbastanza ordinario: non raccoglie francobolli, ma francobolli di inchiostro (tamponi). Quando viene dato un pacchetto di una certa forma, cerca il più grande timbro di inchiostro per applicarlo. Il pacchetto è piatto con un orientamento fisso e i timbri di inchiostro sono quadrati i cui lati sono paralleli agli assi di un quadro di coordinate ortogonali fissi.\n\n1. Qual è il più grande timbro possibile se il pacchetto è:\n - Un rettangolo di lati $a$ e $b$ (con $$\begin{gathered} a \\ neqb \end{gathered}$$), i cui lati sono paralleli agli assi?\n - Un disco di raggio $r$?\n - Un triangolo rettangolo di uguali stelle le cui gambe (i lati dell’angolo giusto), di lunghezza $a$, sono paralleli agli assi?\n\n2. Supponiamo ora che il pacchetto sia un poligono converso, cioè un poligono il cui angolo interno misura rigorosamente tra 0^\\circ e 180^\\circ. Roman analizza il numero di modi (potenzialmente infiniti) per posizionare il timbro di inchiostro di dimensioni massime sul confezionamento. Dopo la riflessione, Roman si dice che un pacchetto porterebbe più francobolli di inchiostro se potesse mettere due francobolli di inchiostro invece di uno; poi cerca di massimizzare la loro dimensione totale. I due timbri di inchiostro devono essere inseriti all’interno dell’imballaggio, devono essere quadrati allineati all’asse e non devono sovrapporre­si (potranno comunque toccarsi, avendo solo punti in comune). Nota con $A_p$ la superficie più grande che Roman può ottenere se prima applica un timbro di inchiostro di dimensioni massime, poi un secondo nello spazio che rimane; e con $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ la superficie totale più grande che può ottenere se può posizionare i due timbri di inchiostro come desidera, a condizione che siano disconnessi.\n\n3. Abbiamo sempre $$\begin{gathered} A_p=A_{ \\ textdis} \end{gathered}$$? Se no, quale può essere il rapporto $$\begin{gathered} A_{ \\ textdis}/A_p \end{gathered}$$?\n\n4. Qual è il valore di $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ se il pacchetto è:\n - Un rettangolo di lati $a$ e $b$ (con $$\begin{gathered} a \\ neqb \end{gathered}$$), i cui lati sono paralleli agli assi?\n - Un disco di raggio $r$?\n - Un triangolo rettangolare di uguali pollice le cui gambe, di lunghezza $a$, sono parallele agli assi?\n\n5. Supponiamo ora che il pacchetto sia un poligono convex. Trova, in funzione del numero di lati del poligono, i valori possibili per il rapporto $$\begin{gathered} A_{ \\ textdis}/A_p \end{gathered}$$.\n\n6. Ora ci rendiamo conto che i francobolli di inchiostro non si riproducono bene se si toccano, quindi Roman impone ora che l’unione di due francobolli di inchiostro di dimensioni arbitrarie, quando li colloca, non deve essere sovrapponibile (i due francobolli di inchiostro non contano più come lo stesso mescolamento, cioè non devono sovrapporre o toccare un segmento). Qual è il valore di $$\begin{gathered} A_{ \\ textdis} \end{gathered}$$ se il pacchetto è:\n - Un rettangolo di lati $a$ e $b$ (con $$\begin{gathered} a \\ neqb \end{gathered}$$), i cui lati sono paralleli agli assi?\n - Un disco di raggio $r$?\n - Un triangolo rettangolare di uguali braccia le cui gambe, di lunghezza $a$, sono parallele agli assi?\n\n7. Risolvi il problema se non è più possibile richiedere che i timbri di inchiostro siano allineati all’asse. In particolare, trovare le forme di confezione che consentono Roman di posizionare 2 timbri di inchiostro la cui superficie totale aumenta il più possibile.\n\n8. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q01

Counting orientations of rivers between villages with assigned altitudes so water flows downhill; functions n_k(P) on graph families

The mountain of streams. Olympe is an apprentice landscape designer. She has been entrusted with building a mountain, on which she installs villages. Rivers connect the villages two by two, and we always assume there is at least 1 village. There can be at most one river between two villages.\n\nOlympe wants each village at a different altitude and assigns to the $v$ villages the altitudes $$\begin{gathered} 1 \\ textkm,2 \\ textkm, \\ dots,v \\ textkm \end{gathered}$$. An orientation of the rivers is a choice, for each river, of a flow direction. For a given orientation, an assignment of altitudes to the villages is valid if for every river the water flows from the higher village to the lower one (downhill). For $$\begin{gathered} k \\ in \\ mathbbN \end{gathered}$$, $n_k(P)$ denotes the number of orientations of the rivers of $P$ such that there are exactly $k$ valid ways of assigning altitudes. For example, $n_0(P)$ is the number of orientations for which there is no valid altitude assignment.\n\n1. Given a plan $P$ with $v$ villages and $r$ rivers, how many orientations of the rivers exist?\n\n2. Which are the plans $P$ that Olympe can receive such that $n_0(P)=n$ for:\n a) $n=0$?\n b) $n=1$?\n c) $n=2$?\n d) $n=4$?\n e) $n=6$?\n\n3. For which integers $$\begin{gathered} n \\ geqslant0 \end{gathered}$$ does there exist a plan $P$ such that $n_0(P)=n$?\n\nFor $$\begin{gathered} v \\ in \\ mathbb{N}^{\ast } \end{gathered}$$, we define different plans of $v$ villages: the cycle $C_v$, the grid $Q_v$ (only for $v$ even), the complete plan $K_v$, the star $E_v$ and the line $L_v$ (see figure 4).\n\n4. Compute $n_1(P)$ in the following cases:\n a) $P$ is the cycle $C_v$.\n b) $P$ is the grid $Q_v$.\n\n5. For which integers $$\begin{gathered} n \\ geqslant0 \end{gathered}$$ does there exist a plan $P$ such that $n_1(P)=n$?\n\n6. Compute $n_k(P)$ for all $$\begin{gathered} k \\ in \\ mathbbN \end{gathered}$$ in the following cases:\n a) $P$ is the complete plan $K_v$.\n b) $P$ is the star $E_v$.\n c) $P$ is the line $L_v$.\n\n7. Characterize the pairs of integers $(k,n)$ such that there exists a plan $P$ satisfying $n_k(P)=n$.\n\n8. Propose and study other lines of research.

Topic: Combinatoria Metodo: Grafi, Conteggio, Casework, Casi e conteggio Abilita: Conteggio sistematico, Modellizzazione, Astrazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Conteggiamento degli orientamenti dei fiumi tra villaggi con altitudini assegnate in modo che l’acqua scorra in discesa; funzioni n_k(P) sulle famiglie di grafici

La montagna dei ruscelli. Olympe è un apprendista di paesaggio. Le è stato affidato il compito di costruire una montagna, su cui installa villaggi. I fiumi collegano i villaggi a due a due, e supponiamo sempre che ci sia almeno un villaggio. L’Olympe vuole che ogni villaggio sia a un’altitudine diversa e assegna ai villaggi $v$ le altitudini $$\begin{gathered} 1 \\ textkm,2 \\ textkm, \\ dots,v \\ textkm \end{gathered}$$. Un orientamento dei fiumi è una scelta, per ogni fiume, della direzione del flusso. Per un determinato orientamento, un’altitudine assegnata ai villaggi è valida se per ogni fiume l’acqua scorre dal villaggio superiore al villaggio inferiore (basso). Per $$\begin{gathered} k \\ in \\ mathbbN \end{gathered}$$, $n_k(P)$ indica il numero di orientamenti dei fiumi di $P$ in modo tale che ci siano esattamente $k$ modi validi di assegnare le altitudini. Ad esempio, $n_0(P)$ è il numero di orientamenti per i quali non esiste un’assegnazione di altitudine valida.\n\n1. Dato un piano $P$ con villaggi $v$ e fiumi $r$, quanti orientamenti dei fiumi esistono?\n\n2. Quali sono i piani $P$ che Olympe può ricevere in modo tale che $n_0(P)=n$ per:\n a) $n=0$?\n b) $n=1$?\n c) $n=2$?\n d) $n=4$?\n e) $n=6$?\n\n3. Per quali integri $$\begin{gathered} n \\ geqslant0 \end{gathered}$$ esiste un piano $P$ tale che $n_0(P)=n$?\n\nPer $$\begin{gathered} v \\ in \\ mathbb{N}^{\ast } \end{gathered}$$, definiamo diversi piani dei villaggi $v$: il ciclo $C_v$, la griglia $Q_v$ (solo per $v$ pari), il piano completo $K_v$, la stella $E_v$ e la linea $L_v$ (vedi figura 4).\n\n4. Calcolare $n_1(P)$ nei seguenti casi:\n a) $P$ è il ciclo $C_v$.\n b) $P$ è la griglia $Q_v$.\n\n5. Per quali integri $$\begin{gathered} n \\ geqslant0 \end{gathered}$$ esiste un piano $P$ tale che $n_1(P)=n$?\n\n6. Calcolare $n_k(P)$ per tutti $$\begin{gathered} k \\ in \\ mathbbN \end{gathered}$$ nei seguenti casi:\n a) $P$ è il piano completo $K_v$.\n b) $P$ è la stella $E_v$.\n c) $P$ è la linea $L_v$.\n\n7. Caratterizzare le coppie di integri $(k,n)$ in modo tale che esista un piano $P$ soddisfacente $n_k(P)=n$.\n\n8. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q02

Monetary systems S: S-appoints (exact payments), S-primary prices, and S-decompositions; finiteness and uniqueness conditions

Monetary change (Appoint monétaire). In a galaxy far, far away, the little prince moves from planet to planet aboard his margarine spaceship. Each planet has its own monetary system $S$, a set of coin values, and the prince must give exact change for his purchases. We always assume $$\begin{gathered} 1 \\ inS \end{gathered}$$. For example, the monetary system $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$.\n\nWhen the prince arrives on a new planet with a certain amount of money $$\begin{gathered} x \\ in \\ mathbbN \end{gathered}$$, he converts it into the system $S$. We say he can give change (faire l’appoint) for a price $p$ on an amount $x$ if he can write $p$ as a sub-sum of the coins making up $x$. We denote by $mathcal{A}_S(x)$ the set of prices for which he can give change in the system $S$ having an amount $x$ of money. For example $$\begin{gathered} mathcal{A}_{ \\ 1,2,5 \\ }(4)= \\ 0,2,4 \end{gathered}$$ for one decomposition of $x=4$ into two coins of value 2; with $1+1+2$ instead he gets $0,1,2,3,4$.\n\n1. The little prince arrives on a planet where $$\begin{gathered} S= \\ 1,3,10 \end{gathered}$$. For which prices is he sure of giving change if:\n a) he has an amount $x=10$?\n b) he has an amount $x=100$?\n c) he has an amount $x=10^n$ for $$\begin{gathered} n \\ in \\ mathbb{N}^{\ast } \end{gathered}$$?\n\nThe daisy/margarine merchants charge a price $$\begin{gathered} p \\ geqslant1 \end{gathered}$$ such that one is sure of being able to give change for $p$ on any amount of money: such a price $p$ is called $S$-primary (by convention, $0$ is never $S$-primary). For example, for $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$, the price 6 is $S$-primary because $6=5+1=2+2+2$, whereas it is not for prices 1, 2, 3, 4 or 5. The set of $S$-primary prices is denoted $mathcal{P}_S$. For example $$\begin{gathered} 1,2,5,6 \\ in \\ mathcal{P}_{ \\ 1,2,5 \\ } \end{gathered}$$ but $$\begin{gathered} 0,3,4 \\ notin \\ mathcal{P}_{ \\ 1,2,5 \\ } \end{gathered}$$.\n\n2. Which sets $S$ are such that one can characterize the $S$-primary prices if:\n a) $$\begin{gathered} S= \\ 1,u \end{gathered}$$ for $$\begin{gathered} u \\ geqslant2 \end{gathered}$$?\n b) $$\begin{gathered} S=1+2 \\ mathbbN \end{gathered}$$ the set of odd numbers?\n c) $$\begin{gathered} S= \\ {2}^n,n \\ in \\ mathbbN \end{gathered}$$ the set of powers of 2?\n d) $$\begin{gathered} S= \\ 1,v,w \end{gathered}$$ for $w>v>2$?\n e) $S$ the set of prime numbers together with 1?\n\n3. Determine the subsets $S$ of $mathbb{N}^{\ast }$ such that $mathcal{P}_S$ is finite.\n\n4. Give an estimate (frame from below and above) of the value of the largest $S$-primary price when $S$ is finite, as a function of the values of the elements of $S$. One may begin by treating cases (a) and (d) of question 2.\n\n5. Find necessary and/or sufficient conditions for $$\begin{gathered} mathcal{P}_S= \\ mathbb{N}^{\ast } \end{gathered}$$.\n\nGiven a price $x$, an $m$-tuple $$\begin{gathered} (p_1, \\ dots,p_m) \end{gathered}$$ of $S$-primary prices whose sum is $x$ is called an $S$-decomposition of $x$ if for every subset $$\begin{gathered} J \\ subseteq[ \\ ![1,m] \\ !] \end{gathered}$$, the price $$\begin{gathered} x_J= \\ su{m}_{j \\ inJ}{p}_j \end{gathered}$$ is an $S$-appoint of $x$; in other words, every sub-sum (including the empty sum and the full sum) of these prices is an $S$-appoint of $x$. For example, for $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$ and $x=4$, the unique $S$-decomposition of $x$ is the triplet $(1,1,2)$ but not the pair $(2,2)$, because $1+2=3$ is not an $S$-appoint of 4. Likewise, $(4)$ is not an $S$-decomposition of 4 because 4 is not $S$-primary.\n\n6. For which systems $S$ does every $x$ admit at least one $S$-decomposition?\n\n7. Do there exist systems $S$ for which:\n a) $S$ is finite and every $S$-decomposition is unique (up to permutation of the $S$-primary numbers)?\n b) $S$ is infinite and every $S$-decomposition is unique?\n c) $S$ is of the form $$\begin{gathered} S= \\ 1,u,v \end{gathered}$$ with $1<u<v$ and every $S$-decomposition is unique?\n d) at least one price $x$ admits at least two $S$-decompositions that are not permutations of one another?\n\n8. Find necessary and/or sufficient conditions for a system $S$ to verify the property of the preceding question.\n\n9. Propose and study other lines of research.

Topic: Teoria dei Numeri, Combinatoria, Insiemi e funzioni Metodo: Conteggio, Casework, Fattorizzazione Abilita: Lettura attenta, Casework accurato, Astrazione Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Sistemi monetari S: punti S (pagamenti esatti), prezzi primari S e decomposizioni S; condizioni di finità e unicità

Valutazione monetaria (Appoint monétaire). In una galassia lontana, lontana, il piccolo principe si sposta da pianeta in pianeta a bordo della sua nave spaziale margarina. Ogni pianeta ha il suo sistema monetario, un insieme di valori delle monete, e il principe deve dare il cambio esatto per i suoi acquisti. Supponiamo sempre $$\begin{gathered} 1 \\ inS \end{gathered}$$. Per esempio, il sistema monetario $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$.\n\nQuando il principe arriva su un nuovo pianeta con una certa quantità di denaro $$\begin{gathered} x \\ in \\ mathbbN \end{gathered}$$, lo converte nel sistema $S$. Diciamo che può dare cambio (faire l’appoint) per un prezzo $p$ su un importo $x$ se può scrivere $p$ come sottosumma delle monete che costituiscono $x$. Indichiamo con $mathcal{A}_S(x)$ l’insieme dei prezzi per i quali può dare variazione nel sistema $S$ avendo un importo $x$ di denaro. Ad esempio $$\begin{gathered} mathcal{A}_{ \\ 1,2,5 \\ }(4)= \\ 0,2,4 \end{gathered}$$ per una decomposizione di $x=4$ in due monete di valore 2; con $1+1+2$ invece ottiene $0,1,2,3,4$.\n\n1. Il piccolo principe arriva su un pianeta dove $$\begin{gathered} S= \\ 1,3,10 \end{gathered}$$. Per quali prezzi è sicuro di dare cambio se: a) ha un importo $x=10$? b) ha un importo $x=100$? c) ha un importo $x=10^n$ per $$\begin{gathered} n \\ in \\ mathbb{N}^{\ast } \end{gathered}$$? n\nI commercianti di margherite/margherine addebitano un prezzo $$\begin{gathered} p \\ geqslant1 \end{gathered}$$ tale da essere sicuri di poter dare cambio per $p$ su qualsiasi importo di denaro: tale prezzo $p$ si chiama $S$-primario (per convenzione, $0$ non è mai $S$-primario). Per esempio, per $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$, il prezzo 6 è $S$-primario perché $6=5+1=2+2+2$, mentre non è per i prezzi 1, 2, 3, 4 o 5. L’insieme dei prezzi primari $S$ è indicato come $mathcal{P}_S$. Per esempio $$\begin{gathered} 1,2,5,6 \\ in \\ mathcal{P}_{ \\ 1,2,5 \\ } \end{gathered}$$ ma $$\begin{gathered} 0,3,4 \\ notin \\ mathcal{P}_{ \\ 1,2,5 \\ } \end{gathered}$$.\n\n2. Quali set $S$ sono tali da poter caratterizzare i prezzi primari $S$ se:\n a) $$\begin{gathered} S= \\ 1,u \end{gathered}$$ per $$\begin{gathered} u \\ geqslant2 \end{gathered}$$?\n b) $$\begin{gathered} S=1+2 \\ mathbbN \end{gathered}$$ l’insieme di numeri unici?\n c) $$\begin{gathered} S= \\ {2}^n,n \\ in \\ mathbbN \end{gathered}$$ l’insieme di potenze di 2?\n d) $$\begin{gathered} S= \\ 1,v,w \end{gathered}$$ per $w>v>2$?\n e) $S$ l’insieme di numeri primi insieme a 1?\n\n3. Determinare i sottogruppi $S$ di $mathbb{N}^{\ast }$ in modo tale che $mathcal{P}_S$ sia finito.\n\n4. Indicare una stima (frame da sotto e sopra) del valore del prezzo primario più grande $S$ quando $S$ è finito, in funzione dei valori degli elementi di $S$. Si può iniziare trattando i casi (a) e (d) della domanda 2.\n\n5. Trovare condizioni necessarie e/o sufficienti per $$\begin{gathered} mathcal{P}_S= \\ mathbb{N}^{\ast } \end{gathered}$$.\n\nDato un prezzo $x$, un $m$-tuple $$\begin{gathered} (p_1, \\ dots,p_m) \end{gathered}$$ di $S$-prezzi primari la cui somma è $x$ si chiama $S$-decompilazione di $x$ se per ogni sottoinsieme $$\begin{gathered} J \\ subseteq[ \\ ![1,m] \\ !] \end{gathered}$$, il prezzo $$\begin{gathered} x_J= \\ su{m}_{j \\ inJ}{p}_j \end{gathered}$$ è un $S$-appoint di $x$; in altre parole, ogni sottosomma (compresa la somma vuota e la somma completa) di questi prezzi è un $S$-appoint di $x$. Per esempio, per $$\begin{gathered} S= \\ 1,2,5 \end{gathered}$$ e $x=4$, la decomposizione unica $S$ di $x$ è la tripletta $(1,1,2)$, ma non la coppia $(2,2)$, perché $1+2=3$ non è un $S$-appoint di 4. Allo stesso modo, $(4)$ non è una decomposizione $S$ di 4 perché 4 non è $S$-primaria.\n\n6. Per quali sistemi $S$ ogni $x$ ammette almeno una decomposizione $S$?\n\n7. Esistono sistemi $S$ per i quali:\n a) $S$ è finito e ogni $S$-decomposizione è unica (fino alla permutazione dei numeri primari $S$)?\n b) $S$ è infinito e ogni $S$-decomposizione è unica?\n c) $S$ ha la forma $$\begin{gathered} S= \\ 1,u,v \end{gathered}$$ con $1<u<v$ e ogni $S$-decomposizione è unica?\n d) almeno un prezzo $x$ ammette almeno due $S$-decomposizioni che non sono permutazioni l’una dell’altra?\n\n8. Trovare le condizioni necessarie e/o sufficienti per un sistema $S$ per verificare la proprietà della domanda precedente.\n\n9. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q03

Resolution-change operation on a strip of n notes producing m notes/silences; reachability and minimal operations, then 2D image version

Distorted music (Musique déformée). Perrine plays with an audio montage software. She arranges an initial strip of one minute holding $n$ distinct notes placed end to end, each of duration $1/n$. The software offers a feature to change the resolution of the strip. Perrine chooses a new resolution $$\begin{gathered} m \\ geqslant1 \end{gathered}$$, and the software creates a new strip of one minute holding $m$ notes chosen as follows: for each $k$ with $$\begin{gathered} 1 \\ leqslantk \\ leqslantm \end{gathered}$$, the software looks at the instant $k/m$ on the old strip. If this instant falls strictly inside an old note, it copies that note into the new strip; if it falls exactly between two notes (where one note ends and the next begins), it puts a silence in the new strip. If the instant falls inside an old silence, the new note is a silence too.\n\nFigure 5 shows a resolution change passing from $n=4$ to $m=7$. Each cell represents one note; colors represent different notes; white corresponds to a silence.\n\nPerrine is interested in the strips obtained after several successive transformations of this kind.\n\n1. For each of the following events, say whether it can or cannot happen after a finite number of operations:\n a) A note disappears from the strip.\n b) Two notes that were distinct become the same.\n c) A silence appears.\n d) A silence disappears.\n e) The notes are no longer all the same.\n f) The strip no longer contains any silence.\n\n2. For each of the cases of the preceding question, what is the minimal number of operations that produce that result, as a function of $n$?\n\n3. Choose $$\begin{gathered} 1 \\ leqslantk \\ leqslantn \end{gathered}$$. Redo questions 1 and 2 if Perrine forbids herself from creating a strip of length strictly less than $k$, that is, with strictly fewer than $k$ notes (not necessarily distinct).\n\n4. The software can now work only with strips whose length is odd.\n a) Is it possible for a silence to appear?\n b) Starting from a strip of length 1, Perrine performs a sequence of operations to go from a strip of length 1 to a strip of length 1. Is it possible that the initial strip and the final strip be different?\n c) Starting from $n$ notes, Perrine performs a sequence of operations keeping the number of notes never below $n$ and returning to a strip of $n$ notes. How many different notes can the final strip hold? More generally, which are the possible final strips?\n\n5. Redo question 4 restricting oneself to odd lengths.\n\nPerrine now manipulates not strips but images. Her image is 1 metre by 1 metre, made of $$\begin{gathered} n \\ times{n}^{\prime } \end{gathered}$$ rectangles of size $$\begin{gathered} 1/n \\ times1/n^{\prime } \end{gathered}$$ of different colors. The software can transform an image of $$\begin{gathered} n \\ times{n}^{\prime } \end{gathered}$$ rectangles into one of $$\begin{gathered} m \\ times{m}^{\prime } \end{gathered}$$ rectangles of size $$\begin{gathered} 1/m \\ times1/m^{\prime } \end{gathered}$$ as follows: for each $$\begin{gathered} 1 \\ leqslantk \\ leqslantm \end{gathered}$$ and $$\begin{gathered} 1 \\ leqslant{k}^{\prime } \\ leqslant{m}^{\prime } \end{gathered}$$, the software looks at the center of the new rectangle $(k,k^{\prime })$. If this point falls inside a rectangle of the old image, it copies that color into the new rectangle. If the point falls exactly between two rectangles of the old image, the new rectangle becomes black.\n\n6. Redo all the preceding questions in this framework.\n\n7. Propose and study other lines of research.

Topic: Combinatoria, Insiemi e funzioni Metodo: Casework, Invarianti, Conteggio Abilita: Lettura attenta, Riconoscimento di pattern, Modellizzazione Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

operazione di variazione della risoluzione su una striscia di n note che produce m note/silenzi; operazione di accessibilità e minima, quindi versione di immagine 2D

Musica distorta (Musique déformée). Perrine gioca con un software audio. Si dispone di una striscia iniziale di un minuto contenente $n$ note distinte poste da capo a capo, ciascuna di durata $1/n$. Il software offre una funzione per modificare la risoluzione della striscia. Perrine sceglie una nuova risoluzione $$\begin{gathered} m \\ geqslant1 \end{gathered}$$ e il software crea una nuova striscia di un minuto contenente le note $m$ scelte come segue: per ogni $k$ con $$\begin{gathered} 1 \\ leqslantk \\ leqslantm \end{gathered}$$, il software guarda l’istante $k/m$ sulla vecchia striscia. Se questo istante cade strettamente all’interno di una nota vecchia, copia quella nota nella nuova striscia; se cade esattamente tra due note (dove una nota termina e la prossima inizia), mette un silenzio nella nuova striscia. Se l’istante cade dentro un vecchio silenzio, la nuova nota è anche un silenzio.\n\nLa figura 5 mostra un cambiamento di risoluzione passando da $n=4$ a $m=7$. Ogni cella rappresenta una nota; i colori rappresentano note diverse; il bianco corrisponde a un silenzio. Perrine è interessato alle strisce ottenute dopo diverse successive trasformazioni di questo tipo. Per ciascuno dei seguenti eventi, dire se può o non può accadere dopo un numero finito di operazioni:\n a) Una nota scompare dalla striscia.\n b) Due note che erano distinte diventano le stesse.\n c) Un silenzio appare.\n d) Un silenzio scompare.\n e) Le note non sono più tutte le stesse.\n f) La striscia non contiene più alcun silenzio.\n\n2. Per ciascuno dei casi della domanda precedente, qual è il numero minimo di operazioni che producono tale risultato, come funzione di $n$?\n\n3. Selezionare $$\begin{gathered} 1 \\ leqslantk \\ leqslantn \end{gathered}$$. Redo le domande 1 e 2 se Perrine si proibisce di creare una striscia di lunghezza strettamente inferiore a $k$, cioè con note strettamente inferiori a $k$ (non necessariamente distinte). Il software può ora lavorare solo con strisce la cui lunghezza è strana.\n a) È possibile che si verifichi un silenzio?\n b) Partendo da una striscia di lunghezza 1, Perrine esegue una sequenza di operazioni per passare da una striscia di lunghezza 1 a una striscia di lunghezza 1. È possibile che la striscia iniziale e la striscia finale siano diverse?\n c) Partendo dalle note $n$, Perrine esegue una sequenza di operazioni mantenendo il numero di note mai inferiore a $n$ e tornando a una striscia di note $n$. Quante note diverse può contenere la striscia finale? Più in generale, quali sono le possibili strisce finali? Redo domanda 4 limitarsi a lunghezze strane. Perrine ora non manipola strisce ma immagini. La sua immagine è di 1 metro su 1 metro, fatta di rettangoli $$\begin{gathered} n \\ times{n}^{\prime } \end{gathered}$$ di dimensioni $$\begin{gathered} 1/n \\ times1/n^{\prime } \end{gathered}$$ di diversi colori. Il software può trasformare un’immagine dei rettangoli $$\begin{gathered} n \\ times{n}^{\prime } \end{gathered}$$ in uno dei rettangoli $$\begin{gathered} m \\ times{m}^{\prime } \end{gathered}$$ di dimensioni $$\begin{gathered} 1/m \\ times1/m^{\prime } \end{gathered}$$ come segue: per ogni $$\begin{gathered} 1 \\ leqslantk \\ leqslantm \end{gathered}$$ e $$\begin{gathered} 1 \\ leqslant{k}^{\prime } \\ leqslant{m}^{\prime } \end{gathered}$$, il software guarda al centro del nuovo rettangolo $(k,k^{\prime })$. Se questo punto cade all’interno di un rettangolo della vecchia immagine, copia quel colore nel nuovo rettangolo. Se il punto cade esattamente tra due rettangoli della vecchia immagine, il nuovo rettangolo diventa nero. Riprendi tutte le domande precedenti in questo quadro. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q04

Sets of points/polygons with all integer-degree angles; maxima under convexity, concyclicity, collinearity, and two-line constraints

Integer angles (Angles entiers). To pass the time, Emmanuel amuses himself drawing geometric figures. But when he draws arbitrary figures, he cannot always measure the angles with a protractor. It is annoying when he reports an angle that is not an integer number of degrees, that is, not in \\{0^\\circ, 1^\\circ, \\dots, 360^\\circ\\}. He says that a set of points of the plane has integer angles (aux angles entiers) if for any three distinct points of the set, whether aligned or not, the triangle they form (possibly flattened) has three integer angles.\n\n1. For which $$\begin{gathered} n \\ geqslant3 \end{gathered}$$ does the regular $n$-gon have integer angles?\n\nA polygon is said convex if its interior angles measure strictly between 0^\\circ and 180^\\circ.\n\n2. What is the maximal $n$ such that there exists a convex $n$-gon with integer angles? And imposing that the polygon be not regular?\n\n3. Redo the preceding question imposing this:\n a) Four points are never on the same circle.\n b) Four points are never simultaneously on the same circle.\n\n4. We now impose that the points form a convex polygon. What is the maximal number of points forming a set with integer angles? Same question imposing at the same time that no three points are aligned and that no more than three points are on the same circle.\n\n5. Emmanuel now traces two distinct parallel lines and imposes that each point be on one of the two lines. What is the maximal number of points forming a set with integer angles under this constraint? Same question imposing moreover that there be just as many points on each line.\n\n6. Emmanuel now traces two lines forming an integer angle $theta$ instead of two parallel lines. Redo the preceding question as a function of $theta$.\n\n7. Redo the previous question if Emmanuel’s protractor is not graduated in degrees but in grades (a full turn being $400$ grades).\n\n8. Propose and study other lines of research.

Topic: Geometria piana, Trigonometria, Combinatoria Metodo: Casework, Trigonometria, Estremalità Abilita: Ragionamento geometrico, Casework accurato, Riconoscimento di pattern Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

insiemi di punti/poligoni con tutti gli angoli di gradi interi; massimi sotto convexità, conciclicità, collinearità e restrizioni a due linee

Angoli interi (angoli integrali). Per passare il tempo, Emmanuel si diverte disegnando figure geometriche. Ma quando disegna cifre arbitrarie, non può sempre misurare gli angoli con un prolungatore. È fastidioso quando segnala un angolo che non è un numero intero di gradi, cioè non in \\{0^\\circ, 1^\\circ, \\dots, 360^\\circ\\}. Dice che un insieme di punti del piano ha angoli interi (aux angles entiers) se per qualsiasi tre punti distinti del set, sia allineati che no, il triangolo che formano (possibilmente appiattito) ha tre angoli interi.\n\n1. Per quale $$\begin{gathered} n \\ geqslant3 \end{gathered}$$ il normale $n$-gon ha angoli interi?\n\nUn poligono è detto convexo se i suoi angoli interni misurano rigorosamente tra 0^\\circ e 180^\\circ.\n\n2. Qual è il massimo $n$ tale che esista un convex $n$-gon con angoli interi? E impone che il poligono non sia regolare? Riprendi la domanda precedente che impone questo:\n a) Quattro punti non sono mai sullo stesso cerchio.\n b) Quattro punti non sono mai contemporaneamente sullo stesso cerchio.\n\n4. Ora imponiamo che i punti formino un poligono convex. Qual è il numero massimo di punti che formano un insieme con angoli interi? La stessa domanda impone allo stesso tempo che non ci sono tre punti allineati e che non più di tre punti sono sullo stesso cerchio. Emmanuel traccia ora due linee parallele distinte e impone che ogni punto sia su una delle due linee. Qual è il numero massimo di punti che formano un insieme con angoli interi sotto questo vincolo? La stessa domanda che impone inoltre che ci siano uguali punti su ogni linea. Emmanuel traccia ora due linee che formano un angolo intero $theta$ invece di due linee parallele. Riprendi la domanda precedente come funzione di $theta$.\n\n7. Riprendi la domanda precedente se il prolungatore di Emmanuel non è graduato in gradi ma in gradi (un giro completo è $400$ gradi).\n\n8. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q05

Hierarchies as oriented social-bond graphs; emeutes (riots) that flip and add bonds; stability, reachability, revolutions on complete/coherent/arbitrary tribes

Hierarchical tribes (Tribus hiérarchiques). On an archipelago far from everyone, the tribes each have a well-established social order. Two individuals are linked socially if one is socially superior to the other. A hierarchy is a set of links going from each individual to others. For two individuals $A$ and $B$, we write $$\begin{gathered} A \\ toB \end{gathered}$$ if $A$ is socially (hierarchically) superior to $B$. We assume there are at least 2 persons. Hierarchical superiority is not transitive: if $$\begin{gathered} A \\ toB \end{gathered}$$ and $$\begin{gathered} B \\ toC \end{gathered}$$, then not necessarily $$\begin{gathered} A \\ toC \end{gathered}$$.\n\nOn Tournoasis Isle a tribe organizes itself in a complete hierarchy: for any pair of individuals $A$ and $B$, one has either $$\begin{gathered} A \\ toB \end{gathered}$$ or $$\begin{gathered} B \\ toA \end{gathered}$$.\n\nTwo discontented persons can declare an émeute (riot). An émeute triggered by $$\begin{gathered} A \\ toB \end{gathered}$$ transforms the hierarchy in three steps:\n a) For every social link $$\begin{gathered} C \\ toA \end{gathered}$$ and $$\begin{gathered} B \\ toD \end{gathered}$$ with $C$ and $D$ different, one adds a social link $$\begin{gathered} C \\ toD \end{gathered}$$ (at this stage one may have several social links between two persons).\n b) One reverses the link $$\begin{gathered} A \\ toB \end{gathered}$$ into $$\begin{gathered} B \\ toA \end{gathered}$$.\n c) If, between two persons $X$ and $Y$, there are several social links, one replaces them by the majority social link, or by a single social link in case of a tie. Thus $$\begin{gathered} X \\ rightrightarrowsY \end{gathered}$$ becomes $$\begin{gathered} X \\ toY \end{gathered}$$, and a tie $$\begin{gathered} X \\ rightrightarrowsY \end{gathered}$$ leaves $X$ and $Y$ unlinked.\n\nAs the hierarchy must stay complete on Tournoasis, if the final result would leave a pair of persons with no social link, then the émeute cannot take place.\n\nFigure 7 shows three examples of émeutes between $A$ and $B$. The initial situation is on the left and the final result on the right. On Tournoasis, the émeute between $C$ and $D$ in the right-hand example cannot take place.\n\n1. Do there exist stable hierarchies, in which no émeute can break out? If so, for which numbers of individuals?\n\nFor two hierarchies $H_1$ and $H_2$, we write $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$ if there is a finite sequence of émeutes transforming $H_1$ into $H_2$.\n\n2. Is it true that if $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$, then also $$\begin{gathered} H_2 \\ to{H}_1 \end{gathered}$$?\n\nA révolution is a sequence of émeutes such that the final result has reversed all the arrows.\n\n3. Characterize the hierarchies for which a révolution is possible.\n\n4. For which complete hierarchies $H_1$ and $H_2$ does there exist a sequence of émeutes bringing $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$? If not always, give necessary and sufficient conditions to have $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$.\n\nOn the neighboring isle, Courtoasis, lives a similar tribe. There, hierarchies are not necessarily complete, but they must be coherent, meaning there are no individuals $$\begin{gathered} A_1,A_2, \\ dots,A_n \end{gathered}$$ ($n>1$) with $$\begin{gathered} A_1 \\ to{A}_2 \\ to \\ dots \\ to{A}_n \\ to{A}_1 \end{gathered}$$. If an émeute would make the hierarchy non-coherent, then it cannot take place.\n\n5. Redo the preceding questions in this framework.\n\nOn a third isle, Carquoisis, lives a tribe with a less strict hierarchy, not necessarily complete nor coherent. An émeute can therefore always take place.\n\n6. Redo questions 2, 3 and 4 in this framework.\n\n7. Propose and study other lines of research.

Topic: Combinatoria, Logica Metodo: Grafi, Invarianti, Casework Abilita: Astrazione, Casework accurato, Modellizzazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Ierarchie come grafici di legami sociali orientati; emeute (rivolti) che girano e aggiungono legami; stabilità, accessibilità, rivoluzioni sulle tribù complete/coerenti/arbitrali

Tribù gerarchici (Tribus hierarchiques). In un arcipelago lontano da tutti, le tribù hanno un ordine sociale ben consolidato. Due individui sono collegati socialmente se uno è socialmente superiore all’altro. Una gerarchia è un insieme di collegamenti che vanno da un individuo all’altro. Per due individui $A$ e $B$, scriviamo $$\begin{gathered} A \\ toB \end{gathered}$$ se $A$ è socialmente (ierarchicamente) superiore a $B$. Supponiamo che ci siano almeno due persone. La superiorità gerarchica non è transitiva: se $$\begin{gathered} A \\ toB \end{gathered}$$ e $$\begin{gathered} B \\ toC \end{gathered}$$, allora non necessariamente $$\begin{gathered} A \\ toC \end{gathered}$$.\n\nSulla Tournoasis Isle una tribù si organizza in una completa gerarchia: per qualsiasi coppia di individui $A$ e $B$, si ha o $$\begin{gathered} A \\ toB \end{gathered}$$ o $$\begin{gathered} B \\ toA \end{gathered}$$.\n\nDue persone insoddisfatte possono dichiarare un émeute (rivolto). Una rivolta provocata da $$\begin{gathered} A \\ toB \end{gathered}$$ trasforma la gerarchia in tre fasi:\n a) Per ogni collegamento sociale $$\begin{gathered} C \\ toA \end{gathered}$$ e $$\begin{gathered} B \\ toD \end{gathered}$$ con $C$ e $D$ diversi, si aggiunge un collegamento sociale $$\begin{gathered} C \\ toD \end{gathered}$$ (in questa fase si possono avere più collegamenti sociali tra due persone).\n b) Si inverte il collegamento $$\begin{gathered} A \\ toB \end{gathered}$$ in $$\begin{gathered} B \\ toA \end{gathered}$$.\n c) Se, tra due persone $X$ e $Y$, ci sono più collegamenti sociali, si sostituiscono con il collegamento sociale di maggioranza, o con un singolo collegamento sociale in caso di legame. Così $$\begin{gathered} X \\ rightrightarrowsY \end{gathered}$$ diventa $$\begin{gathered} X \\ toY \end{gathered}$$, e un tie $$\begin{gathered} X \\ rightrightarrowsY \end{gathered}$$ lascia $X$ e $Y$ non collegati.\n\nCome la gerarchia deve rimanere completa su Tournoasis, se il risultato finale lascia una coppia di persone senza legame sociale, allora l’émeute non può avvenire.\n\nLa figura 7 mostra tre esempi di émeutes tra $A$ e $B$. La situazione iniziale è a sinistra e il risultato finale a destra. Su Tournoasis, non può avvenire l’emeute tra $C$ e $D$ nell’esempio di destra.\n\n1. Esistono gerarchie stabili, in cui non può scoppiare alcuna rivolta? In tal caso, per quali numeri di individui?\n\nPer due gerarchie $H_1$ e $H_2$, scriviamo $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$ se c’è una sequenza finita di émeutes che trasforma $H_1$ in $H_2$.\n\n2. E’ vero che se $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$, allora anche $$\begin{gathered} H_2 \\ to{H}_1 \end{gathered}$$?\n\nUna rivoluzione è una sequenza di émeutes tale che il risultato finale ha invertito tutte le frecce.\n\n3. Caratterizzare le gerarchie per le quali una rivoluzione è possibile. Per quali gerarchie complesse $H_1$ e $H_2$ esiste una sequenza di émeutes che porta $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$? Se non sempre, dare le condizioni necessarie e sufficienti per avere $$\begin{gathered} H_1 \\ to{H}_2 \end{gathered}$$.\n\nNella vicina isola, Courtoasis, vive una tribù simile. Qui, le gerarchie non sono necessariamente complete, ma devono essere coerenti, il che significa che non ci sono individui $$\begin{gathered} A_1,A_2, \\ dots,A_n \end{gathered}$$ ($n>1$) con $$\begin{gathered} A_1 \\ to{A}_2 \\ to \\ dots \\ to{A}_n \\ to{A}_1 \end{gathered}$$. Se una rivolta rendesse la gerarchia non coerente, allora non può avvenire. Rendiamo le domande precedenti in questo quadro. In una terza isola, Carquoisis, vive una tribù con una gerarchia meno rigorosa, non necessariamente completa né coerente. Una rivolta può quindi avvenire sempre. Redo le domande 2, 3 e 4 in questo quadro. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q06

Laser reflecting inside an equilateral (then right-isosceles, then general) triangle with mirrored sides and open vertices; counting rebounds n(t)

Mirrors and lasers (Miroirs et lasers). Clémence has an equilateral triangle $ABC$ arranged so that there are mirrors on the three sides and so that the laser can exit only through the vertices (which are infinitely small holes). She amuses herself firing a laser ray that, from a certain point, reflects off the sides of the triangle following the rules of classical mechanics: the angle the ray makes with the normal to the mirror equals the angle between the incoming ray and the outgoing ray (see Figure 8). If the ray hits a vertex it is imprisoned forever.\n\nFor a shot $t$ of the laser ray that Clémence fires, we denote by $$\begin{gathered} n(t) \\ in \\ mathbbN \\ cup \\ infty \end{gathered}$$ the number of times the ray reflects off the mirrors before coming back out.\n\n1. Clémence tries to understand the set of values that $n(t)$ can take.\n a) Which are the values $n(t)$ can take? One may study the smallest possible values of $n(t)$: can one have $n(t)=1,2,3,4$ or 5? Do there exist shots $t$ with $$\begin{gathered} n(t)= \\ infty \end{gathered}$$, i.e. the laser ray never leaves the triangle $ABC$?\n b) Let $n$ be an integer. Find how many distinct shots $t$ verify $n(t)=n$.\n\n2. Suppose now there is no longer a shot that can pass through the vertices $B$ and $C$, in order to avoid the problems with rebounds. Redo question 1 in this framework.\n\n3. Clémence decides to fire two simultaneous distinct shots from the vertex $A$, assuming these two rays travel at the same constant speed of light. So the two rays exit at the same place at a certain instant $s>0$ (that is, after having travelled the same distance). Does there necessarily exist an instant $s^{\prime }>$ such that the rays exit again at the same place? Same question if the shots start from two different vertices $A$ and $B$.\n\n4. Is it possible for a laser ray starting from a point $A$ to pass through all points of the triangle (including the interior) except the points $B$ and $C$? In a new version of this question, suppose the laser ray is thick (épais), still starting from point $A$ but with an angular width $alpha>0$; redo the previous question under this hypothesis.\n\n5. Redo questions 1, 2 and 3 in the case where $ABC$ is a right isosceles triangle (there are two cases to handle, either the segment $BC$ is the hypotenuse or it is not).\n\n6. Clémence now considers much more general triangles. She denotes by $n_{ABC}(t)$ the number of rebounds of a shot $t$ in an arbitrary triangle $ABC$ where only the vertex $A$ is open.\n a) Which are the possible values for $n_{ABC}(t)$ when $ABC$ and $t$ are free?\n b) Do there exist triangles for which $n_{ABC}(t)$ can only take the value $infty$ whatever the shot $t$? If so, characterize them as much as possible.\n c) Let $mathcalS$ be the set of values that $n_{ABC}(t)$ can take in the preceding question. Does there exist a triangle $XYZ$ such that the values of $n_{XYZ}(t)$ describe exactly $mathcalS$ as $t$ runs over all possible shots?\n d) Redo questions 1 and 2 for these triangles.\n\n7. Redo questions 1, 2, 3 and 6 in the case of the square and of the regular hexagon, then of arbitrary regular polygons.\n\n8. Propose and study other lines of research.

Topic: Geometria piana, Trigonometria Metodo: Simmetria, Trigonometria, Casework Abilita: Ragionamento geometrico, Astrazione, Riconoscimento di pattern Area: Geometria Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

*Laser riflesso all’interno di un triangolo equilaterale (poi a destra, poi a fianco e a fianco) con lati specchiati e vertici aperti; conteggio dei rimbalzi n(t) *

Specchi e laser (Specchi e laser). Clémence ha un triangolo equilaterale $ABC$ disposto in modo che ci siano specchi sui tre lati e in modo che il laser possa uscire solo attraverso i vertici (che sono buchi infinitamente piccoli). Si diverte a sparare un raggio laser che, da un certo punto, riflette dai lati del triangolo seguendo le regole della meccanica classica: l’angolo che il raggio fa con il normale allo specchio è uguale all’angolo tra il raggio in entrata e il raggio in uscita (vedi Figura 8). Se il raggio colpisce un vertice, viene imprigionato per sempre. Per un tiro $t$ del raggio laser che Clémence scatta, indichiamo con $$\begin{gathered} n(t) \\ in \\ mathbbN \\ cup \\ infty \end{gathered}$$ il numero di volte che il raggio si riflette dagli specchi prima di tornare fuori. Clémence cerca di comprendere l’insieme dei valori che $n(t)$ può assumere.\n a) Quali sono i valori che $n(t)$ può assumere? Si possono studiare i valori più piccoli possibili di $n(t)$: si può avere $n(t)=1,2,3,4$ o 5? Esistono scatti $t$ con $$\begin{gathered} n(t)= \\ infty \end{gathered}$$, cioè il raggio laser non lascia mai il triangolo $ABC$?\n b) Let $n$ essere un numero intero. Trova quanti scatti distinti $t$ verificano $n(t)=n$.\n\n2. Supponiamo ora che non ci sia più un colpo che possa passare attraverso i vertici $B$ e $C$, al fine di evitare i problemi con i rimbalzi. Riprendiamo la domanda 1 in questo quadro. Clémence decide di sparare due colpi simultanei distinte dal vertice $A$, supponendo che questi due raggi viaggiino alla stessa velocità costante della luce. Quindi i due raggi usciranno nello stesso luogo in un certo istante $s>0$ (cioè dopo aver percorso la stessa distanza). C’è necessariamente un istante $s^{\prime }>$ tale che i raggi uscino di nuovo nello stesso luogo? La stessa domanda se le riprese partono da due vertici diversi $A$ e $B$.\n\n4. È possibile che un raggio laser partendo da un punto $A$ passi attraverso tutti i punti del triangolo (compreso l’interno) tranne i punti $B$ e $C$? In una nuova versione di questa domanda, supponiamo che il raggio laser sia spessore (spessore), ancora partendo dal punto $A$ ma con una larghezza angolare $alpha>0$; rifacciamo la domanda precedente in base a questa ipotesi.\n\n5. Redo le domande 1, 2 e 3 nel caso in cui $ABC$ è un triangolo a piega retta (ci sono due casi da gestire, o il segmento $BC$ è l’ipotenusa o non lo è).\n\n6. Clémence considera ora i triangoli molto più generali. Indica con $n_{ABC}(t)$ il numero di rimbalzi di un colpo $t$ in un triangolo arbitrario $ABC$ dove solo il vertice $A$ è aperto.\n a) Quali sono i valori possibili per $n_{ABC}(t)$ quando $ABC$ e $t$ sono liberi?\n b) Esistono triangoli per i quali $n_{ABC}(t)$ può prendere solo il valore $infty$ qualunque sia il colpo $t$? In tal caso, caratterizzare il più possibile.\n c) Let $mathcalS$ essere l’insieme di valori che $n_{ABC}(t)$ può prendere nella domanda precedente. Esiste un triangolo $XYZ$ tale che i valori di $n_{XYZ}(t)$ descrivano esattamente $mathcalS$ come $t$ corre su tutti i possibili scatti?\n d) Redo domande 1 e 2 per questi triangoli.\n\n7. Redo le domande 1, 2, 3 e 6 nel caso del quadrato e dell’esagono regolare, quindi di poligoni regolari arbitrari. Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q07

Card-deck shuffles as permutations; finding the shuffle sigma in minimum games, and realizable objectives (target partitions) per shuffle

Deck seed (Graine de deck). Nicolas plays a deck-construction card game and seeks the perfect deck, ready to start over many times. Let $$\begin{gathered} k,n \\ in \\ mathbb{N}^{\ast } \end{gathered}$$ with $k$ dividing $n$ and $$\begin{gathered} k \\ geqslant2 \end{gathered}$$. Nicolas’s deck holds $n$ cards in total, each bearing a symbol, with possibly identical cards. There are in the deck several types of cards distinguished by their symbol; some cards may be identical (in which case the shuffle does not change anything since the cards have the same appearance).\n\nAt the start of the game Nicolas knows the composition of his deck but not the shuffle. He must give an initial order to his deck, which he may do as he wishes. The shuffle of the deck is a permutation $sigma$ which, applied to the initial order of the cards, gives a new order; it is the shuffle. Then, at the start of each game $P_i$, the deck whose order is $sigma$ applied to the initial order is drawn, cards being played $k$ by $k$ (so a game has $n/k$ turns). When the deck has cards in $n/k$ copies, two identical cards cannot be distinguished after the shuffle.\n\nFor example, with $n=6$ cards, 3 cards $A$ and 3 cards $B$ initially in order $(A,B,A,B,A,B)$, where cards are played $k=3$ by 3 (so a game has $n/k=2$ turns) and where the shuffle is $$\begin{gathered} sigma= \\ beginpmatrix123456 \\ 152346 \\ endpmatrix \end{gathered}$$, the objects $(ABABAB,AAABBB)$ or $(ABABAB,AAB,ABB)$ are realizable for the shuffle $sigma$ (see question 3). The second choice lets one distinguish $sigma$ from $$\begin{gathered} beginpmatrix123456 \\ 153246 \\ endpmatrix \end{gathered}$$ but the first does not (because the final state of the deck is the same).\n\n1. In this question, Nicolas’s goal is to find the shuffle $sigma$ as fast as possible. The initial order, before a game starts, is always the same. How many games does he need at minimum when:\n a) $k=n$, and all the cards are different?\n b) $k=n$, and the deck consists of 2 different cards, one unique and the other in $n-1$ copies?\n c) $k=n$, and the deck consists of 2 different cards, each in $n/2$ copies?\n d) $k=2$, and the deck consists of 2 different cards, each in $n/2$ copies, and the initial order is a perfect alternation of these cards?\n e) $k=n$, and the deck consists of $a$ different cards, each in $n/a$ copies, for some $a$ dividing $n$?\n\n2. As a function of $k$ and $n$, characterize the ordered initial compositions of the starting deck for which Nicolas can be sure to find $sigma$.\n\nNicolas is now no longer interested in the shuffle $sigma$ but only wants to obtain the perfect game. He knows which cards he wants to draw at the first turn, then at the second turn, and so on. We denote by $P_i$ the set of $k$ cards Nicolas wants to draw at the $i$-th turn after shuffling, in a game. We call objective the data of an ordered initial composition $mathcalO$ of the deck and a partition of the set of cards into $n/k$ parts of size $k$, of the form $$\begin{gathered} (P_1, \\ dots,P_{n/k}) \end{gathered}$$. The order of cards within each $P_i$ does not matter since they are drawn in the same turn. An objective is said realizable for a shuffle $sigma$ if Nicolas can draw his cards in a certain order starting from $mathcalO$ so that, after shuffling, he obtains exactly the cards corresponding to the set $P_1$, then $P_2$, etc.\n\n3. Which objectives are realizable whatever the shuffle $sigma$?\n\n4. Which $sigma$ make the fewest objectives realizable, in the following cases:\n a) $k=2$, and all the cards are different?\n b) $k=2$, and the deck consists of 2 different cards, each in $n/2$ copies, alternating perfectly?\n\n5. Redo the preceding question, but making the most objectives realizable. Nicolas now wants to know whether his objective, whose initial order is that of the game, is realizable. The order of the cards, before each game, is always the same.\n\n6. As a function of his objective, how many games does Nicolas need at minimum to know whether it is realizable in the following cases:\n a) $k=2$, and all the cards are different?\n b) $k=2$, and the deck consists of 2 different cards, each in $n/2$ copies, alternating perfectly?\n\n7. As a function of $k$, $n$ and the card distribution, which are the objectives for which it is hardest to know whether they are realizable (i.e. such that the minimum number of games Nicolas needs to know whether they are realizable is the largest)?\n\n8. Propose and study other lines of research.

Topic: Combinatoria, Algebra Metodo: Conteggio, Casework, Invarianti Abilita: Conteggio sistematico, Astrazione, Modellizzazione Area: Combinatoria, Logica e Probabilita, Algebra e Analisi Fonte: apri PDF

Estratto/tradotto da verificare con la fonte.

Suffichi di carte come permutazioni; trovare la sigma del shuffle in giochi minimi, e obiettivi realizzabili (partizioni di obiettivo) per shuffle

Seme di mazzo (Graine deck). Nicolas gioca a un gioco di carte di costruzione del mazzo e cerca il mazzo perfetto, pronto a ricominciare molte volte. Let $$\begin{gathered} k,n \\ in \\ mathbb{N}^{\ast } \end{gathered}$$ con $k$ dividendo $n$ e $$\begin{gathered} k \\ geqslant2 \end{gathered}$$. Il mazzo di Nicolas contiene carte $n$ in totale, ognuna con un simbolo, possibilmente identiche. Nel mazzo ci sono diversi tipi di carte distinti dal loro simbolo; alcune carte possono essere identiche (in questo caso il shuffle non cambia nulla poiché le carte hanno lo stesso aspetto). Deve dare un ordine iniziale al suo mazzo, che può fare come vuole. Il shuffle del mazzo è una permutazione $sigma$ che, applicata all’ordine iniziale delle carte, dà un nuovo ordine; è il shuffle. Poi, all’inizio di ogni partita $P_i$, viene tirato il mazzo il cui ordine è $sigma$ applicato all’ordine iniziale, le carte vengono giocate $k$ da $k$ (così un gioco ha $n/k$ giri). Quando il mazzo ha carte in $n/k$ copie, due carte identiche non possono essere distinte dopo il shuffle.\n\nPer esempio, con le carte $n=6$, 3 carte $A$ e 3 carte $B$ inizialmente nell’ordine $(A,B,A,B,A,B)$, dove le carte vengono giocate $k=3$ per 3 (un gioco ha $n/k=2$ giri) e dove il shuffle è $$\begin{gathered} sigma= \\ beginpmatrix123456 \\ 152346 \\ endpmatrix \end{gathered}$$, gli oggetti $(ABABAB,AAABBB)$ o $(ABABAB,AAB,ABB)$ sono realizzabili per il shuffle $sigma$ (vedere domanda 3). La seconda scelta consente di distinguere $sigma$ da $$\begin{gathered} beginpmatrix123456 \\ 153246 \\ endpmatrix \end{gathered}$$ ma la prima non lo fa (perché lo stato finale del mazzo è lo stesso).\n\n1. In questa domanda, l’obiettivo di Nicolas è trovare il mix $sigma$ il più velocemente possibile. L’ordine iniziale, prima di iniziare una partita, è sempre lo stesso. Quanti giochi ha bisogno al minimo quando:\n a) $k=n$, e tutte le carte sono diverse?\n b) $k=n$, e il mazzo è costituito da 2 carte diverse, una unica e l’altra in $n-1$ copie?\n c) $k=n$, e il mazzo è costituito da 2 carte diverse, ciascuna in $n/2$ copie?\n d) $k=2$, e il mazzo è costituito da 2 carte diverse, ciascuna in $n/2$ copie, e l’ordine iniziale è una perfezione di queste carte?\n e) $k=n$, e il mazzo è costituito da $a$ diverse carte, ciascuna in $n/a$ copie, per alcune $a$ che dividono <K36/n\n\n2. Come funzione di $k$ e $n$, caratterizzare le composizioni iniziali ordinate del mazzo di partenza per cui Nicolas può essere sicuro di trovare $sigma$.\n\nNicolas ora non è più interessato al shuffle $sigma$ ma vuole solo ottenere il gioco perfetto. Sa quali carte vuole disegnare alla prima volta, poi alla seconda volta, e così via. Indichiamo con $P_i$ l’insieme delle carte $k$ che Nicolas vuole disegnare al $i$-esito dopo il shuffling, in una partita. Chiamiamo obiettivo i dati di una composizione iniziale ordinata $mathcalO$ del mazzo e di una partizione del set di carte in parti di dimensioni $n/k$ $k$, del modulo $$\begin{gathered} (P_1, \\ dots,P_{n/k}) \end{gathered}$$. L’ordine delle carte contenute in ciascuna $P_i$ non è importante poiché vengono tirate nello stesso turno. Un obiettivo è detto realizzabile per un shuffle $sigma$ se Nicolas può disegnare le sue carte in un certo ordine partendo da $mathcalO$ in modo che, dopo il shuffling, ottiene esattamente le carte corrispondenti al set $P_1$, quindi $P_2$, ecc.\n\n3. Quali obiettivi sono realizzabili qualunque sia il conflitto? Quali $sigma$ rendono realizzabili i minori obiettivi nei seguenti casi: a) $k=2$, e tutte le carte sono diverse? b) $k=2$, e il mazzo è costituito da 2 carte diverse, ciascuna in copie $n/2$, che si alternano perfettamente? Riprendiamo la questione precedente, ma rendendo più obiettivi realizzabili. Nicolas ora vuole sapere se il suo obiettivo, il cui ordine iniziale è quello del gioco, è realizzabile. L’ordine delle carte, prima di ogni partita, è sempre lo stesso. In funzione del suo obiettivo, a quanti giochi ha bisogno Nicolas almeno per sapere se è realizzabile nei seguenti casi: a) $k=2$, e tutte le carte sono diverse? b) $k=2$, e il mazzo è costituito da 2 carte diverse, ciascuna in copie $n/2$, che si alternano perfettamente? Come funzione di $k$, $n$ e della distribuzione delle carte, che sono gli obiettivi per i quali è più difficile sapere se sono realizzabili (cioè Il numero minimo di giochi che Nicolas deve sapere se sono realizzabili è il più grande). Proporre e studiare altre linee di ricerca.

src_tfjm_2023__Q08