Re: combinatorics problem



Ed Hook wrote:
> Snis Pilbor wrote:
> > Hello!
> >
> > Suppose I have a set of objects which is partitioned into
> > equivalence classes by an equivalence relation ~. I have a machine
> > which can count how many objects there are, and how many pairs (x,y)
> > there are such that x~y. I want to determine how many total classes
> > there are. Is this possible?
> >
>
> I don't _think_ so ...
>
> Suppose that C is one of the equivalence classes, containing
> k objects. How many pairs will your second machine count for
> C ?? Well, there are k pairs (x,x) with x in C and then there
> are k(k-1) pairs (x,y) with x, y in C and x != y, So C contributes
> k^2 to the second machine's count. Clearly, the second machine's
> output is just the sum over all such classes C of the counts it
> obtains so it follows that, if your *general* problem were
> solvable, then you could conclude that any n which can be expressed
> as a sum of squares has exactly _one_ such representation.
>
> But that's well-known to be *false* ...

I'm not sure that's quite what's going on ...

As I read the problem, you're trying to solve a system of Diophantine
equations with a variable number of variables. You're trying to
determine whether there's a solution to the system:

x_1^2 + x_2^2 + ... + x_m^2 = A (1)
x_1 + x_2 + ... + x_m = B (2)

y_1^2 + y_2^2 + ... + y_n^2 = A (3)
y_1 + y_2 + ... + y_n = B, (4)

where x_i, y_j are positive integers, and m =/= n. (x_i and y_i are the
number of elements in the ith equivalence class for each of two
equivalence relations, of course.) If there is a solution, the problem
is hopeless, since the answer isn't unique. If there are no solutions,
then you want to solve (1) and (2).

For instance, if A = 25, there are solutions to the subsystem of (1)
and (3) with m =/= n (namely m=1, n=2, x_1 = 5, y_1 = 3, y_2 = 4) in
spite of 25 being able to be written as the sum of two squares in more
than one way.

(Note that A = 50, which has the solutions x = (7,1) and y = (5,5)
doesn't help, since m = 2 = n here.)

Maybe writing a computer program to generate the ordered pairs (A,B)
satisfying (1) and (2) with a fixed value of m will help.

> > Thanks very kindly in advance,
> > Snis Pilbor
> > (it isn't a homework problem)

I would hope not. 8-) If it's got a nice solution, then it would be
worthy of the Putnam Exam.

--- Christopher Heckman

.

Relevant Pages

  • Re: Orientation of rotationally invariant bit vectors
    ... The equivalence classes are defined such that each class contains all ... I now apply also reflection, ... we reach the same equivalence class. ... Since applying a rotation and a reflection in sequence is equivalend ...
    (comp.theory)
  • Orientation of rotationally invariant bit vectors
    ... The equivalence classes are defined such that each class contains all ... I now apply also reflection, ... we reach the same equivalence class. ... it is a n-bit to 1-bit function. ...
    (comp.theory)
  • Re: Analysis with nonmeasurable set..
    ... There exists a nonmeasurable set in the interval [0,1). ... We define an equivalence relation '~' in the set I = [0,1) ... while those of the different classes differ by an irrational number. ... Suppose that is disjoint equivalence classes. ...
    (sci.math)
  • Re: Testing for the equivalence relation
    ... >> Here there are 4 equivalence classes and two distinct equivalence ... > There are just two equivalence classes. ... Abiteboul, Hull, and Vianu mention active domains in the context of query ...
    (comp.databases.theory)
  • Re: Side channels in theorems
    ... So where does the rational -> irrational mapping occur? ... one can proof that there is no *rational* number x such that for each precision limit the difference between the series and the number x becomes smaller than this limit if I take just enough terms of the sum. ... shortcut for a complex set of equivalence classes, namely all the series whose difference to the given sequence is a Cauchy sequence. ... This is *not* meant by the notation, you cannot perform an operation an infinite number of times. ...
    (comp.compression)