کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651917 1632582 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding a majority ball with majority answers
ترجمه فارسی عنوان
پیدا کردن توپ اکثریت با پاسخ اکثریت
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Suppose we are given a set of n balls {b1,…,bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls {bi1,bi2,bi3}. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least times among the n balls. We show that the minimum number of queries needed to solve this problem is Θ(n) in the adaptive case and Θ(n3) in the non-adaptive case.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 345-351