| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Proposed by Walther Janous, Ursulinengymnasium, Innsbruck, Austria.
Let d and k be natural numbers with d|k. Let X[k] be the set of all
k-tuples ( x[1], ..., x[k] ) of integers such that 0 <= x[1] <= ... <=
x[k] <= k and x[1] + ... + x[k] is divisible by d. Furthermore let
Y[k] be the set of all elements ( x[1], ..., x[k]) of X[k] such that
x[k] = k. What is the relationship between the sizes of X[k] and Y[k]?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1730.1 | where |A| is the size of set A | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Wed Mar 17 1993 20:27 | 6 |
> What is the relationship between the sizes of X[k] and Y[k]?
0 < |Y[k]| < |X[k]|
Dan
0:-)
| |||||
| 1730.2 | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Thu Mar 18 1993 10:06 | 26 | |
Let d and k be natural numbers with d|k. Let X[k] be the set of all
k-tuples ( x[1], ..., x[k] ) of integers such that 0 <= x[1] <= ... <=
x[k] <= k and x[1] + ... + x[k] is divisible by d. Furthermore let
Y[k] be the set of all elements ( x[1], ..., x[k]) of X[k] such that
x[k] = k. What is the relationship between the sizes of X[k] and Y[k]?
Is there a typo up there ? First you say
Let X[k] be the set of all k-tuples (x[1], ..., m x[k])
From that statement, I assume that x[1] is a k-tuple, and x[2] is a k-tuple,...
and x[k] is a k-tuple. But you go on to say
0 <= x[1] <= x[2] ...
That doesn't make sense, since we can't compare a number to a k-tuple.
Maybe you mean
0 <= x[1,1] <= x[1,2] ... ????
Please clarify.
/Eric
| |||||
| 1730.3 | RUSURE::EDP | Always mount a scratch monkey. | Thu Mar 18 1993 10:16 | 8 | |
Re .2:
Each x[i] is an integer. ( x[1], ..., x[k] ) is a k-tuple of integers.
X[k] is the set of all such k-tuples such that 0 <= x[1] <= ... <= x[k]
<= k and with sum divisible by d.
-- edp
| |||||
| 1730.4 | RUSURE::EDP | Always mount a scratch monkey. | Wed Jan 12 1994 11:08 | 40 | |
Solution by Margherita Barile, student, Universitat Essen, Germany.
We show that
|Y[k]| = |X[k]| / 2.
Let 0 <= x[1] <= x[2] <= ... <= x[k] <= k. For all i, j in { 1, ..., k
} set
a[i,j] = { 1 if x[i] >= j, 0 otherwise.
Then
k
x[i] = sum a[i,j]
j=1
k
for all i. Moreover, set b[i,j] = 1 - a[i,j] and y[i] = sum b[j,i]
j=1
for all i. Since a[i,j] >= a[i,j+1] for all i, j in { 1, ..., k }, it
follows that 0 <= y[1] <= ... <= y[k] <= k. Also
k k k k 2
sum x[i] + sum y[i] = sum sum (a[i,j] + 1 - a[i,j]) = k .
i=1 i=1 i=1 j=1
Thus (x[1], ..., x[k]) is in X[k] if and only if (y[1], ..., y[k]) is
in X[k] [since d|k]. Furthermore, x[k] = k if and only if a[i,k] = 1
for some i [if and only if a[k,k] = 1], which is the case if and only
if
k
y[k] = k - sum a[i,k] < k.
i=1
Thus the injection phi: X[k] -> X[k] defined by the assignment
phi: (x[1], ..., x[k]) -> (y[1], ..., y[k])
is such that phi(Y[k]) is a subset of X[k] \ Y[k] and phi(X[k] \ Y[k])
is a subset of Y[k]. Hence |Y[k]| = |X[k] \ Y[k]|, so |X[k]| = 2
|Y[k]|, as was to be proved.
| |||||