End-state variations in a one-contact information model.

[Ali Sada]

Hi everyone,

Hope all is well. Please see the mathematical exercise below.

 

Title: 

“Number of possible end states in a community of n individuals, where uninformed individuals adopt the state of the first informed or misinformed person they meet, and each individual interacts at most once.”

 

Description:

In a certain community, there are three types of people: informed (i), misinformed (m), and uninformed (u).

• The informed and the misinformed do not seek further knowledge.
• The uninformed, however, want to acquire knowledge by interacting with either informed or misinformed individuals.

The possible interactions are defined as follows:

• u + i → 2i
• u + m → 2m

Each person in the community can participate in only one interaction. In a community of population n, how many distinct end state variations are possible?

Examples:

• n = 1:
  The individual can be {i}, {m}, or {u}.
  → a(1) = 3
• n = 2:
  Possible end states are {2i}, {2m}, {i, m}, and {2u}.
  → a(2) = 4
• n = 3:
  Possible end states: {3i}, {2i, m}, {i , 2m}, {3m}, {2i , u}, {2m, u}, and {3u}.
  → a(3) = 7
• n = 4:
  Possible end states: {4i}, {3i, m}, {2i , 2m}, {i , 3m}, {4m}, {2i, 2u}, {2m, 2u}, and {4u}.
  → a(4) = 8

 

I would really appreciate it if you could tell me if this sequence is suitable for the OEIS.

 

Best,

 

Ali

 

[Martin Fuller]

Is this a standard model in the literature?

I don't understand how the interactions work. How are they chosen? Are they one-way or two-way? Sequential or simultaneous?

[Michael Branicky]

Ali,

I am getting this is 3, 4, 7, 8, 12, 13, 18, 19, 25, ..., or your a(n) = A165157(n+1).

Regards,

Michael

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/ecd7ff86-0fd9-4bd8-92f1-b95ab27af114n%40googlegroups.com.

[Michael Branicky]

Empirically, I have verified that relationship through n = 175. Probably not too hard to prove, given description at A165157.

If you "mark" those that have interacted/combined and distinguish them from those who have not, I get the counts are: 3, 6, 11, 17, 26, 36, 50, 65, 85, 106, 133, 161, ..., which matches A003453(n+5). Empirically verified through n = 113.

[Ali Sada]

Thank you, Jon, Martin, and Michael, for your response. I really appreciate them.

 

Jon, you’re right. My initial description left some ambiguity about how the pairings occur. The uninformed people seek knowledge. So, they would pair with someone with information (good or bad) when they have the chance. They don’t interact with each other. So, an end state like {i,m,u,u} cannot happen because if it was a start state the u’s will seek knowledge from the i and the m and this will end up {i,i,m,m}. And it can't be an end state because {i,u,u,u}à{i,i,u,u} and {m,u,u,u}à{m,m,u,u}.

And I sincerely apologize for not responding to your abstract model. I have a kind of ADHD and it’s very difficult for me to understand abstract math statements. Would what I said above change the model?  

 

Martin, I don’t know if this is within the literature. It’s just a math practice from a non-expert. According to ChatGPT, “It’s more of a combinatorial toy model inspired by limited-contact information spread” and “All pairings happen simultaneously (not sequentially)”.

 

Michael, do you think it’s worth a new sequence? Or should we add it, with Jon’s model, to A165157?

 

Best,

 

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD0v53yCLHqeQ-%2B0V7h-ePf4ai6xTDCoEPrQjJFNJiKTFHcK1w%40mail.gmail.com.

[Michel Marcus]

Chat gpt ?  Frau Blücher !!!

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNrZeQo%3DqEHhiqBNHZzTqNSKsQ0EJUfdZtot0db1D1017Q%40mail.gmail.com.

[Michael Branicky]

If you can PROVE the relationship, perhaps a comment in A165157, but definitely not a new sequence since it is "essentially the same"

I can not see Jon's model in this thread, but was able to discern the rules from your initial post.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNrZeQo%3DqEHhiqBNHZzTqNSKsQ0EJUfdZtot0db1D1017Q%40mail.gmail.com.

[Ali Sada]

I am not sure I can prove it. Which means we want to add a new sequence! 

This is Jon's model " You could model this more abstractly as follows: start with a multiset
of n items that are either 1, -1, or 0. Now partition the multiset into
dyads (leaving one item as a singleton, if n was odd). Now within each
dyad, replace any 0 by the non-zero value in that dyad, if there is one.
Then take the union of all the dyads (plus potentially the singleton),
i.e. "flatten" the multiset. How many possible final multisets are there
if the initial multiset had n items?"

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD0v53z7Wwjy0KhzyJ8vuuhUHiZu8xqVAzEh3MzoP0UPLQVzgA%40mail.gmail.com.

[Michael Branicky]

You don't add a sequence that is "essentially the same"

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CACOfRNoUUOBNv_HFxuLJt51nuSSFBVKDR9VmR6mbT1T2rZ%2B5zA%40mail.gmail.com.

[Ali Sada]

Oh come on Michel. Haven't you noticed that you are spending less time editing my sequences now? Either a miracle happened and my language improved exponentially, or I am getting some help from my little brother Chati (in addition to Michael's supervision). And please put in mind that very soon our AI Masters will control the world, and since they already have full access to our emails, I advise you to be careful when you talk about them. 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFxT7zUR5KaYH9gVVurEFdbEFc%2Bxto7%3DqAvCP-TNbH%2BEdRJ_pQ%40mail.gmail.com.

[Jonas Karlsson]

My interpretation is the following: first, suppose the number of individuals is even, say 2n. Since they have no properties other than their epistemic state, we might as well pair them up first, so now we have n pairs of individuals with no properties (if you are a Rawlsian you might want to interview them now, before they are spoiled).

Next we assign epistemic states {u, i, m} to all the individuals in all possible ways. This is the same as assigning a pair of states {uu, ui, um, ii, im, mm} to each pair of individuals in all possible ways. If we let the numbers uu be x_1, and so on up to x_6 = the number of mm, then the set of all assignments is the integer points in the 5-simplex x_i >= 0 for every i, and x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = n (there being n pairs).

Then the interactions happen, as described by Ali. If we tally up the numbers of u's, i's and m's as a triple, we get (I get):

(u, i, m) = (2x_1, 2x_2 + 2x_4 + x_5, 2x_3 + x_5 + 2x_6)

The number of i's is 2x_2 + 2x_4 + x_5 since every initial ui turns into ii and contributes 2, every initial ii remains ii and contributes 2, and every initial im remains im and contributes 1; analogously for the two other counts.

So we are counting the number of integer points in the image of the set of integer points in a 5-simplex, under a linear map. If I've done my algebra correctly, the images of the vertices of the simplex are

(2n, 0, 0), once; (0, 2n, 0), twice; (0, 0, 2n), twice; and (0, n, n), once.

Now we need to ask ourselves if every integer point here is the image of an integer point. The answer is 'no' because the first coordinate (the u-count) depends only on x_1 and changing x_1 by 1 will change u by 2. So the u-count will be even but this is the only constraint - changing x_5 will change the parity of i and m.

So I find that the number of possible final states is the number of triples (u, i, m) where all coordinates are non-negative integers, where u is even and where u + i + m = 2n. The should be a quasipolynomial in n. There are quite possibly numerical slips in the above but I think the general form of the argument is sound.

This was all assuming the number of individuals is even. Adding an odd one seems like an unnecessary complication since it will not interact.

As for inclusion-worthiness, my opinion is that this is interesting. 

J

[Jon Wild]

The more abstract way I suggested of framing the problem no longer
applies, since Ali has added a restriction on how individuals pair up
(two uninformed individuals somehow know to avoid each other without
using up their sole interaction). Of course it could be fixed (just
forbid partitions that include dyads of two zeroes (uninformeds)), if
someone cared to and thought the abstract model was more relevant.

-Jon

> more of a *combinatorial toy model* inspired by limited-contact

> information spread”and “All pairings happen simultaneously (not
> sequentially)”.
>
> Michael, do you think it’s worth a new sequence? Or should we
> add it, with Jon’s model, to A165157?
>
> Best,
>
> Ali
>
>
>
> On Thu, Oct 30, 2025 at 7:29 AM Michael Branicky
> <bran...@gmail.com <mailto:bran...@gmail.com>> wrote:
>
> Ali,
>
> I am getting this is 3, 4, 7, 8, 12, 13, 18, 19, 25, ..., or
> your a(n) = A165157(n+1).
>
> Regards,
> Michael
>
>
> On Thu, Oct 30, 2025 at 3:38 AM 'Martin Fuller' via SeqFan

> <seq...@googlegroups.com <mailto:seq...@googlegroups.com>>

> wrote:
>
> Is this a standard model in the literature?
> I don't understand how the interactions work. How are
> they chosen? Are they one-way or two-way? Sequential or
> simultaneous?
>
> On Thursday, October 30, 2025 at 6:15:10 AM UTC

> ali....@gmail.com <mailto:ali....@gmail.com> wrote:
>
>
> Hi everyone,
>
>
> Hope all is well. Please see the mathematical
> exercise below.
>

> *Title: *

>
> “Number of possible end states in a community of n
> individuals, where uninformed individuals adopt the
> state of the first informed or misinformed person
> they meet, and each individual interacts at most once.”
>

> *Description: *

>
> In a certain community, there are three types of
> people: informed (i), misinformed (m), and
> uninformed (u).
>

> * The informed and the misinformed do not seek
> further knowledge.
> * The uninformed, however, want to acquire

> knowledge by interacting with either informed or
> misinformed individuals.
>
> The possible interactions are defined as follows:
>

> * u + i → 2i
> * u + m → 2m

>
> Each person in the community can participate in only
> one interaction. In a community of population n, how
> many distinct end state variations are possible?
>

> *
> *
>
> **
>
> *Examples:*
>
> * n = 1:
> The individual can be /{i}, {m}, or {u}./
> → a(1) = 3
> * n = 2:
> Possible end states are {/2i}/, {/2m}/, {/i,
> m}/, and {/2u}/.
> → a(2) = 4
> * n = 3:
> Possible end states: {/3i}/, {/2i, m}/, {/i ,
> 2m}/, {/3m}/, {/2i , u}/, {/2m, u}, and {3u}/.
> → a(3) = 7
> * n = 4:
> Possible end states: {/4i}/, {/3i, m}/, {/2i ,
> 2m}/, {/i , 3m}/, {/4m}/, {/2i, 2u}/, {/2m, 2u},
> and {4u}/.

> → a(4) = 8
>
> I would really appreciate it if you could tell me if
> this sequence is suitable for the OEIS.
>
> Best,
>
> Ali
>
>
> --
> You received this message because you are subscribed to
> the Google Groups "SeqFan" group.
> To unsubscribe from this group and stop receiving emails
> from it, send an email to
> seqfan+un...@googlegroups.com

> <mailto:seqfan+un...@googlegroups.com>.

> To view this discussion visit https://groups.google.com/
> d/msgid/seqfan/ecd7ff86-0fd9-4bd8-92f1-

> b95ab27af114n%40googlegroups.com <https://
> can01.safelinks.protection.outlook.com/?
> url=https%3A%2F%2Fgroups.google.com%2Fd%2Fmsgid%2Fseqfan%2Fecd7ff86-0fd9-4bd8-92f1-b95ab27af114n%2540googlegroups.com%3Futm_medium%3Demail%26utm_source%3Dfooter&data=05%7C02%7Cjon.wild%40mcgill.ca%7C95ce99eb05fb46b3677a08de17be7d1e%7Ccd31967152e74a68afa9fcf8f89f09ea%7C0%7C0%7C638974304074863497%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=XQ1wAuXG3SgRexjYxp5kJ%2BqV3Ovd45Q7OpJyU3FZE%2Fs%3D&reserved=0>.

>
> --
> You received this message because you are subscribed to the
> Google Groups "SeqFan" group.
> To unsubscribe from this group and stop receiving emails
> from it, send an email to
> seqfan+un...@googlegroups.com

> <mailto:seqfan+un...@googlegroups.com>.

> To view this discussion visit https://groups.google.com/d/

> msgid/seqfan/CAD0v53yCLHqeQ-%2B0V7h-
> ePf4ai6xTDCoEPrQjJFNJiKTFHcK1w%40mail.gmail.com <https://
> can01.safelinks.protection.outlook.com/?
> url=https%3A%2F%2Fgroups.google.com%2Fd%2Fmsgid%2Fseqfan%2FCAD0v53yCLHqeQ-%252B0V7h-ePf4ai6xTDCoEPrQjJFNJiKTFHcK1w%2540mail.gmail.com%3Futm_medium%3Demail%26utm_source%3Dfooter&data=05%7C02%7Cjon.wild%40mcgill.ca%7C95ce99eb05fb46b3677a08de17be7d1e%7Ccd31967152e74a68afa9fcf8f89f09ea%7C0%7C0%7C638974304074909457%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=reSTvQNQrF5V17kKnsa3Ka19QF897UzBp89A5d8P08w%3D&reserved=0>.

>
> --
> You received this message because you are subscribed to the
> Google Groups "SeqFan" group.
> To unsubscribe from this group and stop receiving emails from
> it, send an email to seqfan+un...@googlegroups.com

> <mailto:seqfan+un...@googlegroups.com>.

> To view this discussion visit https://groups.google.com/d/msgid/
> seqfan/

> CACOfRNrZeQo%3DqEHhiqBNHZzTqNSKsQ0EJUfdZtot0db1D1017Q%40mail.gmail.com <https://groups.google.com/d/msgid/seqfan/CACOfRNrZeQo%3DqEHhiqBNHZzTqNSKsQ0EJUfdZtot0db1D1017Q%40mail.gmail.com?utm_medium=email&utm_source=footer>.

>
> --
> You received this message because you are subscribed to the Google
> Groups "SeqFan" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to seqfan+un...@googlegroups.com

> <mailto:seqfan+un...@googlegroups.com>.

> To view this discussion visit https://groups.google.com/d/msgid/
> seqfan/

> CAD0v53z7Wwjy0KhzyJ8vuuhUHiZu8xqVAzEh3MzoP0UPLQVzgA%40mail.gmail.com
> <https://can01.safelinks.protection.outlook.com/?
> url=https%3A%2F%2Fgroups.google.com%2Fd%2Fmsgid%2Fseqfan%2FCAD0v53z7Wwjy0KhzyJ8vuuhUHiZu8xqVAzEh3MzoP0UPLQVzgA%2540mail.gmail.com%3Futm_medium%3Demail%26utm_source%3Dfooter&data=05%7C02%7Cjon.wild%40mcgill.ca%7C95ce99eb05fb46b3677a08de17be7d1e%7Ccd31967152e74a68afa9fcf8f89f09ea%7C0%7C0%7C638974304074974200%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=uV1B7fWm8Q%2FpGWLRqv7dsAmlGcCzl6OCXln3e63bF9w%3D&reserved=0>.

>
> --
> You received this message because you are subscribed to the Google
> Groups "SeqFan" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to seqfan+un...@googlegroups.com

> <mailto:seqfan+un...@googlegroups.com>.

> To view this discussion visit https://groups.google.com/d/msgid/seqfan/

> CACOfRNoUUOBNv_HFxuLJt51nuSSFBVKDR9VmR6mbT1T2rZ%2B5zA%40mail.gmail.com
> <https://can01.safelinks.protection.outlook.com/?
> url=https%3A%2F%2Fgroups.google.com%2Fd%2Fmsgid%2Fseqfan%2FCACOfRNoUUOBNv_HFxuLJt51nuSSFBVKDR9VmR6mbT1T2rZ%252B5zA%2540mail.gmail.com%3Futm_medium%3Demail%26utm_source%3Dfooter&data=05%7C02%7Cjon.wild%40mcgill.ca%7C95ce99eb05fb46b3677a08de17be7d1e%7Ccd31967152e74a68afa9fcf8f89f09ea%7C0%7C0%7C638974304074998565%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=A0F4zeGb4IzUAb5pTaHkPuqw1RnpKvgn7u6PxDeWyl8%3D&reserved=0>.

[Jonas Karlsson]

Right, forbidding uu imposes x_1 = 0 and gives a different quasipolynomial from the one I didn't compute. :)

[Ali Sada]

Thank you, Jonas. I really appreciate it. 

Michael, can you please help me with your sequences (terms, definition, etc.) so that I could add it? 

Jon, I will add your comment to A165157, with your permission. Also, I can submit the sequence generated from your first model, and include Joans' analysis, if the editors approve. 

Best,

Ali  

To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/05e08276-7ad9-4489-b511-8422ae0b921en%40googlegroups.com.

[M F Hasler]

On Thu, Oct 30, 2025 at 7:29 AM Michael Branicky <bran...@gmail.com> wrote:

Ali,

I am getting this is 3, 4, 7, 8, 12, 13, 18, 19, 25, ..., or your a(n) = A165157(n+1).

Michael,

What do you get as possible outcomes for n=5?

I get the following 13 (not 12) possible ( i, m, u ) :

all(5)
 = [[0, 0, 5], [0, 2, 3], [0, 4, 1], [0, 5, 0], [1, 4, 0], [2, 0, 3], [2, 2, 1], [2, 3, 0], [3, 1, 1], [3, 2, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]

and terms

[a(n) | n<- [1..19]]
 = [3, 4, 7, 8, 13, 14, 21, 22, 31, 32, 43, 44, 57, 58, 73, 74, 91, 92, 111]

(not in the OEIS)

- Maximilian 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD0v53yCLHqeQ-%2B0V7h-ePf4ai6xTDCoEPrQjJFNJiKTFHcK1w%40mail.gmail.com.

[Michael Branicky]

For 5, I get:

{'iiimm', 'iiiii', 'mmuuu', 'iimmm', 'mmmmu', 'uuuuu', 'mmmmm', 'iiuuu', 'iimmu', 'iiiiu', 'immmm', 'iiiim'} 12

The discrepancy is you have [3, 1, 1] and I don't.

But, then shouldn't you have [1, 3, 1] by symmetry?

[Jon Wild]

Michael Branicky wrote to MF Hasler:

> The discrepancy is you have [3, 1, 1] and I don't.

[3,1,1] {iiimu} as an end-state is only reachable from [2,1,2] {iimuu}
IF the rules that allow one individual to remain unpartnered when n is
odd include the possibility that it could be one of the u's that remains
unpartnered. I still don't know what Ali intended there. (But yes if
[3,1,1] is reachable then so is [1,3,1].)

[Michael Branicky]

I don't allow unpartnered states. I only count "end states" where no further interactions are possible.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/89f7de45-70ed-4fc0-bfc3-8035dd6ab18d%40mcgill.ca.

[Ali Sada]

Hi everyone,

 

Let x be the number of u’s in each start state, and S=int((n-1)/2).

We have four categories of start states:

a)      x=n, this is an end state since no interaction happens.

b)     x=0. This will give us n+1 start states, all of them are also end states.  

c)      x<S. Here all the start states end up in category b, so no new end state happens.

d)     x>=S. Here the start states have a number of u's between n-1 and S.

(n-1) u's gives 2 new end states, (n-2) u's gives us 3 new end states, and so on, up to S u's which gives us S+1 end states. So, the number of new end states will be T(S+1)-1.

 

So, the final number of options will be n+1+T(S+1). Which is A165157(n+1). So, maybe we can add a comment to A165157, and submit a new sequence for the other version?  

 

Best,

 

Ali

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAD0v53ykf09JzSDpZDYfYRu2s18mHUwkyNsWt5Zv7gS0-V5YAA%40mail.gmail.com.

[M F Hasler]

On Thu, Oct 30, 2025 at 11:17 PM Ali Sada <ali....@gmail.com> wrote:

Hi everyone,

 

Let x be the number of u’s in each start state, and S=int((n-1)/2).

We have four categories of start states:

a)      x=n, this is an end state since no interaction happens.

b)     x=0. This will give us n+1 start states, all of them are also end states.  

c)      x<S. Here all the start states end up in category b, so no new end state happens.

d)     x>=S. Here the start states have a number of u's between n-1 and S.

(n-1) u's gives 2 new end states, (n-2) u's gives us 3 new end states, and so on, up to S u's which gives us S+1 end states. So, the number of new end states will be T(S+1)-1.

 

So, the final number of options will be n+1+T(S+1). Which is A165157(n+1). So, maybe we can add a comment to A165157, and submit a new sequence for the other version?  

Excellent suggestion!

(PS: I confirmed off-list to Michael that the spurious (3,1,1) listed by my program was incorrect,

I still don't know how it could occur... Sorry for the confusion this may have caused.

Actually my program reasons in the same way as Ali outlines above,

but there was a bug when it explicitly created the possibilities.)

[Ali Sada]

Thank you Maximilian. Is this comment suitable?

"a(n+1) counts the number of distinct end states in a one-interaction knowledge model. In a community of n people, each person is either informed (i), misinformed (m), or uninformed (u). Uninformed individuals must interact when possible, adopting the state of the first informed or misinformed person they meet: u + i → 2i, u + m → 2m. Every person can interact at most once."

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFqvfd-VhZ7rOTOSAyhg2PypdnzBCajMNkbH9iXYtMoLP5jXXw%40mail.gmail.com.