# Countability Q

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

Is the number of domino tilings of an infinite strip of height 2 countable or uncountable?

Eg. Any sequence of V for vertical domino and H for horizontal domino represents a tiling:

VHHHVHHVHHVHVHVHVVVVVHVVVVHHH....

Are such sequences countable or uncountable?

Eg. Any sequence of V for vertical domino and H for horizontal domino represents a tiling:

VHHHVHHVHHVHVHVHVVVVVHVVVVHHH....

Are such sequences countable or uncountable?

0

reply

Report

#2

(Original post by

Is the number of domino tilings of an infinite strip of height 2 countable or uncountable?

Eg. Any sequence of V for vertical domino and H for horizontal domino represents a tiling:

VHHHVHHVHHVHVHVHVVVVVHVVVVHHH....

Are such sequences countable or uncountable?

**elly17**)Is the number of domino tilings of an infinite strip of height 2 countable or uncountable?

Eg. Any sequence of V for vertical domino and H for horizontal domino represents a tiling:

VHHHVHHVHHVHVHVHVVVVVHVVVVHHH....

Are such sequences countable or uncountable?

Would 3 HHH be allowed in your example, or would they have to occur in pairs?

Edit - what level are you / where does the question come from?

Last edited by mqb2766; 3 weeks ago

0

reply

(Original post by

Maybe start small and think about whether you can produce some form of sequence / pattern which represents the number when the strip is 2, 3, 4, ... long? Can you then argue about the countability (or not)?

Would 3 HHH be allowed in your example, or would they have to occur in pairs?

Edit - what level are you / where does the question come from?

**mqb2766**)Maybe start small and think about whether you can produce some form of sequence / pattern which represents the number when the strip is 2, 3, 4, ... long? Can you then argue about the countability (or not)?

Would 3 HHH be allowed in your example, or would they have to occur in pairs?

Edit - what level are you / where does the question come from?

Sorry I think HHH is a typo - it would only occur in pairs since height is 2.

My maths teacher asked the question (I'm an A-level student)

0

reply

Report

#4

(Original post by

I've figure out that for a strip of n length, the number of domino tilings is the nth term of the Fibonacci sequence since it can only end in either a vertical or 2 horizontal, which would mean 2(n-1) and 2(n-2) domino tilings respectively, so it's just a recurrent series adding the two previous terms. I not quite sure how to argue about the countability or not though?

Sorry I think HHH is a typo - it would only occur in pairs since height is 2.

My maths teacher asked the question (I'm an A-level student)

**elly17**)I've figure out that for a strip of n length, the number of domino tilings is the nth term of the Fibonacci sequence since it can only end in either a vertical or 2 horizontal, which would mean 2(n-1) and 2(n-2) domino tilings respectively, so it's just a recurrent series adding the two previous terms. I not quite sure how to argue about the countability or not though?

Sorry I think HHH is a typo - it would only occur in pairs since height is 2.

My maths teacher asked the question (I'm an A-level student)

Talking about countability ... is unusual at a level. What do you know about it / why did your teacher set the question.

Youre correct about fibonacci - recurrent definition, when the length is finite. Your question is obviously about what happens when the length is infinite. Do you think you can do a (countable) map to the integers, do you think you can do a diagonal-type argument ...?

Last edited by mqb2766; 3 weeks ago

0

reply

(Original post by

Can you upload a picture of the actual question?

Talking about countability ... is unusual at a level. What do you know about it / why did your teacher set the question.

Youre correct about fibonacci - recurrent definition, when the length is finite. Your question is obviously about what happens when the length is infinite. Do you think you can do a (countable) map to the integers, do you think you can do a diagonal-type argument ...?

**mqb2766**)Can you upload a picture of the actual question?

Talking about countability ... is unusual at a level. What do you know about it / why did your teacher set the question.

Youre correct about fibonacci - recurrent definition, when the length is finite. Your question is obviously about what happens when the length is infinite. Do you think you can do a (countable) map to the integers, do you think you can do a diagonal-type argument ...?

He set the question because I'm applying for maths at uni.

With a diagonal-type argument, could you argue that it is countable, since you can only have either vertical or two horizontal, and you can't just take the complement of each alternating tile (vertical/2 horizontal) since vertical goes to 2 horizontal and not to just horizontal? I'm not quite sure

0

reply

Report

#6

(Original post by

Sorry but that's his question word for word - it was emailed to me informally.

He set the question because I'm applying for maths at uni.

With a diagonal-type argument, could you argue that it is countable, since you can only have either vertical or two horizontal, and you can't just take the complement of each alternating tile (vertical/2 horizontal) since vertical goes to 2 horizontal and not to just horizontal? I'm not quite sure

**elly17**)Sorry but that's his question word for word - it was emailed to me informally.

He set the question because I'm applying for maths at uni.

With a diagonal-type argument, could you argue that it is countable, since you can only have either vertical or two horizontal, and you can't just take the complement of each alternating tile (vertical/2 horizontal) since vertical goes to 2 horizontal and not to just horizontal? I'm not quite sure

I dont think that any deep understanding is required here, just the usual countable integers and the uncountable diagonal. Try and work both approaches and see what gives? I dont understand how your diagonal argument would show its countable? To show its countable, youd have to show the patterns can be mapped to the integers. A diagonal type argument would show its uncountable, but you might have to be creative with how to flip the bits on the diagonal. Either way ...

Last edited by mqb2766; 3 weeks ago

0

reply

(Original post by

Why not think a bit more/write up your ideas better and post them? The more thinking you put into it, the better you'll understand which approach works as well as which ones dont. The latter are arguably more important as you better understand the problem and rather than just quoting a result youd had help with, youd have a more rounded story about what you tried, why it didnt work, .... If its informal background work, you dont have a specific deadline I guess?

I dont think that any deep understanding is required here, just the usual countable integers and the uncountable diagonal. Try and work both approaches and see what gives? I dont understand how your diagonal argument would show its countable? To show its countable, youd have to show the patterns can be mapped to the integers. A diagonal type argument would show its uncountable, but you might have to be creative with how to flip the bits on the diagonal. Either way ...

**mqb2766**)Why not think a bit more/write up your ideas better and post them? The more thinking you put into it, the better you'll understand which approach works as well as which ones dont. The latter are arguably more important as you better understand the problem and rather than just quoting a result youd had help with, youd have a more rounded story about what you tried, why it didnt work, .... If its informal background work, you dont have a specific deadline I guess?

I dont think that any deep understanding is required here, just the usual countable integers and the uncountable diagonal. Try and work both approaches and see what gives? I dont understand how your diagonal argument would show its countable? To show its countable, youd have to show the patterns can be mapped to the integers. A diagonal type argument would show its uncountable, but you might have to be creative with how to flip the bits on the diagonal. Either way ...

Since it needs to be mapped both one-to-one and onto the natural numbers in order for it to be countable, I don't think it is, since when we have the two horizontal tiles, it won't be mapped one-to-one as the horizontal tiles have to be in pairs in order for the tiling to work.

With the diagonal argument, could we say its uncountable if for every V we use HH, and for every H we use a V?

0

reply

Report

#8

(Original post by

The deadline is tomorrow for our extension maths class...

Since it needs to be mapped both one-to-one and onto the natural numbers in order for it to be countable, I don't think it is, since when we have the two horizontal tiles, it won't be mapped one-to-one as the horizontal tiles have to be in pairs in order for the tiling to work.

With the diagonal argument, could we say its uncountable if for every V we use HH, and for every H we use a V?

**elly17**)The deadline is tomorrow for our extension maths class...

Since it needs to be mapped both one-to-one and onto the natural numbers in order for it to be countable, I don't think it is, since when we have the two horizontal tiles, it won't be mapped one-to-one as the horizontal tiles have to be in pairs in order for the tiling to work.

With the diagonal argument, could we say its uncountable if for every V we use HH, and for every H we use a V?

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top