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 /sci/ solve this?
>>8058064
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...
>>8058105
This
i really hate problems
>>8058105
Proof that /sci/ is retarded and in denial. This problem is from a 6th grade math exam.
Lmao so easy it's 5x4^9
>>8058121
>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
>>8058130
So basically none of the letters repeat. My answer is correct, actually.
>>8058142
no please tell me you are trolling
>>8058130
Spotted the humanities retard.
lrn2formal languages or gb2/lit/
>>8058165
pls accept the fact that the letters can be used over again
>>8058172
> making 10 letter words from only 5 distinct letters
>>8058185
5 reusable letters
>>8058200
Nah it's clearly the other way.
The answer is 0 OP
>>8058064
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
>>8058284
>Solution larger than 2*5^9
You can't be serious.
MULTI
TRACK
DRIFTING
>>8058064
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.
>>8058105
>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
>>8058294
only correct solution
>>8058064
There is 199776 of them.
No real solution, just calculated it programmatically.
https://gist.github.com/anonymous/542af9ab0287019fac3429f285359bce
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
>>8058427
But it's not. It's a combinatorics problem whose answer is a large number. 0/10
>>8058064
Where's multi track drifting?
>>8058064
>>8058064
Why would anyone pull the lever? I'm saving 100% of the people in the pic by not pulling it.
>>8058388
Correct answer
>>8058388
Easier programmable way to do this however, here it is in rust. It gets the answer recursively.
https://gist.github.com/anonymous/aa63ddafa832ce361161d6909dfd0aa1
and here is my c++ solution:
https://ghostbin.com/paste/z8yyt
it's still running by the time I post this so I don't know if it works jet
>>8059358
I forgot that it has to beginn with a vowel
>>8059358
>using a function call for CtoI instead of a #DEFINE
pleb
Here is the corrected version of >>8058283
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]
>>8058064
The trolley kills -1/12 people in both scenarios, so it doesn't really matter.
>>8059398
This is incorrect. My bad.
>>8059255
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.
https://gist.github.com/e779072068bc5a805630014f10b70fff
>>8059358
>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
Anon, what the fuck.
>>8059479
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?)
>>8059599
while (1) {} can potentially max a core out at 100%, don't do that
>>8059599
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<v.size(); i++){
auto el = v[i]; ...
Using constant instead of v.size is even worse.
Array thing doesn't make it much slower but it makes it use fuck ton of ram.
When you do while(true){} your program will Halt and Catch Fire, ie. will use 100% of processor/core.
You should use while(true){std::this_thread::yield();}. It will tell operating system that you don't have anything to do and will allow other programs to use rest of cpu time.
>>8059619
while(1){} gets removed and similar things get optimized by any compiler from this century
>>8059635
No it doesn't...
>>8059641
I can't get the new for loop working and I'm self-teaching myself sooo...
>>8059640
use the optimization flags then. -o2 is sensible in G++
>>8059657
Are you blind or retarded?
>>8059657
Tell me what, exactly, would while (1) {} "optimize" to?
