Consider all possible sets of natural numbers $(x_1, x_2, ..., x_{100})$ such that $1\leq x_i \leq 2017$ for every $i = 1,2, ..., 100$. We say that the set $(y_1, y_2, ..., y_{100})$ is greater than the set $(z_1, z_2, ..., z_{100})$ if $y_i> z_i$ for every $i = 1,2, ..., 100$. What is the largest number of sets that can be written on the board, so that any set is not more than the other set?
Problem
Source: Kazakhstan National Olympiad 2017, Final Round, 11-Grade, P5
Tags: logic, Sets, combinatorics
Generic_Username
19.03.2017 01:18
Is it possible to establish partial order?
laegolas
19.03.2017 01:30
I think a few things need to be clarified in the problem statement. I'm guessing the OP means sequences $(x_1,x_2,x_3,\dots x_{100})$ rather than sets, but then we need to decide whether or not terms may be repeated in a sequence.
DVDthe1st
19.03.2017 03:54
Partial order is not required, since the comparison between each elements is strict. @laegolas - OP means 100-tuples rather than sets.
The answer is $2017^{100}-2016^{100}$, which can be constructed by considering the set of all tuples $S$ that contain at least one $2017$.
Now for every $x=(x_1,x_2,...,x_n)\in S$, we denote $S_x$ as the set containing $(x_1-k,x_2-k,...,x_n-k)$, so long as every term in the tuple is positive. It is clear that the family of $S_x$ forms a partition of all tuples, however there can only be one element selected from each $S_x$.
math90
20.03.2017 12:30
Does the problem mean that no two elements can be compared?