TT's Maths Thread

[TrueTears]

A form of the pigeonhole theorem is stated as "If f is a function from a finite set X to a finite set Y with then for some ,

Now a question says: An inventory consists of a list of 89 items (Listed from 1 to 89), each marked "available" or "unavailable". There are 45 available items, show that there are at least two available items in the list exactly 9 items apart (For example items at position 13 and 22 satisfy the condition).

Now I just don't know how to apply the pigeonhole theorem to this question, what is set X and Y in this case? And what is the function?

[brightsky]

Hmmm...is it supposed to be 46 available items...

Consider the worst-case scenario. We have the list of items:

1, 2, 3, 4, 5, ..., 89

If 1 - 9 were  available, then for the sake of a worst-case scenario, let 19 - 27 be available, then 37 - 45, then 55 - 63, then 73 - 81. (We have 45 available at present, with no pair of numbers exactly 9 apart). Notice that if we pick any number from the remaining numbers, we will get a pair that is exactly 9 apart. So if we have 46 items, then there will be at least two items exactly 9 items part.

[TrueTears]

Hmm says 45


The solutions do it like this:

Let X be the set of the positions of the available items and those items who are 9 items away from it.

Let a_i denote the position of the ith available item.

X = {a_1, a_2, ... , a_45, a_1+9, a_2+9, ... , a_45+9}

|X| = 90

Now let Y be the set of the 89 items.

Y = {1, 2, ... , 89}

|Y| = 89

Since |X| > |Y| Using the second form of the pigeonhole theorem (which is the form I stated above) we have a_i = a_j+9 for some i,j.

Thus a_i-a_j = 9 so 2 available items are 9 items away.


The solutions make perfect sense, and so does your way, so again where is the fallacy? I can't see it ><

[pooshwaltzer]

TT,

Your "fallacy" may be in the assumption of fixed permutation. Who's to say order of precedence was necessary?

E.G. For items A and B where both denote available; there are 2 outcomes

A,1,2,3,4,5,6,7,8,9,B

B,1,2,3,4,5,6,7,8,9,A

[TrueTears]

Hmm I see, thanks for that, but I think I made the mistake of assuming the course numbers (from 1 to 300) are ONLY for computer science, rather they can be for other courses too, maybe commerce etc. So since the course numbers are not only for computer science, you can not place the course numbers (pigeons) into the 151 computer courses (pigeonholes) because the course numbers may not all be 'pigeons', eg, only the course numbers which are for computer science are pigeons, the rest are 'chickens' and you can stuff chickens into pigeonholes lol

does that even make sense...?

[brightsky]

Yeah I think that's one way of interpreting it. :p

So the question would be something like: there are 300 courses, numbered in order from 1 to 300, of which 151 are computer science courses. Show that there must be at least two pairs of computer science courses that are next to each other in the aforementioned order.

Generally speaking, the pigeons are the "selected" items you are dealing with, or rather, the things you are focussing on. If you have a question like: There are 21 points on a circle of radius 10, prove that there must be at least one pair of points that are blah blah blah. Then the pigeons would be the 21 points. If you have something like: Jimmy selected 60 numbered balls at random from a bag of 100 number balls, prove that blah blah blah, then the pigeons would be the 60 balls.

The pigeonholes on the other hand are constructed from the other information that you are given, and you need to construct your holes so that it "works".

Lol, hope this makes sense.

[TrueTears]

haha yeah i like your explanation, thanks i think i have a much better idea how to tackle these problems now they have always been one of my weak points, like what do i assign the pigeons/pigeonholes to lol.

thanks again

[brightsky]

No probem.

[TrueTears]

Find a recursive relation for the number of distinct ordered pairs (a,b) of non-negative integers satisfying 2a+5b=100.

Okay, so I took an entirely different approach to this question using generating functions unlike my book.

Let be the number of nonnegative ordered pairs which solve .

We define and

Now

Clearly, A(x)B(x) is the generating function sequence for the sequence





We can see from inspection that and

But up to this step, I have no idea how to get the recursive relation for

[Ahmad]

Due to the specially chosen numbers it really is easier to just do it the 'standard' way.

But you asked for a recursion:





Combinatorial interpretation: To make up n cents using 2 and 5 cents you can either choose 2 cents and count the number of ways of making n-2 cents, or 5 cents and count the number of ways of making n-5 cents, but then you'll have double counted if you chose 2 cents then 5 cents, or 5 cents then 2 cents, so you subtract the number of ways to make n-7 cents.

[TrueTears]

Due to the specially chosen numbers it really is easier to just do it the 'standard' way.

But you asked for a recursion:





Combinatorial interpretation: To make up n cents using 2 and 5 cents you can either choose 2 cents and count the number of ways of making n-2 cents, or 5 cents and count the number of ways of making n-5 cents, but then you'll have double counted if you chose 2 cents then 5 cents, or 5 cents then 2 cents, so you subtract the number of ways to make n-7 cents.

Hey Ahmad, thanks for the help, I'm still unsure how you went from to the recursive relation, can you explain?


Nvm, thanks I got it

[TrueTears]

A domino is a rectangle divided into two squares with each square numbered one of 0,1,2,3,4,5,6. Two squares on a single domino can have the same number. Show that distinct dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers.

This is how I interpreted this question. But the solution says something else and I don't know how they got it.

This is my graph



Now we can turn this into a graph, G, by letting the dominoes be the edges and each of the numbers be vertices.

Clearly, G is a connected graph and each vertex's degree is 2. Thus G has a Euler's cycle, therefore the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers.

Now the solutions says this: (My questions are in brackets)

"We model the situation as a graph G with seven vertices labeled 0,1,2,3,4,5,6. The edges represent the dominoes. There is one edge between each distinct pair of vertices (Why do you connect every single vertex to each other?) and there is one loop at each vertex (Why do you have a loop at each vertex?). Notice that G is connected. Now the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers iff G contains an Euler cycle (Why does G have to contain an Euler cycle so that adjacent squares will have identical numbers?). Since the degree of each vertex is 8, then G has an Euler cycle. Therefore, the dominoes can be arranged in a circle so that touching dominoes have adjacent squares with identical numbers."

Many thanks.

[TrueTears]

I'm confused about the definition of a Euler cycle, my book says "a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler cycle"

However on wikipedia it says "An Eulerian cycle, in an undirected graph is a cycle that uses each edge exactly once."

Which one is it?

If it is the latter, then is it possible to travel all the edges once and touch every vertex (not necessarily once) given the graph G has a Euler cycle?

[pooshwaltzer]

Which one is it?

Definition: A path through a graph which starts and ends at the same vertex and includes every edge exactly once.

Read the sentences again TT, they are actually both correct, ie. stating the same thing but from different priors.

[TrueTears]

But using each edge once doesn't mean you have to touch every vertex.

So saying "A cycle in a graph G that includes all of the edges and all of the vertices in G" is very different from saying "A cycle that uses each edge exactly once"

I illustrate in my graph attached.

It contains a cycle that uses each edge exactly once, namely (1,5,6,4,1,3,6,1), but doesn't touch the vertex 2.