Original Post
🔒 Locked
f(n)
Advertisement
This isn't actually my first post. I had an account under Zido, but when I returned to these forums, I found out the passwords were wiped due to someone attempting to hack the database. Haven't been here in forever. When I tried to recover for a new password, I found out that there was no email connected to my old Zido account. I've been trying to get access to a moderator for help, but no luck. So I just made a new one.
5!
Quote:
Original post by Zido_Z
lol No, it's a riddle.
But it looks EXACTLY like homework. A math question, looking like it comes right out of a textbook, with no connection back to the core subject of the forums. Please do not post riddles without saying what you are doing. If I had seen the post before the follow-on discussion, the thread would have been closed immediately. Read the Forum FAQ for more information.
Quote:
Original post by Lord Crc
I must admit I'm not getting this at all. What prevents f(n) = 1 for all n?
Nothing, but in that case the sequence will only contain one item.
Quote:
Original post by grhodes_at_work Quote:
Original post by Lord Crc
I must admit I'm not getting this at all. What prevents f(n) = 1 for all n?
Nothing, but in that case the sequence will only contain one item.
Actually, it violates "contains exactly f(n) occurrences of n for each positive integer n" for n=1. Since f(1) is 1, there should be exactly 1 occurrence of 1.
Ok, so this is how I figured it out...
We know f(1)=1, meaning there is exactly one occurrence of 1. The first element of the sequence is 1, and since we know this is the only occurrence, the next element has to be 2 (since the sequence is also non-decreasing, and we need to have at least a single 2, since f(n) is positive). The second element is also f(2), so right away we know f(2)=2. Thus there has to be another 2 in the list. It must come after the first 2, since if we were to jump to 3, or any value greater than 2, then there would only be one occurrence of 2 in the sequence, and since the sequence can never decrease back down from 3 or greater, we violate f(2)=2 which says there must be two occurrences of 2. So thus far we have (1,2,2,...). The third element is f(3), so we have f(3)=2. The same rule applies from before, and we get the sequence (1,2,2,3,3,...). We see that f(4)=3 and f(5)=3, and from there we can extend the sequence to (1,2,2,3,3,4,4,4,5,5,5,...) which is already more than 10 elements, and the 10th element is 5. You can keep generating the sequence like this forever.
I couldn't really be bothered to prove it by induction but I'm sure someone else would be glad to :)
We know f(1)=1, meaning there is exactly one occurrence of 1. The first element of the sequence is 1, and since we know this is the only occurrence, the next element has to be 2 (since the sequence is also non-decreasing, and we need to have at least a single 2, since f(n) is positive). The second element is also f(2), so right away we know f(2)=2. Thus there has to be another 2 in the list. It must come after the first 2, since if we were to jump to 3, or any value greater than 2, then there would only be one occurrence of 2 in the sequence, and since the sequence can never decrease back down from 3 or greater, we violate f(2)=2 which says there must be two occurrences of 2. So thus far we have (1,2,2,...). The third element is f(3), so we have f(3)=2. The same rule applies from before, and we get the sequence (1,2,2,3,3,...). We see that f(4)=3 and f(5)=3, and from there we can extend the sequence to (1,2,2,3,3,4,4,4,5,5,5,...) which is already more than 10 elements, and the 10th element is 5. You can keep generating the sequence like this forever.
I couldn't really be bothered to prove it by induction but I'm sure someone else would be glad to :)
@grhodes_at_work: I apologize if it does. But it was a riddle that a friend came up with, but was never told why it's sequence was (1,2,2,3,... etc). He just gave it to me. I was working like crazy trying to get why 5 was the answer, but my current math skills failed me. So I gave the people here a try to see if they could figure it out, and sure enough, Zipster was capable of working it out.
@Zipster: That's simply amazing. I never would have thought of that. How twisted. So it was basically rooting. Why does this look like recursion to me?
@Zipster: That's simply amazing. I never would have thought of that. How twisted. So it was basically rooting. Why does this look like recursion to me?
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement