Optimal strategies against a liar

We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1,…,M}. Player Q has to find out x by asking questions of type: “which one of the sets A₁,A₂,…,A_q, does x belong to?”, where the sets A₁,…,A_q constitute a partition of S. Player R answers “i” to indicate that the number x belongs to A_i. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [log_qM]. The case q=2 and e1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qⁱ, for any i1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qⁱ, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions.     

Least adaptive optimal search with unreliable tests

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let q_e(m) be the smallest integer q satisfying Berlekamp’s bound . Then at least q_e(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly q_e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q_e(m) questions—or equivalently, e-error correcting codes with 2^m codewords of length q_e(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q_e(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q_e(m)−1 questions do not suffice to find the unknown number, and q_e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.     

On the correlation between porosity and strength in high-alumina cement mortars

The evolution in time of the strength and porosity of mortars made with the same type of high-alumina cement and two different types of aggregate, calcareous and siliceous, is studied, and the effects of aggregate composition on both parameters are analysed. It is found that between strength and porosity a linear correlation exists. The effects of pore diameter on such correlation is investigated and it is ascertained that the best correlation can be obtained for total cumulative porosity. The results show that this correlation can be useful for the determination of compressive strengthin situ.

---

Résumé On étudie l’évolution dans le temps de la résistance et de la porosité de mortiers confectionnés avec le même type de ciment alumineux et deux types différents de granulats, calcaire et siliceux, et on analyse les effets de la composition du granulat sur les deux paramètres. On constate qu’il existe une corrélation linéaire entre la résistance et la porosité. On examine les effets du diamètre des pores sur une telle corrélation et on établit qu’on peut obtenir la meilleure corrélation pour la porosité totale. Les résultats montrent que cette corrélation peut servir pour déterminer la résistance à la compressionin situ.

     

Conformational analysis of the conducting copolymer poly(3,4-ethylenedioxythiophene-co-pyrrole)

Electronic structure methods have been used to investigate conducting copolymers of 3,4-ethylenedioxythiophene (EDOT) and pyrrole (Py). The calculations show the planar anti conformation and the syn conformers have extended conjugation. In the anti conformation the EDOT–Py dimer is calculated to have a lower reorganization energy (0.390 eV) than either homodimer (0.423 eV EDOT; 0.455 eV Py) and consequently is expected to have higher charge carrier mobility. The HOMO–LUMO gap of the copolymers is intermediate between the two homopolymers and for regular sequences varies monotonically as a function of the monomer content.     

A dual–polarimetric approach to earthquake damage assessment

In this study, a novel physical approach is proposed to detect damages due to earthquakes using dual polarimetric (DP) coherent Synthetic Aperture Radar (SAR) imagery. An optimization method, aimed at enhancing scattering basis differences between measurements collected before and after the event, is designed exploiting Lagrange optimization of the difference between two polarimetric covariance matrices. A meaningful showcase is presented to demonstrate the soundness of the proposed approach that consists of processing Sentinel–1 C–band scenes related to 2016 Central Italy Earthquake. The proposed approach, which is contrasted with the conventional coherence based single– and dual–polarization approaches, results in the best sensitivity to damages.