elly17
Badges: 7
Rep:
?
#1
Report Thread starter 3 weeks ago
#1
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?
0
reply
mqb2766
Badges: 19
Rep:
?
#2
Report 3 weeks ago
#2
(Original post by 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?
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?
Last edited by mqb2766; 3 weeks ago
0
reply
elly17
Badges: 7
Rep:
?
#3
Report Thread starter 3 weeks ago
#3
(Original post by 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?
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)
0
reply
mqb2766
Badges: 19
Rep:
?
#4
Report 3 weeks ago
#4
(Original post by 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)
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 ...?
Last edited by mqb2766; 3 weeks ago
0
reply
elly17
Badges: 7
Rep:
?
#5
Report Thread starter 3 weeks ago
#5
(Original post by 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 ...?
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
0
reply
mqb2766
Badges: 19
Rep:
?
#6
Report 3 weeks ago
#6
(Original post by 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
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 ...
Last edited by mqb2766; 3 weeks ago
0
reply
elly17
Badges: 7
Rep:
?
#7
Report Thread starter 3 weeks ago
#7
(Original post by 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 ...
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
mqb2766
Badges: 19
Rep:
?
#8
Report 3 weeks ago
#8
(Original post by 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?
Sounds like youve got a reasonable idea so just go with that tomorrow.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

How are you feeling now you've started university?

I'm loving it! (57)
14.69%
I'm enjoying it but I'm still settling in (98)
25.26%
I'm a bit unsure (67)
17.27%
I'm finding things difficult (132)
34.02%
Something else (let us know in the thread!) (34)
8.76%

Watched Threads

View All