FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
graph theory
Post new topic   Reply to topic Page 1 of 2 [20 Posts] View previous topic :: View next topic
Goto page:  1, 2 Next
Author Message
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Jul 16, 2006 4:34 am    Post subject: Re: Combinatorics Reply with quote

Thomas Mautsch wrote:
Quote:
In news:<1152934283.850075.249680@b28g2000cwb.googlegroups.com
schrieb Proginoskes <CCHeckman@gmail.com>:
Whatever5k@web.de wrote:

Suppose you have n fields, where n is at least 10. Each field is to be
filled with a ball. There are infinitely many balls, but they can be
distincted by their colour. In total there are 10 different colours. So
now, you want to find out how many distinct possibilities there are to
fill the n fields with those balls. There are, however, two conditions:
a) at the end, each colour has to appear at least once
b) the first field cannot contain the colour blue

Any idea how to tackle this?
I am an absolute beginner in combinatorics.
Please help.

The answer should be "infinitely many possibilities". You should check
the wording of the problem.

From what can be gathered from the OP's postings in de.sci.mathematik,
the problem is to determine the number of n-digit decimal numbers
with first digit different from zero
that contain each of the ten digits 0,1,2,3,4,5,6,7,8,9 at least once.

I don't see this at all. _IF_ there was a condition that stated each
field had to have at most one ball, then that would be the case. But as
I read the question, the following are all solutions to the problem,
for any nonnegative integer K: (where 0 = "blue")

Field 1: Infinitely many balls of colors 1 ... 9,
Field 2: Infinitely many balls of color 0, K balls of color 1,
Fields 3-n: Empty.

This satisfies conditions (a) and (b). If fields aren't allowed to be
empty, put an infinite number of balls of color 1 in fields 3-n.

That was what I was asking clarification about.

--- Christopher Heckman
Back to top
Rich Holme
science forum beginner


Joined: 06 Jun 2005
Posts: 45

PostPosted: Mon Jul 10, 2006 2:24 pm    Post subject: Re: arithmetic Robak 0,(9)+{1+}0=1 Time Theory Reply with quote

dbd@gatekeeper.vic.com (David DeLaney) writes:

Quote:
ks-robak <ks-robak@o2.pl> wrote:
Rich Holmes <rsholmes+usenet@mailbox.syr.edu
And why, WHY, has this information been withheld from a.r.k until now?
[Rich Holmes]

Manley Hubbel had a kid?

~~~~~~~~~~~~~~~~~~~~~~~~
X + oo = oo <== religion
X + oo = X + oo <== LOGIC
~~~~~~~~~~~~~~~~~~~~~~~~

X + oo = oo ; oo + X = oo + X <== ordinal transfinite arithmetic
* <== PERTH

A=A

Dave "time=inertia?" DeLaney

Ah yes, I remember that post. Good times, good times.

--
- Doctroid Doctroid Holmes <http://www.richholmes.net/doctroid/>
Ancient use of incendiary pigs as an anti-elephant measure is
disqualified on grounds of pigs not being cows, even when on fire.
-- John D Salt
Back to top
David DeLaney
science forum beginner


Joined: 08 May 2005
Posts: 20

PostPosted: Sat Jul 08, 2006 4:28 pm    Post subject: Re: arithmetic Robak 0,(9)+{1+}0=1 Time Theory Reply with quote

ks-robak <ks-robak@o2.pl> wrote:
Quote:
Rich Holmes <rsholmes+usenet@mailbox.syr.edu
And why, WHY, has this information been withheld from a.r.k until now?
[Rich Holmes]

Manley Hubbel had a kid?

Quote:
~~~~~~~~~~~~~~~~~~~~~~~~
X + oo = oo <== religion
X + oo = X + oo <== LOGIC
~~~~~~~~~~~~~~~~~~~~~~~~

X + oo = oo ; oo + X = oo + X <== ordinal transfinite arithmetic
* <== PERTH

Quote:
A=A

Dave "time=inertia?" DeLaney
--
\/David DeLaney posting from dbd@vic.com "It's not the pot that grows the flower
It's not the clock that slows the hour The definition's plain for anyone to see
Love is all it takes to make a family" - R&P. VISUALIZE HAPPYNET VRbeable<BLINK>
http://www.vic.com/~dbd/ - net.legends FAQ & Magic / I WUV you in all CAPS! --K.
Back to top
BDH
science forum beginner


Joined: 25 Oct 2005
Posts: 11

PostPosted: Thu Jun 29, 2006 10:06 am    Post subject: Re: Combinations satisfying linear equations? Reply with quote

Exactly.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Mon Apr 03, 2006 6:08 am    Post subject: Re: Help in solving this puzzle Reply with quote

Michael Harrington wrote:
Quote:
"James Waldby" <j-waldby@pat7.com> wrote in message
news:442CDE7C.89CBBFB4@pat7.com...
Michael Harrington wrote:
"john@x" ... wrote ...
There is a lottery drawn on 1 through 20 numbers and six distinct balls
are randomly picked by the lottery every day. To play you need to buy a
ticket and select six numbers of your choice. An example ticket might
be [1,20,6,19,5,12] You can buy any number of tickets. If any three of
the numbers in one of your tickets are among the six winning numbers
picked by the lottery, in any order then you win.
What is the minimum number of tickets you have to buy to be certain of
winning with atlease one?
...
Now for your stated 20 numbers we have 10 blocks of 2
{1,2} {3,4}.............{17,18}{19,20}
This will equate to 10C3 = 120 tickets.
This is unproven as the minimum, but it is some partial solution.
Would be interested to see any improvement on this.
This is not the simplistic problem others are making it out to be.

You need to cover at least 17 of the numbers to force a win,
not 20 of them. Rather than 10C3 tickets your scheme should
need somewhere between 8C3 and 9C3, ie, between 56 and 84.

Return on investment might be better or worse with your 120-
ticket scheme vs. an 84-ticket one, depending on how many of
the 20 (6C3) winning triples occur on distinct tickets.
Having multiple winning triples on some tickets will decrease
the total payoff if each winning ticket pays only once.

-jiw

Good point on only covering 17 numbers. Would be good to
know if there is a mathematical method of finding the minimum
number of covering tickets.

The problem clearly belongs in the field of combinatorics. If you want
every triple to be in exactly K tickets, then you're in the area of
design theory/t-designs.

--- Christopher Heckman
Back to top
Richard Reddy
science forum beginner


Joined: 16 Nov 2005
Posts: 1

PostPosted: Wed Nov 16, 2005 5:33 am    Post subject: Re: > Challenge Reply with quote

The statistics on child mortality for AIDS are fairly accurate, but the
"third world" depends on who you talk to. We have underdeveloped nations
in Africa, Asia and Latin America. Many developed nations also have
AIDS epidemics, including the USA. There is substantial margin for error in
the business of counting deaths for epidemics of all kinds. We also find
politics in official numbers, which are frequently wrong.

The issue of quality of life for people infected with AIDS is even
more tragic, given the high cost of drugs proven to be effective. The
poorest
nations are simply helpless in the face of this epidemic, lacking medical
infrastructure, public health education, or the ability to assist sick and
disabled people.

In my opinion, the age of AIDS victims is irrelevant. We should endeavor
to assist any nation or state unable to cope with this pandemic. It's the
human thing to do, whatever we think of particular statistics. The
suffering
is real and the AIDS epidemic is enormous. So too are millions of deaths
that might have been delayed by years or decades with appropriate medical
intervention.

I offer another challenge. Find a reputable organization and try to
be of help in some way. An organization can be in error with statistics,
but still be highly effective in delivering assistance, a process that
frequently
involves danger and hardship. There are many wonderful people stretched
out beyond reckoning in combating this global menace. You will find many
charities who hire "pros" to raise money, sometimes with questionable
tactics
or poor percentages reaching the intended recipients. By law, this
statistics
are public information.

Apathy is certainly a dangerous condition. I know little about this
organization,
but there are many putting their whole heart into the effort to fight this
epidemic.

If you want to hang your hat on some real statistical offenders, try the
antismoking crew. Prohibitionists love to exaggerate. For example, public
adds that say each cigarette shortens your life by 5 minutes.






<dsaklad@zurich.csail.mit.edu> wrote in message
news:1117871877.716280.18410@o13g2000cwo.googlegroups.com...
Quote:
Path: grapevine.lcs.mit.edu!newsswitch.lcs.mit.edu!
bloom-beacon.mit.edu!newsfeed.stanford.edu!



postnews.google.com!news4.google.com!news.glorb.com!



sn-xit-04!sn-xit-12!sn-xit-01!sn-post-01!supernews.com!



corp.supernews.com!not-for-mail
From: "PaulKing" <aimulti at aimultimedia.com
Newsgroups: misc.health.aids
Subject: Challenge
Date: Fri, 03 Jun 2005 19:51:13 -0400
Organization: www.talkabouthealthnetwork.com
Message-ID: <431b337a0657600e87b4f777796371e2 at
localhost.talkabouthealthnetwork.com
X-Newsreader: www.talkabouthealthnetwork.com
X-Problems-To: info at talkaboutnetwork.com
X-Posted-By: USERID-7496
Content-Type: text/plain;
X-Complaints-To: abuse at supernews.com
Lines: 28
Xref: grapevine.lcs.mit.edu misc.health.aids:98998

CHALLENGE TO BELIEVERS

If anyone still believes 'AIDS' statistics, let them answer
just this one question.

The high budget apathykills.org TV commercial claims 25 million
children in the Third World have died of 'AIDS'.

The UN figures (see graph from them I posted above) says that
ONLY 3% of child mortalities in the Third World are from
'AIDS'.

If 3% = 25 million then 100% must = 832.5 million.

If nearly ONE BILLION children in the Third World have died
then how come the population growth is at an all time high.

ONE BILLION DEAD CHILDREN would almost mean every child in
Africa and India is dead.

Explain this and you can still believe 'AIDS' figures.

Fail to do so and you must admit 'AIDS' figures are TOTAL
GARBAGE.
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 5:56 pm    Post subject: Re: graph theory Reply with quote

amanda.pascoe@gmail.com wrote:
Quote:
11.

sketch pf:
A well-known fact in graph theory is the theorem that the sum of the
degrees of the vertices of G is equal to twice the number of edges
(imagine adding the number of edges leaving each vertex. When all
vertices are accounted for, each edge has been counted twice). Then by
assumption the sum of the degrees of V(G) is greater than or equal to
3p, so p is less than or equal to 2*|E(G)|/3.

p<=2*(17)/3<=11.333...

p is an integer, so the maximum value for p is 11.


This establishes the upper bound for p.
To complete the proof, all we have to show is that there exists a
solution for p = 11.

Start with an 11-gon (which uses 11 of our edges), and label the
vertices 0,...,10 in order. Ignoring the points 0,5,10 for a moment,
draw the edges that are equivalent mod 5... so 1 connects to 6, 2
connects to 7, etc. There are 4 of these so we have used 15 edges total
and each of these 8 vertices has degree 3. We then connect 0 to both 5
and 10 (17 edges total) to give 5 and 10 degree 3 and 0 degree 4.

- Matt
Back to top
Woeginger Gerhard
science forum beginner


Joined: 30 Jul 2005
Posts: 5

PostPosted: Tue Aug 16, 2005 8:30 am    Post subject: Re: Integer Optimization Problem P+p(j)/C+c(j) Reply with quote

unix68 <unix68@networld.at> wrote:
# Hi,
# I need help for solving the following problem (references to
# algorithms and papers).
#
# Given:
# P, p1,p2,...,pn all integers
# C, c1,c2,...,cn all integers
# P = constant
# C = constant
#
# Goal:
# maximize [P+sum(pj)]/[C+sum(cj)] for any j=1..n
#
# This means we have to find the optimal subset of elements
# out of a given set (1...n) such that the ratio
# [P+sum(pj)]/[C+sum(cj)] gets maximal.


In case all c1,...,cn are NON-NEGATIVE integers,
your problem is polynomially solvable. (There is
a direct solution via sorting, you do not even
need fractional programming.)

In case c1,...,cn are ARBITRARY integers,
your problem is NP-hard. (By a reduction from
subset sum.)

--Gerhard

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
Back to top
Guest






PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

Well, yeah, actually a "trivial" lower bound can be derived easily.

Consider all k-sets of [1..n], we have totally

{n choose k} such sets.

and each coloring is going to color at most

(n/k)^k

of them. Therefore another lower bound should be

{n choose k}/(n/k)^k

with stirling's approximation, we can easily get a lower bound of

e^k, when n/k is large enough.

Nice day.Smile
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

fhzhang@gmail.com wrote:
Quote:
I tried some simple cases, your result seems correct.

I really appreciate your help. Nice weekend.Smile

This problem looks like it's going to be a difficult one in general.

I did some reading through the literature earlier today (Monday), and I
found some papers related to the problem, which evidently goes by the
name of Perfect Hashing. (Colorings which color all the vertices in a
set of size k with different colors are sometimes called "Anti-Ramsey
Colorings." You may also want to search for related papers on this
subject.)

Some of the titles are incomplete, but once you find the appropriate
journal, you'll see what the rest of them are.

(1) M. Fredman, J. Komlos, "On the size of separating ...", SIAM
Journal of Algebraic and Discrete Methods 5 (1984), 61-68.

(2) J. Korner, K. Marton, "New bounds ...", European Journal of
Combinatorics 9 (1988), 523-530.

(3) J. Korner, G. Simonyi, "Trifference", Studia Sci. Math Hungar 30
(1995), 95ff.

(4) S. Blackburn, "Perfect Hash Families ...", Journal of Combinatorial
Theory Series A 92 (2000), #1, 54-60.

(5) D. Deng, D. Stinson, R. Wei, "Lovasz's local lemma ...", Designs,
Codes, and Cryptography 32 (2004), #1-3, 121-134.

Unfortunately, (3) and (5) weren't in the ASU library. Paper (4) gives
the best bounds, as well as some constructions, and (2) is also worth
checking into.

--- Christopher Heckman
Back to top
Guest






PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

That's what I was thinking too. This problem seems well-defined and
should have been studied.

Write to you later.

Fenghui
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

fhzh...@gmail.com wrote:
Quote:
Great, thank you very much Mr. Heckman.

I will look into your proof carefully. Can I write to you
later?

Yes. My "professional" e-mail address is checkman@math.usa.edu.
(Actually, you need to reverse the orders of the letters in USA; this
is to throw off spambots.)

I can't shake the feeling that someone has answered this problem
before, though, and written a paper about it.

--- Christopher Heckman
Back to top
Guest






PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

I tried some simple cases, your result seems correct.

I really appreciate your help. Nice weekend.Smile
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: Combinatorics question. Reply with quote

Binesh Bannerjee wrote:
Quote:

But, say I wanted the number of ways to pick _3_ items
from there?
How would I get that number, with 2A's, 3B's and 4C's?
(Or more basically, for a group consisting of any number
of items, with any number of those items possibly repeated,
how do I find the number of ways of picking n items, with
order being significant.)

I can see that AABBBCCCC empirically can have 26 possible
ways of picking 3 items. I can see that's because it's
3^3-1, with the -1 being the possibility of picking 3
A's... But, I'm not sure how to genericize the calculation,
which is what I'm after. (for instance, it's less easy for
me to see how to calculate that to pick _4_ items from
there, would have 71 possible ways, even tho, I can
enumerate those...)

Cross-posted to alt.sci.math.combinatorics ...

(I thought I had an answer, but I realized it doesn't work.)
--- Christopher Heckman
Back to top
Guest






PostPosted: Tue Jul 05, 2005 9:32 pm    Post subject: Re: An interesting coloring problem, can anyone help? Reply with quote

Sorry I made a mistake,

ln(n/(k-1))/ln(k/(k-1))=(ln(n)-ln(k-1))/(ln(k)-ln(k-1))<ln(n)/ln(k)=log(n,k)


is not correct. But still when n=6,k=4, we have

ceil(ln(n/(k-1))/ln(k/(k-1)))=3

Three colorings are not enough do distinguish all 4-subsets of a 6-set.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 2 [20 Posts] Goto page:  1, 2 Next
View previous topic :: View next topic
The time now is Thu Oct 19, 2017 2:37 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts unified theory gb6724 New Theories 4 Fri Jul 21, 2006 5:25 am
No new posts Signal Nonlocality Loophole in Quantum Theory? Jack Sarfatti Math 0 Thu Jul 20, 2006 1:59 am
No new posts A Combinatorics/Graph Theory Question mathlover Undergraduate 1 Wed Jul 19, 2006 11:30 pm
No new posts A Combinatorics/Graph Theory Question mathlover Math 2 Wed Jul 19, 2006 11:02 pm
No new posts A Combinatorics/Graph Theory Question mathlover Combinatorics 0 Wed Jul 19, 2006 10:58 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0597s ][ Queries: 16 (0.0341s) ][ GZIP on - Debug on ]