On a conjecture of Butler and Graham

Tengyu Ma, Xiaoming Sun, Huacheng Yu

Research output: Contribution to journalArticlepeer-review

Abstract

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k]n : there exists a way to mark one point on each coordinate line in [k]n, so that every point in [k] n is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k n and as + bt = nkn-1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.

Original languageEnglish (US)
Pages (from-to)265-274
Number of pages10
JournalDesigns, Codes, and Cryptography
Volume69
Issue number3
DOIs
StatePublished - Dec 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Characteristic function
  • Hat guessing games
  • Marking coordinate lines

Fingerprint

Dive into the research topics of 'On a conjecture of Butler and Graham'. Together they form a unique fingerprint.

Cite this