Home > Algebra, Combinatorics, IMO, Olympiad, Problem Solving > Positive integers partitioned by translations of the same set

Positive integers partitioned by translations of the same set


It is possible to partition the set \Bbb{N}^*=\{0,1,2,...\} in infinitely many parts each of which having infinitely many elements such that there exists one member of the partition such that all other members of the partiton are translates of the first set with an integer?

Answer: Surprinsingly yes. Partition \Bbb{N} into two parts, namely A which is the set of positive integers which have zeros on even positions (starting from right) and B be the set of positive integers which have zeros on odd positions (starting from right). Evidently, every positive integer is the sum of an element from A and one from B.
Say that (b_k)_{k \geq 1} is an enumeration of B. Then \Bbb{N}= A\cup(b_1+A)\cup ... \cup (b_k+A)\cup .... Let’s prove now that any two of A,\ b_i+A are disjoint. It is obvious that A \cap (b_i+A)=\emptyset from the definitions of A,B.
Suppose there exists i\neq j and k \in (b_i+A)\cap (b_j+A). Then k=b_i+m=b_j+n, where n,m have zeros on even positions. The digits from odd positions are uniquely determined by b_i and $b_j$ which means that b_i=b_j, contradiction.
Therefore, these sets form indeed a partition as required.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: