11Yup, prophet sir, this was a gr8 "non-routine" prob, even though i cud get nowhere with this, still I enjoyed trying it, waiting for more from ur side.
A row contains 1000 integers
The second row is formed by writing under each integer, the number of times it occurs in the first row
The third row is now constructed by writing under each number in the 2nd row, the number of times it occurs in the 2nd row
This is process is continued
Prove that at some point, one row becomes identical to the next.
[I could give the source too since the author has given a very cryptic clue in place of a solution. Its from Chapter 1 of Problem Solving Strategies by Arthur Engel]
-
UP 0 DOWN 0 0 26
26 Answers
11Prophet sir, pls wait for some-time before giving the soln.....me trying it.
11
1Yeah though it is more of a puzzle, it took in a lot of logic to solve and was a very good one indeed
341yeah. its more of a puzzle. that's what makes it sort of frustrating because there are no expressions to manipulate, no derivatives or integrals to take! The approach to be used is so open-ended.
Unless you play around with some example sequences and make observations you just dont know how to proceed.
But the result obtained is so dramatic, I felt it was worth sparing some thought for it :D
9so this thread ends here :)
but i shud say this is a good Q but not of olympiad level
341Ok the main points to be put together are
1. From 2nd row onwards a number k occurs n times where n is a multiple of k (celestine has already said this)
2. This means that the numbers that appear underneath k in the succeeding row are never less than k.
(Kaymant Sir)
3. If nk represents the number of times the number k occurs then Σnk = 1000 for k appearing in the row.(Celestine)
4. We have said that nk = mkk. The claim is that the rows start to become identical when mk=1 for all k appearing in the row.(Celestine said this, but this has to be spelled out in this way so that we can conclude that:)
This is bound to happen as the numbers in succeeding rows keep increasing. All The coefficients gotta turn out to be 1 at some stage and remain so thereafter.
1say, the numbers are a,c,b,b,c,a,s,g,b,b,f,g,d,s,s,a
the next row will be 3,2,4,4,2,3,3,2,4,4,1,2,1,3,3,3
the third row will be 6,4,4,4,4,6,6,4,4,4,2,4,2,6,6,6
4th row 6,8,8,8,8,6,6,8,8,8,2,8,2,6,6,6
Fifth row is the same as the fourth one.......
If a number repeats k times, 'k' is written k times in the next row,
while, if n numbers repeat k times, 'k' is written nk times in the next row
Further in the next row 'nk' is written nk times in the next row, whatever the positions be
Similarly other numbers come to the third row.
Now in the third row if nk=mp=~~, (mp, if m numbers repeat k times in the first row)and if there x such equivalent conditions,
the fourth row contains 'nk', xnk times
and the fifth row has 'xnk' written xnk times.
This process continues until there are no such equivalence conditions.
Say, these equivalence conditions occur q times,
then (2q+3)th and (2q+4)th rows are identical.
I dont know if the explanation is clear, but that is what I could infer after trying many numbers in a program created on the basis of the given conditions!!![3][4]
[339]
9sir can u post ur argument why #10 or # 16
are not fully convincing solutions ?
they appear fully convincing to me :P
341Yeah, non-decreasing is ok. But from there is a short leap to be taken to land at the solution. Meanwhile celestine is online and come with a solution I hope.
66I think even in the situation mentioned in #18 my arguments remain valid. Each column will be non-decreasing even in that case. But still let me see.
341Actually this argument too will not lead us to the solution.
What could happen is that a certain number b appears b times. But another number a also appears b times. This means a number b does not necessarily remain constant across rows after if it has appeared b times in a particular row.
341A small detail is missing. If that is supplied, then the problem will be convincingly closed.
Hint: (already there in cele's post) under what conditions does a row become identical to the previous?
66I used the idea of the hint given in the book itself and came up with the following:
Suppose that in the n\mathrm{th} row some number a occupies exactly b places. Then in the (n+1)\mathrm{th} row these b positions are occupied by the number b. Hence for each n\geq 2 we can conclude that:
The number of occurrences of an integer a in the n\mathrm{th} row is an integral multiple of a, say ka where k is the number of those entries which appeared exactly a times in the (n-1)\mathrm{th} row.
As such from the n\mathrm{th} row onwards, we have beneath the entries a an integers ka\geq a. Hence, the sequence of the integers in each column beginning with the second row is an non-decreasing sequence of numbers which is bounded by 1000 above. As such in each of the 1000 columns the same number is going to be repeated from a certain row onwards. Accordingly, sooner or later we shall come across a row starting from which all the subsequent rows are going to be identical.
9well i cud infer that a particular integer x shud be repeated x times for it to be feasible
trying to solve
62Will it suffice that there are a finite number of n digit numbers?
9ive indeed proven mathematically only sir !
though im lost for words on how to express it
(i shud admit im quite busy with admission process pls excuse me )
341That is not the crux observation that will solve the problem.
Also it is possible to prove it mathematically. So do try some more.
9eg
1 1 1 1 1 2 2 2 2 3 3 3 3 randomly distinct nos
next row bcoms
5 5 5 5 5 4 4 4 4 4 4 4 4 randomly distinct nos
so the next step is obvious
:D
9the solution is such that i need to express in words
see after rth row either r+1 th row is identical or
r+1 th row is partially identical with a lesser no of identical groups
i think the above statement directly solves the problem
341Your argument does not seem to use induction.
Also, there is no necessity that you will get numbers that repeat 1,2,3, times and so on. You could have several numbers all repeating the same number of times.
For induction to work, you should be able to ignore, say, one particular number k in the row. That means in that row k appears k times. But things get ruined if there is another number in the row that appears k times.
Induction is hence not an option.
11I dunnow whether I'm correct or not....pls correct me if I'm wrong.... P(n) denote the statement that a row repeats at some point with n integers initially repeating.... P(1) is true, Let P(n) be true, For proving P(n+1), we have n+1 integers are repeating, so ai represent the number that repeats i times, i ranges from 1 to (n+1)... So a1,a2,a3,....repeat 1,2,3 times respy... Randomly any order like a1 a3 a2 a2 a3 a4 a3 ..... The next row contains 1 3 2 2 3 4 3 ...... Next row has 1 3 2 2 3 ........exactly identical like the last......
9oops realised my mistake :)
ok anyway yes we can prove this easily
row 1
im shuffling the order and grouping like terms
a1(r1s) a2 (r2s) .......... an (rns)
where a1 + a2 + .........an= 1000
now we have in 2nd row
a1(a1s) a2(a2s) ...............an(ans)
if all ar's are distinct then 3rd row = 2nd row
oops gtg will finish this soon
9wat is it so simple
the 2nd row itself is equal to 3rd row always !