On a conjecture of Butler and Graham

Tengyu Ma; Xiaoming Sun; Huacheng Yu

doi:10.1007/s10623-012-9656-8

On a conjecture of Butler and Graham

Tengyu Ma
, Xiaoming Sun
, Huacheng Yu

Research output: Contribution to journal › Article › peer-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]ⁿ : there exists a way to mark one point on each coordinate line in [k]ⁿ, so that every point in [k] ⁿ 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 ⁿ and as + bt = nk^n-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 language	English (US)
Pages (from-to)	265-274
Number of pages	10
Journal	Designs, Codes, and Cryptography
Volume	69
Issue number	3
DOIs	https://doi.org/10.1007/s10623-012-9656-8
State	Published - Dec 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science Applications
Applied Mathematics

Keywords

Characteristic function
Hat guessing games
Marking coordinate lines

Access to Document

10.1007/s10623-012-9656-8

Cite this

@article{a0fe8f183b4a4c7bb38c900c4e192d29,

title = "On a conjecture of Butler and Graham",

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.",

keywords = "Characteristic function, Hat guessing games, Marking coordinate lines",

author = "Tengyu Ma and Xiaoming Sun and Huacheng Yu",

note = "Funding Information: Acknowledgments The authors would like to thank the anonymous referees for their helpful comments and suggestion to improve the presentation of this paper. This work was supported in part by the National Natural Science Foundation of China Grant 61170062, 61061130540, the National Basic Research Program of China Grant 2011CBA00301.",

year = "2013",

month = dec,

doi = "10.1007/s10623-012-9656-8",

language = "English (US)",

volume = "69",

pages = "265--274",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - On a conjecture of Butler and Graham

AU - Ma, Tengyu

AU - Sun, Xiaoming

AU - Yu, Huacheng

N1 - Funding Information: Acknowledgments The authors would like to thank the anonymous referees for their helpful comments and suggestion to improve the presentation of this paper. This work was supported in part by the National Natural Science Foundation of China Grant 61170062, 61061130540, the National Basic Research Program of China Grant 2011CBA00301.

PY - 2013/12

Y1 - 2013/12

N2 - 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.

AB - 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.

KW - Characteristic function

KW - Hat guessing games

KW - Marking coordinate lines

UR - https://www.scopus.com/pages/publications/84883234294

UR - https://www.scopus.com/pages/publications/84883234294#tab=citedBy

U2 - 10.1007/s10623-012-9656-8

DO - 10.1007/s10623-012-9656-8

M3 - Article

AN - SCOPUS:84883234294

SN - 0925-1022

VL - 69

SP - 265

EP - 274

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 3

ER -

On a conjecture of Butler and Graham

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this