Problem A. 830. (September 2022)

A. 830. For \(\displaystyle H\subset \mathbb{Z}\) and \(\displaystyle n\in \mathbb{Z}\), let \(\displaystyle h_n\) denote the number of finite subsets of \(\displaystyle H\) in which the sum of the elements is \(\displaystyle n\). Does there exist \(\displaystyle H\subset \mathbb{Z}\), for which \(\displaystyle 0\notin H\), and \(\displaystyle h_n\) is a (finite) even number for every \(\displaystyle n\in \mathbb{Z}\)? (The sum of the elements of the empty set is 0.)

Submitted by Csongor Beke, Cambridge

(7 pont)

Deadline expired on October 10, 2022.

Solution 1: Let \(\displaystyle A_0=\{-1,1\}\) and observe that 0 can be obtained in two ways. Let us define finite sets \(\displaystyle A_0\subset A_1 \subset \dots \subset A_n\subset \dots\) such that the following are true:

• For every \(\displaystyle k\ge 1\) let \(\displaystyle A_{2k-1}\) have an even number of subsets where the sum is \(\displaystyle k\), and also make sure that no subset \(\displaystyle H\subset A_{2k-1}\) is created for which \(\displaystyle H \not\subset A_{2k-2}\) and \(\displaystyle -k+1 \leq \sum_{x \in H} x \leq k-1\).
• For every \(\displaystyle k\ge 1\) set \(\displaystyle A_{2k}\) has an even number of subsets in which the sum is \(\displaystyle -k\), and also make sure no subset \(\displaystyle H\subset A_{2k}\) is created for which \(\displaystyle H \not\subset A_{2k-1}\) and \(\displaystyle -k+1 \leq \sum_{x \in H} x \leq k\).
• \(\displaystyle |\min\{x \in A_n\}|<\max\{x \in A_n\}\) if and only if \(\displaystyle n\) is odd.

Observe that the conditions above guarantee that for every \(\displaystyle -k+1\le j \le k\) there will be an even number of subsets in which the sum is \(\displaystyle j\), since in each step we make sure that a given number is the sum for an even number of subsets, and the subsequent steps won't change this.

We will use induction to create sets \(\displaystyle A_n\). \(\displaystyle A_0\) is already defined.

Let us assume that \(\displaystyle A_{2k-2}\) is already defined. Let \(\displaystyle -m\) denote the sum of the negative elements of \(\displaystyle A_{2k-2}\). If \(\displaystyle A_{2k-2}\) has an odd number of subsets in which the sum is \(\displaystyle k\), then let's define \(\displaystyle A_{2k-1}=A_{2k-2}\cup \{m+k\}\), otherwise let \(\displaystyle A_{2k-1}=A_{2k-2}\cup \{m+k+1\}\). Based on the induction hypothesis, (one of) the element(s) with the largest absolute value in \(\displaystyle A_{2k-2}\) is negative, so in \(\displaystyle A_{2k-1}\) the newly added element will have the largest absolute value, so the third requirement is satisfied. This also shows that \(\displaystyle m+k\) and \(\displaystyle m+k+1\) are not in \(\displaystyle A_{2k-2}\), so we indeed added a new element.

The new subsets of \(\displaystyle A_{2k-1}\) are those that contain the new element (\(\displaystyle m+k\) or \(\displaystyle m+k+1\)). Thus based on the definition of \(\displaystyle m\) all the new sums are at least \(\displaystyle k\). If the new element is \(\displaystyle m+k\), then \(\displaystyle k\) is obtained exactly once (by choosing \(\displaystyle m+k\) and all the negative elements), and if the new element is \(\displaystyle m+k+1\), then we do not get \(\displaystyle k\) as a sum. Thus we have guaranteed that \(\displaystyle k\) is obtained for an even number of subsets.

Let us use a similar process to define \(\displaystyle A_{2k}\) from \(\displaystyle A_{2k-1}\). Let \(\displaystyle m\) denote the sum of the positive elements of \(\displaystyle A_{2k-1}\). If \(\displaystyle -k\) is the sum in an odd number of subsets of \(\displaystyle A_{2k-1}\), then let \(\displaystyle A_{2k}=A_{2k-1}\cup \{-m-k\}\), otherwise let \(\displaystyle A_{2k}=A_{2k-1}\cup \{-m-k-1\}\). Similarly to the earlier case, the newly added element will have the largest absolute value, all the new sums are at most \(\displaystyle -k\), and \(\displaystyle -k\) will be a sum in a new subset if and only if \(\displaystyle -m-k\) is the new element. In this case there will be exactly one new subset with a sum of \(\displaystyle -k\), so the number of subsets in which the sum is \(\displaystyle -k\) is even.

Finally, let \(\displaystyle H=\cup_{n=0}^{\infty}A_n\). From the definition \(\displaystyle 0\not \in H\), and for any finite \(\displaystyle G\subset H\) it is also true that \(\displaystyle G\subset A_n\) for some \(\displaystyle n\). Thus any number \(\displaystyle k\) can be the sum in a finite subset of \(\displaystyle H\) that is already a subset of \(\displaystyle A_{2k}\), and we know that the number of such subsets is even. Thus this is indeed a good construction.

Solution 2: Let \(\displaystyle H'=\{1,-2,4,-8,...,(-2)^k,...\}\). It is well known that every integer can be obtained in a unique way as a sum of different elements of \(\displaystyle H_1\) (this is sometimes referred to as the negabinary system). Let \(\displaystyle H=H'\cup \{-1\}\). It is very easy to check that every number can be obtained in exactly two ways, thus this is a good construction.

Statistics:

23 students sent a solution.
7 points:	Czanik Pál, Duchon Márton, Lovas Márton, Mckinley D. Xie, Móra Márton Barnabás, Németh Márton, Nguyen Kim Dorka, Seres-Szabó Márton, Szakács Ábel, Sztranyák Gabriella, Varga Boldizsár, Wiener Anna.
6 points:	Chrobák Gergő, Farkas 005 Bendegúz.
5 points:	3 students.
0 point:	6 students.

Problems in Mathematics of KöMaL, September 2022