A new language is created that only uses the letters A, B, C, D, and E. A sequence of letters is called a word if it does not include the same letter twice in a row, and it does not include two vowels in a row. How many words are there in this language that are 10 letters long and that begin with a vowel?
How does Veeky Forums solve this?
Other urls found in this thread:
gist.github.com
gist.github.com
ghostbin.com
gist.github.com
youtube.com
ghostbin.com
twitter.com
by writing all the possible words and counting.
i really hate combinatorics problems
0 . You can't have words 10 letters long with no repeats allowed and only 5 letters...
This
i really hate problems
Proof that Veeky Forums is retarded and in denial. This problem is from a 6th grade math exam.
Lmao so easy it's 5x4^9
>A sequence of letters is called a word if it does not include the same letter twice in a row, and it does not include two vowels in a row.
lol no
So basically none of the letters repeat. My answer is correct, actually.
no please tell me you are trolling
Spotted the humanities retard.
lrn2formal languages or gb2/lit/
pls accept the fact that the letters can be used over again
> making 10 letter words from only 5 distinct letters
5 reusable letters
Nah it's clearly the other way.
The answer is 0 OP
a=2*3*b
b=2*c+2*3*d
c=2*d+2*3*e
...
i=2*j+2*3
j=5
Evaluate a
Something like that
pull the lever, they die twice as fast so suffer half as much.
Let
v(n) be the number of words that start with a vowel and end with a vowel.
c(n) be the number of words that start with a vowel and end with a consonant.
Then
v(1) = 1
c(1) = 0
v(n+1) = v(n) + 2*c(n)
c(n+1) = 3*v(n) + 2*c(n)
Written as matrix this is
[eqn] \left( \begin{matrix} v(n+1) \\ c(n+1) \end {matrix} \right) = \left( \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right) \left( \begin{matrix} v(n) \\ c(n) \end {matrix} \right) [/eqn]
So the solution is
[eqn] v(10) + c(10) = \left( \begin{matrix} 1 & 1 \end {matrix} \right) \left( \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right)^{9} \left( \begin{matrix} v(1) \\ c(1) \end {matrix} \right) [/eqn]
Answer is 36455768
Let:
P_i = {w | w has a length w_i}
R = {w |w has no two vowels in a row, and no two same letters in a row}
Q = {w |w begins with a vowel}
n_i = card (Pi && R && Q)
m_i = card (Pi && R && not Q)
i.e.
n_i is the number of such words of length i beginning with a vowel
m_i is the number of such words of length i beginning with a consonant
n_1 = card {A,E} = 2
m_1 = card {B,C,D} = 3
And:
n_i = 2*m_(i-1) + n_(i-1)
m_i = 5*(m_(i-1) + n_(i-1))
i.e.
m_2 = 25
n_2 = 8
m_3 = 165
n_3 = 58
m_4 = 1115
n_4 = 388
m_5 = 7515
n_5 = 2618
m_6 = 50665
n_6 = 17648
m_7 = 341565
n_7 = 118978
m_8 = 2302715
n_8 = 802108
m_9 = 15524115
n_9 = 5407538
m_10 = 104658265
And our final result: n_10 = 36455768
--
FistiSWAG, École Normale Supérieure du SWAG
>Solution larger than 2*5^9
You can't be serious.
MULTI
TRACK
DRIFTING
But [math]/omega * 2[/math] is still much, much less than uncountably many people. I don't think you can even have uncountably many people on the track when you can clearly, well, count them.
I got halfway through the problem before I gave up.
I plotted out the first part of the problem in pic related
(empty circle is the start, red circles are vowels, black circles are consonants)
The first part is simple enough
from the start, you have 2 options, a or e. From each of those nodes, you have 3 options, the 3 consonants, since you cant have two vowels. So it's 2*3 for words of length 2.
From there, those nodes branch out into 4 i.e. any letter other than itself. So for words of length 3, it's 2*3*4
This is where I'm stuck.
The branching degree of the next level varies because there are 12 vowel nodes that expand into 3, and 12 consonant nodes that branch into 4. (12*3)+(12*4) makes for 84 branches total. So if 24 nodes branch of in 84 directions, that gives an average branching factor of 84/24 = 3.5
The ratio of red vowel nodes to black consonant nodes keeps changing. Just by hand counting, I can see the average branching is approx 3.71428
I don't know where to go from here.
I've never dealt with combinations where the branching varies.
>no repeats
>in a row
ABABABCDE
2*(2^3+2^4+2^4+2^4+2^4+2^4 + 2^4 + 2^4 + 2^4 + 2^4) = 304
only correct solution
There is 199776 of them.
No real solution, just calculated it programmatically.
gist.github.com
I would create an adjacency-matrix and multiply it with itself 10 times and finally sum all elements in that matrix. Something along those lines should give all possible words in that language
>6th grade math
But it's not. It's a combinatorics problem whose answer is a large number. 0/10
Where's multi track drifting?
...
Why would anyone pull the lever? I'm saving 100% of the people in the pic by not pulling it.
Correct answer
Easier programmable way to do this however, here it is in rust. It gets the answer recursively.
and here is my c++ solution:
ghostbin.com
it's still running by the time I post this so I don't know if it works jet
I forgot that it has to beginn with a vowel
>using a function call for CtoI instead of a #DEFINE
pleb
Aleph_0 and Aleph_1 are ordinalities not cardinalities. I don't think this question is well posed.
Here is the corrected version of Let
v(n) be the number of words of length n that start with a vowel and end with a vowel.
c(n) be the number of words of length n that start with a vowel and end with a consonant.
Then
v(1) = 2
c(1) = 0
v(n+1) = 2*c(n)
c(n+1) = 3*v(n) + 2*c(n)
Written as matrix this is
[eqn] \left( \begin{matrix} v(n+1) \\ c(n+1) \end {matrix} \right) = \left( \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right) \left( \begin{matrix} v(n) \\ c(n) \end {matrix} \right) [/eqn]
So the solution is
[eqn] v(10) + c(10) = \left( \begin{matrix} 1 & 1 \end {matrix} \right) \left( \begin{matrix} 0 & 2 \\ 3 & 2 \end{matrix} \right)^{9} \left( \begin{matrix} v(1) \\ c(1) \end {matrix} \right) = \left( \begin{matrix} 1 & 1 \end {matrix} \right) \left( \begin{matrix} 35328 & 43040 \\ 64560 & 78368 \end{matrix} \right) \left( \begin{matrix} 2 \\ 0 \end {matrix} \right) = 199766 [/eqn]
The trolley kills -1/12 people in both scenarios, so it doesn't really matter.
This is incorrect. My bad.
Nice one.
>Easier
Well, my was brute force. To come up with your solution you had to think a little.
But these matches are bad. You don't need to write return in last statement of function and you don't need to use these unreadable ifs inside match.
gist.github.com
>using new for tables instead of Vector
>{ 'A', 'B', 'C', 'D', 'E' }; instead of "ABCDE";
>C-like fors instead of C++14 for-in
>generating, storing in huge array and then checking all words instead of doing it while generating
>while(true) without thread yield insdie
user, what the fuck.
as you may have noticed I'm new in c++
what is thread yield and what is wrong with my for loops?
(the array thing doesn't make it slower does it?)
while (1) {} can potentially max a core out at 100%, don't do that
You should never use `new` and `delete` in C++ unless you know absolutely what you are doing. You should use shared/unique pointers and/or Vector and/or Array. It will prevents all memory and resource leaks and RAII is much more safer and easier to do.
Your for loops looks ugly and are very vulnerable to bugs.
for(auto el : v){ ...
is more readable and easier than
for(int i=0; i
Also it seems you learned C++ from someone/book who doesn't understand C++11.
Go watch:
youtube.com
And then read Meyers S - Effective Modern C++ if you want to use C++ at its full potential.
while(1){} gets removed and similar things get optimized by any compiler from this century
No it doesn't...
thank you very much guys here is the updated code (it only takes like 27s now before it took like 7min)
ghostbin.com
I can't get the new for loop working and I'm self-teaching myself sooo...
use the optimization flags then. -o2 is sensible in G++
Are you blind or retarded?
Tell me what, exactly, would while (1) {} "optimize" to?