AbstractRecently, Tu and Deng proposed a combinatorial conjecture about binary strings, and, on the assumption that the conjecture is correct, they obtained two classes of Boolean functions which are both algebraic immunity optimal, the first of which are also bent functions. The second class gives balanced functions, which have optimal algebraic degree and the best nonlinearity known up to now. In this paper, by using three different approaches, we prove the conjecture for many cases. We also propose some problems about the weight equations which are related to this conjecture. Because of the scattered distribution, we predict that an exact count is difficult to obtain, in general.