{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:40:01Z","timestamp":1750455601541,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T00:00:00Z","timestamp":1108425600000},"content-version":"unspecified","delay-in-days":45,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>Suppose we are given <jats:inline-formula>$n$<\/jats:inline-formula> coloured balls and an integer <jats:inline-formula>$k$<\/jats:inline-formula> between 2 and <jats:inline-formula>$n$<\/jats:inline-formula>. How many colour-comparisons <jats:inline-formula>$Q(n,k)$<\/jats:inline-formula> are needed to decide whether <jats:inline-formula>$k$<\/jats:inline-formula> balls have the same colour? The corresponding problem when there is an (unknown) linear order with repetitions on the balls was solved asymptotically by Bj\u00f6rner, Lov\u00e1sz and Yao, the complexity being <jats:inline-formula>\\smash{$\\theta (n\\log\\frac{2n}{k})$}<\/jats:inline-formula>. Here we give the exact answer for <jats:inline-formula>\\smash{$k&gt;\\frac{n}{2}: Q(n,k)=2n-k-1$}<\/jats:inline-formula>, and the order of magnitude for arbitrary <jats:inline-formula>\\smash{$k:Q(n,k)=\\theta(\\frac{n^2}{k})$}<\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548304006704","type":"journal-article","created":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T12:56:08Z","timestamp":1108472168000},"page":"17-24","source":"Crossref","is-referenced-by-count":0,"title":["The $k$-Equal Problem"],"prefix":"10.1017","volume":"14","author":[{"given":"MARTIN","family":"AIGNER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2005,2,15]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:19:02Z","timestamp":1750454342000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006704\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":0,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["S0963548304006704"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006704","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}