Last wins - DPChallenge Forums

01/11/2011 05:12:43 PM · #4676

No no - we're only eager to win. I just won actually - yay!

01/11/2011 05:23:50 PM · #4677

think again Mr. TrollMan!!!

01/11/2011 07:12:21 PM · #4678

yeah, think again. *clank clank clank clank* <-- Monkey Cymbals

01/11/2011 08:10:28 PM · #4679

and again....

01/12/2011 01:57:21 AM · #4680

You have to look at it positively Ken. Everytime you "clank" the cymbals, you jolt forward on your cheeks - towards the goal, albeit turtle speed. You just have to watch out for that wascally wabbit.

01/12/2011 02:20:32 AM · #4681

Originally posted by TrollMan:

You just have to watch out for that wascally wabbit.

What, me worry?

01/12/2011 02:27:48 AM · #4682

Where's the kaboom? There was supposed to be an earth-shattering kaboom!

01/12/2011 02:37:49 AM · #4683

01/12/2011 02:44:45 AM · #4684

Awww - ain't I the cutest little wabbit

01/12/2011 03:27:37 AM · #4685

ROFL! Oh yeah, that's going in my TrollMan collection. I am wallpapering the wall behind my "Last wins" trophy case with those.

bvy

Sigma DP1x

01/12/2011 07:27:22 PM · #4686

Here's an interesting problem.

Let U = {1, 2, 3, ... 10} and define subsets of U as follows:
A1 = {1, 2, 6, 9}
A2 = {2, 7, 8}
A3 = {4, 6, 10}
A4 = {3, 5, 8}
A5 = {6, 7, 9}
A6 = {1, 2, 3, 4, 6}
A7 = {8, 9}
A8 = {1, 2, 6, 10}
A9 = {1, 3, 4, 5, 9}
A10 = {1, 2, 3, 7}
A11 = {2, 4, 6, 7}
A12 = {1, 3, 5}
A13 = {2, 4, 6, 10}
A14 = {5, 8}
A15 = {7, 8, 9}

The problem asks for the minimum number n such that S1, S2, ..., Sn are collections of the subsets of U with the following properties:
1. Each subset Ai of U belongs to exactly one Si (1 <= i <= n).
2. Every two subsets of U which belong to some Si are disjoint.

I decided that this is just a generalization of the scheduling problem and could be modeled with a chromatic graph. The subsets Ai represent the vertices of the graph, we'll call it G, and edges between vertices of G exist if the subsets associated with those vertices are not disjoint (i.e. they share an element). To determine the minimum number n, as the problem asks, is equivalent to finding a minimal coloring of G, or the chromatic number of G. I discovered quickly that it was cumbersome and finally impractical to draw G with all of its edges. So I approached the problem analytically.

Again, we let X(G) represent the chromatic number of the graph G, and d(G) represent the maximum degree of any of the vertices of G. The easiest way to find d(G) is to list each element of U and its number of occurrences in any of the sets Ai. This gives us:

1: 6
2: 7
3: 5
4: 5
5: 4
6: 7
7: 5
8: 5
9: 5
10: 3

The element 1 shows up in exactly six of the subsets, more than any other element. Therefore a vertex associated with a subset containing 1 is adjacent to five other vertices, and d(G) = 5.

We appeal to a result we proved earlier: X(G) <= d(G) + 1. In this case, X(G) <= 5 + 1 = 6, so X(G) <= 6.

Notice, however, that G has K6 as a subgraph, which comes from connecting the six vertices associated with a subset containing 1 -- namely those associated with A1, A6, A8, A9, A10, and A12. For any complete graph on n vertices, X(Kn) = n. So X(K6) = 6, and since K6 is a subgraph of G, X(G) >= 6.

If we take our two results, X(G) <= 6 and X(G) >= 6, clearly X(G) = 6 and six colors are needed to color G.

Hence our minimum number n = 6.

jvaughn94

Canon EOS-1000D Rebel XS

Canon EF 50mm f/1.8 II

01/12/2011 07:35:44 PM · #4687

TL:DR

01/12/2011 08:01:50 PM · #4688

Originally posted by bvy:

01/12/2011 08:29:39 PM · #4689

Evening...everyone playing nice???

Canon EF 24-70mm f/2.8L II

01/12/2011 11:46:25 PM · #4690

When do we not?

bergiekat

Canon EOS-5D Mark IV

01/13/2011 12:57:19 AM · #4691

isn't it past your bedtime?

01/13/2011 01:07:00 AM · #4692

Art doesn't have a bedtime. He's nocturnal.

01/13/2011 01:17:49 AM · #4693

I am omniturnal.

01/13/2011 09:32:19 AM · #4694

Morning...I have a bad headache... :(

01/13/2011 09:45:17 AM · #4695

Originally posted by Ja-9:

Morning...I have a bad headache... :(

Sounds like a standard excuse ;)

01/13/2011 09:50:01 AM · #4696

Originally posted by TrollMan:

Originally posted by Ja-9:
Morning...I have a bad headache... :(

Sounds like a standard excuse ;)

ha...ha...but it hurts...

01/13/2011 09:55:15 AM · #4697

Originally posted by Ja-9:

Originally posted by TrollMan:

Originally posted by Ja-9:
Morning...I have a bad headache... :(

Sounds like a standard excuse ;)

ha...ha...but it hurts...

Well, you know what they say: Love hurts.

01/13/2011 01:03:10 PM · #4698

Finally the headache is gone...yea....BTW..I win...again

bvy

Sigma DP1x

01/13/2011 01:14:33 PM · #4699

Where did my proof go?