On more variants of the Majority Problem - Optimisation Combinatoire Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

On more variants of the Majority Problem

Résumé

The variant of the Majority problem we are considering is the following. A colorblind player is given a set of colored balls. He knows that each ball is colored either red or green, and that there are less green than red balls, but he cannot distinguish the two colors. For any two balls he can ask whether they are colored the same. His goal is to determine the color of each of the balls, asking as few questions as possible. In the case where there are at most (respectively exactly ) green balls, the minimum number of questions that guarantees the determination of the colors is denoted by (respectively ). We extend results of Aigner on exact values of , and we provide upper bounds for , and even exact values for the first two values of p. Our results lead to several new questions.
Fichier principal
Vignette du fichier
S0166218X19302070.pdf (410.23 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02148478 , version 1 (25-10-2021)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Myriam Preissmann, Paul-Elliot Angles d'Auriac, Francis Maisonneuve, Vivien Maisonneuve, Emmanuel Preissmann. On more variants of the Majority Problem. Discrete Applied Mathematics, 2019, 265, pp.1-12. ⟨10.1016/j.dam.2019.03.030⟩. ⟨hal-02148478⟩
119 Consultations
35 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More