Search

Vengono descritte le gare a squadre delle Olimpiadi della Matematica, una competizione annuale molto seguita dagli studenti delle scuole superiori in Italia. Le squadre, composte da sette membri, si allenano durante tutto l'anno e si sfidano con spirito agonistico. Le gare a squadre stimolano la collaborazione alla risoluzione dei problemi e l'aspetto ludico aiuta a rendere la matematica meno temuta., The paper describes the team competitions of the Mathematical Olympiad, an annual competition much awaited by students in Italy. The teams are composed of seven members and they train throughout the year and challenge each other with a competitive spirit. Mathematical team competitions stimulate collaboration in problemsolving and the playful aspect helps to fight the fear of mathematics.

Discrete tomography deals with the reconstruction of images from a (usually small) set of X-ray projections. This is achieved by modeling the tomographic problem as a linear system of equations and then applying a suitable discrete reconstruction algorithm based on iterations. In this paper we adopt the well-known grid model and prove some geometric properties of integer solutions consisting of $p\geq 2$ gray levels. In particular, we show that all gray-scale solutions having the same two-norm belong to a same hypersphere, centered at the uniform image related to the data and having radius ranging in an interval whose bounds are explicitly computed. Moving from a uniqueness theorem for gray-scale images, we compute special sets of directions that guarantee uniqueness of reconstruction and exploit them as the input of the Conjugate Gradient Least Squares algorithm. Then we apply an integer rounding to the resulting output and, basing on previously described geometric parameters, we test the quality of the obtained reconstructions for an increasing number of iterations, which leads to a progressive improvement of the percentage of correctly reconstructed pixels, until perfect reconstruction is achieved. Differently, using sets of directions which are classically employed, but far from being sets of uniqueness, only partial reconstructions are obtained.

Nonostante la teoria dei codici coniughi geniali intuizioni matematiche con utilissime applicazioni pratiche, essa rimane praticamente sconosciuta al grande pubblico. Per tale ragione in questo articolo proponiamo una serie di attività che permettono di avvicinare gli studenti delle scuole secondarie ad alcuni temi di questa affascinante disciplina. In particolare, le idee di codice rilevatore e di codice correttore proposte da Hamming vengono presentate mescolando elementi di gamification ad un apprendimento di tipo esperienziale.

The power sum polynomial associated to a multi-subset of the projective plane PG(2,q) is the sum of the (q−1)-th powers of the Rédei factors of the points in the multi-subset. The classification of multi-subsets having the same power sum polynomial passes through the determination of those multi-subsets associated to the zero polynomial, called ghosts. In this paper we provide new classes of ghosts and compute the dimension of the ghost subspace by exploiting the linear code generated by the lines of PG(2,q) and its dual. Moreover, we explicitly enumerate and classify ghosts for planes of order 2, 3, 4.

The reconstruction of an unknown function $f$ from its line sums is the aim of discrete tomography. However, two main aspects prevent reconstruction from being an easy task. In general, many solutions are allowed due to the presence of the switching functions. Even when uniqueness conditions are available, results about the NP-hardness of reconstruction algorithms make their implementation inefficient when the values of $f$ are in certain sets. We show that this is not the case when $f$ takes values in a field or a unique factorization domain, such as $R$ or $Z$. We present a linear time reconstruction algorithm (in the number of directions and in the size of the grid), which outputs the original function values for all points outside of the switching domains. Freely chosen values are assigned to the other points, namely, those with ambiguities. Examples are provided.

For a point of the projective space $PG(n,q)$, its R'edei factor is the linear polynomial in $n+1$ variables, whose coefficients are the point coordinates. The power sum polynomial of a subset $S$ of $PG(n,q)$ is the sum of the $(q-1)$-th powers of the R'edei factors of the points of $S$. The fact that many subsets may share the same power sum polynomial offers a natural connection to discrete tomography. In this paper we deal with the two-dimensional case and show that the notion of ghost, whose employment enables to find all solutions of the tomographic problem, can be rephrased in the finite geometry context, where subsets with null power sum polynomial are called ghosts as well. In the latter case, one can add ghosts still preserving the power sum polynomial by means of the multiset sum (modulo the field characteristic). We prove some general results on ghosts in $PG(2,q)$ and compute their number in case $q$ is a prime.

Per chi si occupa di divulgazione della matematica, la figura di John Horton Conway è imprescindibile: da un lato si è affascinati dall’accademico che ha dato contributi importanti in svariate aree, dall’altro si apprezza la spensieratezza dell’inventore di giochi matematici, che possono costituire un possibile approccio ad una materia che da sempre spaventa il grande pubblico. La rete offre elenchi dettagliati dei contributi di Conway; in questo articolo si è deciso di presentarne due, uno più prettamente legato alla matematica pura (ma con possibili applicazioni ancora da esplorare) e uno invece sul versante della matematica ricreativa. Si tratta, rispettivamente, del gruppo Mostro e del Game of Life, sui quali è stato modellato anche il titolo dell’articolo.

In discrete tomographic image reconstruction, projections are taken along a finite set S of valid directions for a working grid A. In general, uniqueness cannot be achieved in the whole grid A. Usually, some information on the object to be reconstructed is introduced, that, sometimes, allows possible ambiguities to be removed. From a different perspective, one aims in finding subregions of A where uniqueness can be guaranteed, and obtained in linear time, only from the knowledge of S. When S consists of two lattice directions, the shape of any such region of uniqueness, say ROU, have been completely characterized in previous works by means of a double Euclidean division algorithm called DEDA. Results have been later extended to special triples of directions, under a suitable assumption on their entries. In this paper we remove the previous assumption, so providing a complete characterization of the shape of the ROU for such kind of triples. We also show that the employed strategy can be even applied to more general sets of three directions, where the corresponding ROU can be characterized as well. Independently of the combinatorial interest of the problem, the result can be exploited to define in advance, namely before using any kind of radiation, suitable sets of directions that allow regions of interest to be included in the corresponding ROU. Results have been proved in all details, and several experiments are considered, in order to support the theoretical steps and to clarify possible applications.

Discrete tomography deals with the reconstruction of images from projections collected along a few given directions. Different approaches can be considered, according to different models. In this paper we adopt the grid model, where pixels are lattice points with integer coordinates, X-rays are discrete lattice lines, and projections are obtained by counting the number of lattice points intercepted by X-rays taken in the assigned directions. We move from a theoretical result that allows uniqueness of reconstruction in the grid with just four suitably selected X-ray directions. In this framework, the structure of the allowed ghosts is studied and described. This leads to a new result, stating that the unique binary solution can be explicitly and exactly retrieved from the minimum Euclidean norm solution by means of a rounding method based on some special entries, which are precisely determined. A corresponding iterative algorithm has been implemented, and tested on a few phantoms having different characteristics and structure.

The goal of discrete tomography is to reconstruct an image, seen as a finite set of pixels, by knowing its projections along given directions. Uniqueness of reconstruction cannot be guaranteed in general, because of the existence of the switching components. Therefore, instead of considering the uniqueness problem for the whole image, in this paper we focus on local uniqueness, i.e., we seek what pixels have uniquely determined value. Two different kinds of local uniqueness are presented: one related to the structure of the directions and of the grid supporting the image, having as a sub-case the region of uniqueness (ROU), and the other one depending on the available projections. In the case when projections are taken along two lattice directions, both kinds of uniqueness have been characterized in a graph-theoretical reformulation. This paper is intended to be a starting point in the construction of connections between pixels with uniquely determined value and graphs.

Several papers in the available literature tackled problems concerning convex polyominoes in discrete tomography. An interesting subclass consists of L-convex polyominoes, since the related reconstruction problem can have only a unique solution. On the other hand, recent studies have modeled an approach to reconstruct objects even in the case that some of the projections are unavailable, due to a particularly dense part of the scanned object, that we refer to as a blocking component. In this work we merge the two problems in order to obtain efficient reconstruction algorithms for convex and L-convex polyominoes, in case a blocking component is included.

The faithful reconstruction of an unknown object from projections, i.e., from measurements of its density function along a finite set of discrete directions, is a challenging task. Some theoretical results prevent, in general, both to perform the reconstruction sufficiently fast, and, even worse, to be sure to obtain, as output, the unknown starting object. In order to reduce the number of possible solutions, one tries to exploit some a priori knowledge. In the present paper we assume to know the size of a lattice grid $\mathcal{A}$ containing the object to be reconstructed. Instead of looking for uniqueness in the whole grid $\mathcal{A}$, we want to address the problem from a \textit{local} point of view. More precisely, given a limited number of directions, we aim in showing, first of all, which is the subregion of $\mathcal{A}$ where pixels are uniquely reconstructible, and then in finding where the reconstruction can be performed quickly (in linear time). In previous works we have characterized the shape of the region of uniqueness (ROU) for any pair of directions. In this paper we show that the results can be extended to special sets of three directions, by splitting them in three different pairs. Moreover, we show that such a procedure cannot be employed for general triples of directions. We also provide applications concerning the obtained characterization of the ROU, and further experiments which underline some regularities in the shape of the ROU corresponding to sets of three not-yet-considered directions.

In some circumstances it is preferable, instead of modeling the real world as a continuous space, facing directly the discrete problem. It may happen in the framework of Tomography, where we can employ several tools relying on discrete models: this is Discrete Tomography. In this work we start our investigation from a limit case of the discretization process, namely the grid model, and then show how we can extend our approach to a more general framework. It turns out that, if we employ X-rays in the strip model whose width is under a given threshold, uniqueness of reconstruction, which came from exploiting the line structure of X-rays in the grid model, is still achieved. Moreover, we wrote a program which enumerates all possible sets of four valid directions which ensure uniqueness of reconstruction in a given lattice grid.

In the reconstruction problem of Discrete Tomography, projections are considered from a finite set $\mathcal{S}$ of lattice directions. Employing a limited number of projections implies that the injectivity of the Radon transform is lost, and, in general, images consistent with a given set of projections form a huge class. In order to lower the number of allowed solutions, one usually tries to include in the problem some a priori information. This suggests that modeling the tomographic reconstruction problem as a linear system of equations is preferable. In this paper we propose to restrict the usual notion of uniqueness, related to the solutions of the linear system, and to provide, for each set $\mathcal{S}$, a geometrical characterization of the shape of a lattice subset, say region of uniqueness (ROU), forming a partial, fast reconstructible, solution. Any selected set $\mathcal{S}$ intrinsically determines its ROU inside an arbitrary lattice grid. For instance, trivially, if $|\mathcal{S}|=1$, the ROU is represented by two rectangles having sizes equal to the absolute values of the entries of the unique direction in $\mathcal{S}$, and placed at two opposite corners of the chosen grid. Surprisingly, if $|\mathcal{S}|=2$, the problem becomes much more complicated. Our purpose is to provide a geometrical characterization of the ROU. This is based on a double Euclidean division algorithm (DEDA), which runs in polynomial time. It turns out that the ROU is delimited by a zigzag profile obtained by means of numerical relations among the entries of the employed directions. According to different inputs in DEDA, the shape of the ROU can change consistently, as it can be easily observed from the provided examples. Moreover, after selecting a region of interest (ROI) from a given phantom, we exploit DEDA to reconstruct the part of the ROI which falls in the ROU and, with a few further a priori knowledge, even parts of the ROI which are outside the ROU.

In this paper the well-known problem of reconstructing hv-convex polyominoes is considered from a set of noisy data. Differently from the usual approach of Binary Tomography, this leads to a probabilistic evaluation in the reconstruction algorithm, where different pixels assume different probabilities to be part of the reconstructed image. An iterative algorithm is then applied, which, starting from a random choice, leads to an explicit reconstruction matching the noisy data.

In Discrete Tomography, objects are reconstructed by means of their projections along certain directions. It is known that, for any given lattice grid, special sets of four valid projections exist that ensure uniqueness of reconstruction in the whole grid. However, in real applications, some physical or mechanical constraints could prevent the use of such theoretical uniqueness results, and one must employ projections fitting some further constraints. It turns out that global uniqueness cannot be guaranteed, even if, in some special areas included in the grid, uniqueness might be still preserved. In this paper we address such a question of local uniqueness. In particular, we wish to focus on the problem of characterizing, in a sufficiently large lattice rectangular grid, the sub-region which is uniquely determined under a set $S$ of generic projections. It turns out that the regions of local uniqueness consist of some curious twisting of rectangular areas. This deserves a special interest even from the pure combinatorial point of view, and can be explained by means of numerical relations among the entries of the employed directions.

The recovery of an unknown density function from the knowledge of its projections is the aim of tomography. In many cases, considering the problem from a discrete perspective is more convenient than employing a continuous approach: discrete tomography, and in particular binary tomography, is therefore exploited. One of the main goals of tomography is guaranteeing that the produced output coincides with the scanned object, namely, one wants to achieve uniqueness of reconstruction, even when only a few directions, from which projections are taken, are employed. Relying on a theoretical result stating that special sets of just four lattice directions are enough to uniquely reconstruct a binary grid, we prove that such sets are stable, in the sense that a small discrete perturbation of the components of the directions returns sets which again ensure uniqueness of reconstruction. Examples are provided.