Determine the maximal size of a set of positive integers with the following properties: $1.$ The integers consist of digits from the set $\{ 1,2,3,4,5,6\}$. $2.$ No digit occurs more than once in the same integer. $3.$ The digits in each integer are in increasing order. $4.$ Any two integers have at least one digit in common (possibly at different positions). $5.$ There is no digit which appears in all the integers.
Problem
Source: Baltic Way 2006
Tags: combinatorics proposed, combinatorics
25.01.2012 13:16
I think the answer is $32$ let denote the set of digits of an integer $A$ with $S(A)$ we call two integers$a,b$ a pair if $S(a) \cup S(b)=\{1,2,3,4,5,6\}$ and $S(a) \cap S(b)=\phi$ obviously, we can choose at most one integer from each pair so the maximal number of integers that we can choose is at most $\frac{2^6}{2}=32$ for achieving this maximal number of integers consider all integers $a$ such that $|S(a)|\in\{6,5,4\}$ and these integers $\{123,124,125,126,134,135,136,145,146,156\}$ Feel free to correct me
25.01.2012 14:05
mohamad4 wrote: For achieving this maximal number of integers consider all integers $a$ such that $S(a)\in\{6,5,4\}$ and these integers $\{123,124,125,126,134,135,136,145,146,156\}$. I don't quite understand what you mean there; by your notations $S(a)$ is a set, so $S(a)\in\{6,5,4\}$ is ill-defined. But a simple example is given by $\{1\} \cup B$, for any $\emptyset \neq B \subseteq \{2,3,4,5,6\}$, plus the set $\{2,3,4,5,6\}$. The same reasoning works for the general problem Determine the largest number of subsets of a set $X$ with $n>2$ elements, pairwise non-disjoint, but with empty intersection of all. By the $(A, X\setminus A)$ argument, the maximum possible is $2^{n-1}$. A model is given by selecting an arbitrary $x\in X$, and taking $\{x\} \cup Y$, for any $\emptyset \neq Y \subseteq X\setminus \{x\}$, plus the set $X\setminus \{x\}$. EDIT. With the correction made, that example is now correct; however, my example above works the same for any $n$, even or odd.
25.01.2012 17:36
mavropnevma wrote: mohamad4 wrote: For achieving this maximal number of integers consider all integers $a$ such that $S(a)\in\{6,5,4\}$ and these integers $\{123,124,125,126,134,135,136,145,146,156\}$. I don't quite understand what you mean there; by your notations $S(a)$ is a set, so $S(a)\in\{6,5,4\}$ is ill-defined. I'm really sorry ,i mean $|S(a)|$ instead of $S(a)$ now,i think that's correct!